Récursivité, ou pas ?

Version imprimable

12/05/2015, 22h50
N_BaH

Récursivité, ou pas ?
Bonjour à tous,

ici, je lis
Citation:
Envoyé par Sve@r

[...]la factorielle sans boucle ni récursivité

Code:

1 2 3 4 5 6 7 #!/bin/bash test -z "$arg" && arg=$1 && res=1 test $arg -eq 0 && echo $res && exit 0 res=$(($res * $arg)) arg=$(($arg - 1)) source $0
moi, je vois de la récursivité dans un script qui se source lui-même, mais s'appellerait-il (sans se sourcer), jusqu'à une condition donnée, que j'en verrais encore...

Citation:

Envoyé par Sve@r

Ressembler n'est pas jouer. Comme Canada Dry. Ca a la couleur de l'alcool, son nom sonne comme un nom d'alcool mais ce n'en est pas. Donc ça a la couleur de la récursivité, son nom sonne comme un nom de récursivité... mais ce n'en est pas

Ceci dit, effectivement je pense qu'un débat à ce propos intéresserait pas mal de monde. Peut-être dans une section plus générale du shell...

j'ouvre donc le débat.
12/05/2015, 22h56
Flodelarab

Bonjour :coucou:

Ce qui serait plus constructif serait que ceux qui pensent que ce code n'est pas récursif nous explique pourquoi, selon eux.
12/05/2015, 23h11
xflr6

Pour moi aussi, c'est récursif.

Pour l'opinion contraire, les amateurs comme moi (je n'ai utilisé source que pour sourcer des variables...) auraient pu penser à "source" comme un "include" agissant non au runtime mais en style préprocesseur, mais ça n'est pas le cas selon l'aide de bash.

Cordialement,
xflr6
13/05/2015, 00h02
BufferBob
http://fr.wikipedia.org/wiki/Récursivité :
Citation:
La récursivité est une démarche qui fait référence à l'objet de la démarche. Ainsi, les cas suivants constituent des cas concrets de récursivité :
(...)
Écrire un algorithme qui s'invoque lui-même.
(...)
En informatique et en logique, une fonction ou plus généralement un algorithme qui contient un appel à elle-même est dite récursive.
ça revient à considérer ce que fait le code plutôt que l'interface qu'il utilise pour le faire, ça a du sens non ?
13/05/2015, 00h19
disedorgue

Bonjour,
En principe, dans la récursivité, il y a une notion de pile. Ici je vois plus une notion de Méta-programmation (une forme de duplication de données qui devient du code).

PS: un simple code de factoriel(6): echo $(($(seq -s '*' 1 6)))

Bonjour,

Citation:

Envoyé par disedorgue

dans la récursivité, il y a une notion de pile.

"pile" me semble plus connoté "structure de données" alors que récursif est vraiment connoté "action dont la réal appelle à renouveler action".
Certes, on peut sans doute utiliser une technique de récursion pour aller chercher dans une pile, mais c'est à mon sens plus général que ça.

Citation:

Envoyé par disedorgue

Ici je vois plus une notion de Méta-programmation (une forme de duplication de données qui devient du code).

C'était le sens de mon commentaire qques posts plus haut:

Citation:

[On pourrait] penser à "source" comme un "include" agissant non au runtime mais en style préprocesseur, mais ça n'est pas le cas selon l'aide de bash.

En effet,
Code:

1 2 3 4 5 6 7 8 9 10 11 12 $ help source source: source nom_fichier [arguments] Execute des commandes depuis un fichier dans le shell actuel. Lit et exécute des commandes depuis NOMFICHIER dans le shell actuel. Les éléments dans $PATH sont utilisés pour trouver le répertoire contenant NOMFICHIER. Si des ARGUMENTS sont fournis, ils deviennent les paramètres de position lorsque NOMFICHIER est exécuté. Code de sortie : Renvoie le code de la dernière commande exécutée dans NOMFICHIER, ou le code d'échec si NOMFICHIER ne peut pas être lu.
qui me donne vraiment l'impression que c'est au runtime que c'est effectué.

De toute manière, on ne pourrait pas sortir de la duplication sans exécuter la commande test $arg -eq 0 && echo $res && exit 0.
Donc que ce soit du point de vue "codeur" ou du point de vue "interpréteur", c'est selon moi récursif.

Cordialement,
xflr6

Bonjour

J'aime bien la remarque sur la notion de pile car elle est importante. En effet, il est arrivé parfois que certains codeurs simulent la récursivité en empilant et dépilant eux-mêmes les informations nécessaires au calcul sans passer par le mécanisme récursif qui va lui, empiler et dépiler tout l'environnement de travail (c'est plutôt vu dans des langages comme le C ou le Pascal). Ca arrive surtout quand la vitesse est importante et que le mécanisme récursif est trop coûteux en temps.
Dans ce cas là, le code n'est pas considéré comme du code récursif.

Ici c'est pareil. Il n'y a pas d'empilement. Le shell déroule et exécute juste un code qui se génère au fur et à mesure. Par exemple, pour la factorielle de 3, ce code sera
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #!/bin/bash test -z "$arg" && arg=3 && res=1 # Ici arg vaut 3 et res vaut 1 test $arg -eq 0 && echo $res && exit 0 # Le test est faux res=$(($res * $arg)) # Ici res vaut 3 arg=$(($arg - 1)) # Ici arg vaut 2 #!/bin/bash # Comme il n'est pas sur la première ligne ça devient un simple commentaire test -z "$arg" && arg=3 && res=1 # Ici arg vaut 2 et res vaut 3 test $arg -eq 0 && echo $res && exit 0 # Le test est faux res=$(($res * $arg)) # Ici res vaut 6 arg=$(($arg - 1)) # Ici arg vaut 1 #!/bin/bash # Comme il n'est pas sur la première ligne ça devient un simple commentaire test -z "$arg" && arg=3 && res=1 # Ici arg vaut 1 et res vaut 6 test $arg -eq 0 && echo $res && exit 0 # Le test est faux res=$(($res * $arg)) # Ici res vaut 6 arg=$(($arg - 1)) # Ici arg vaut 0 #!/bin/bash # Comme il n'est pas sur la première ligne ça devient un simple commentaire test -z "$arg" && arg=3 && res=1 # Ici arg vaut 0 et res vaut 6 test $arg -eq 0 && echo $res && exit 0 # Le test est vrai donc affichage 6 et sortie du shell
Ce code est-il un code récursif ??? Le shell n'a fait que dérouler une suite d'instructions et de calculs sans mettre en jeu le lourd mécanisme d'empilement/dépilement nécessaire à la récursivité. Bien entendu ça a l'esprit de la récursivité, mais ce n'en est pas.

PS: j'ai bien aimé le code de disedorgue :applo:
D'ailleurs son code comme le mien font tous deux appels à des possibilités offertes par les outils de notre environnement. Moi j'utilise une possibilité offerte par le runtime (certains l'ont appelé "préprocesseur") et lui un outil extérieur qui affiche une séquence.

13/05/2015, 10h12
BufferBob

salut,

Citation:

Envoyé par Sve@r

Ce code est-il un code récursif ??? Le shell n'a fait que dérouler une suite d'instructions et de calculs sans mettre en jeu le lourd mécanisme d'empilement/dépilement nécessaire à la récursivité.

ben on pourrait penser que si justement, on prend un code en 3 partie; 1-début, 2-sourcing, 3-suiteducode, l'interpréteur évalue la 1ere partie, puis... la 2e ? donc il source le même script, évalue à nouveau la 1ère partie etc. et pour revenir à la partie 3-suiteducode il a forcément du stacker quelque chose un moment donné à mon sens, elle est là la récursivité

edit: c'est même assez limpide pour ma part, ça l'aurait été beaucoup moins avec un truc genre exec $0 par exemple
13/05/2015, 11h24
Flodelarab
- Bien vu! J'allais dire pareil.
- Que veut dire GNU ?
  "GNU" = "GNU not Unix"
  
  Que veut dire Wine ?
  "Wine" = "Wine Is Not an Emulator"
  
  Voilà des acronymes récursifs. Il n'y a aucune pile.
- Seuls ceux qui ont eu le plaisir de faire exploser une pile par "stack overflow" comprennent que la récursivité, ça n'est joli que pour les mathématiciens. Sinon, c'est une horreur. Mais de nos jours, les piles sont très grosses.
- Citation:
  
  "action dont la réal appelle à renouveler action"
  
  Hum. Là tu abordes la nuance entre itératif et récursif. Ce qui fait qu'on parle de "récursion" est l'appel à soi-même. Le fait que les instructions soient réitérées n'est qu'un dommage collatéral.
- Toute boucle ne pourrait-elle pas être considérée comme récursive car se rebranchant sur son début continuellement ?
13/05/2015, 11h50
xflr6

Pour la différence entre récursif et itératif, il y a dans mon ressenti une notion de scope.
Pour moi, la décision de renouveler l'action en itératif est prise en dehors de l'algo à l'intérieur de la boucle, alors qu'en récursif, elle est dedans. Non ?

Cordialement,
xflr6.

du coup que penser d'un truc comme ça (hormis que c'est crado :aie:) :
Code:

1 2 3 4 5 6 7 8 9 #!/bin/bash [[ $2 = $1 ]] && { s=${3:1} echo -ne "$1! = $s\n$1! = $((s))\n" exit 0 } || { i=$(($2+1)) exec $0 $1 $i "${3}*${i}" }
et l'invocation :
Code:

1 2 3 $ ./factorielle 6 6! = 1*2*3*4*5*6 6! = 720
récursif ou pas ?

13/05/2015, 13h04
disedorgue

Citation:

Envoyé par xflr6

Pour la différence entre récursif et itératif, il y a dans mon ressenti une notion de scope.
Pour moi, la décision de renouveler l'action en itératif est prise en dehors de l'algo à l'intérieur de la boucle, alors qu'en récursif, elle est dedans. Non ?

Je suis d'accord sur ce point de vu, on pourrait même rajouter que dans l'itératif, la décision d'arrêt est visible ce qui permet parfois aux compilateur de supprimer une boucle itérative en calculant directement son résultat.
Dans le récursif, il y a aussi une notion de réentrance, et dans le cas du sourcing, peut-on dire qu'il y a réentrance ?

En tout cas, le récursif n'est pas à proscrire quand on connait la limite de profondeur.
Lors de mes études en fac, j'ai eu à programmer les règles du jeux de dame (règle française), j'ai présenté 2 versions:
Une itérative qui faisait environ 200 lignes mais que tout le monde pouvait comprendre en lisant le code.
Puis une version récursive sur 3 fonctions => 30 lignes de code, mais là, même le prof était perplexe sur le fonctionnement :aie:

PS: une méthode builtin pour CERTAINES version bash (4.1.4): echo $(($(echo {1..6}'*')1))
13/05/2015, 13h35
Flodelarab

Très important de toujours multiplier par 1 :D

Mais dans cette dernière version le 6 n'est pas variable.

Alors que "echo $(($(seq -s '*' 1 6)))" peut être changé par "echo $(($(seq -s '*' 1 $n)))". Auquel cas le 1 est important.
13/05/2015, 19h39
disedorgue

Ok, une version builtin bash variabilisée:

Code:

X=6 && printf -v YY "%0${X}d\n" 0 && echo $((${YY//0/X--*}1))

Là pour le coups, peut-on considérer qu'elle est récursive ?
13/05/2015, 21h47
xflr6

Non, mais c'est joli.
- Je ne connaissais pas le printf dans une variable [mon man non plus d'ailleurs ?],
- Je n'avais jamais osé les opérateurs increment/decrement en bash.
Ca va m'être utile, merci.

xflr6
14/05/2015, 10h10
Sve@r
Citation:

Envoyé par Flodelarab

Que veut dire GNU ?
"GNU" = "GNU not Unix"

Que veut dire Wine ?
"Wine" = "Wine Is Not an Emulator"

Voilà des acronymes récursifs. Il n'y a aucune pile.

Définition donnée pour ces acronymes de façon humoristique. Conceptuellement ce ne sont pas des acronymes vraiment récursifs sinon chacun devrait être redécrit à chaque fois qu'on l'écrit et ça partirait à l'infini.
Ce n'est pas parce que les créateurs de ces acronymes ont employé le terme "récursif" (ce sont tous des acronymes informatiques donc ils ont voulu donner leur donner un adjectif à connotation informatique) que c'est du vrai récursif et qu'on peut alors les utiliser comme base de référence pour définir ce qui est récursif et ce qui ne l'est pas. http://fr.wikipedia.org/wiki/R%C3%A9...A9#cite_note-3.

Citation:

Envoyé par Flodelarab

Toute boucle ne pourrait-elle pas être considérée comme récursive car se rebranchant sur son début continuellement ?

Je crois qu'on inverse le problème. Un peu comme Pythagore quand il disait que le nombre 10 était un nombre parfait et que même les dieux le savaient car ils nous avaient donnés dix doigts. Les premiers langages ne connaissaient pas la récursivité. Celui qui voulait explorer un arbre en profondeur devait se débrouiller pour empiler/dépiler lui-même ses éléments de recherche. Je me souviens de mon premier code en Basic où je voulais afficher toutes les lettres de "aaaaaaaaa" jusqu'à "zzzzzzzzz" pour reproduire l'intrigue de la nouvelle d'Arthur C. Clarke. Ca avait l'air trivial pourtant j'en ai bavé. Ensuite, quand je l'ai réécrit en C ça a été effectivement beaucoup plus trivial...

Ensuite les concepteurs de langages ont automatisé cet empilement/dépilement ce qui a permis effectivement de créer les structures de boucles. En effet, devoir se rebrancher sur le début correspondant à la fin de boucle implique forcément un empilement de chaque début de boucle et un dépilement en fin de boucle pour pouvoir revenir à ce début. Et ça je l'ai compris le jour où j'ai voulu écrire mon compilateur Brainfuck et où j'ai dû empiler chaque position correspondant à "[" (début de boucle) pour pouvoir y revenir (goto) chaque fois que je tombais sur un "]" (fin de boucle).
Ca a permis aussi de créer la récursivité (permettre à une fonction de s'appeler elle-même). Mais empiler/dépiler n'est pas du récursif. Certes la récursivité exige de l'empilement (pour pouvoir revenir en fin d'action au point où l'action commence) mais on peut très bien écrire soi-même cet empilement pour arriver au résultat. Et dans ce cas, ce n'est plus du récursif. C'est plutôt un retour à "avant" la récursivité. D'ailleurs même moi je me trompe quand je dis qu'on "simule" la récursivité. C'est plutôt la récursivité qui "simule" (ou plutôt "automatise") un algorithme fait à partir d'empilements/dépilements de ses éléments nécessaires...

Bien entendu que mon code est récursif. D'ailleurs on ne peut pas calculer la factorielle sans passer soit par du récursif, soit par de l'itératif. Mais ma récursivité était cachée derrière un outil qui, BufferBob l'a bien fait remarquer, est forcément récursif. Mon trait était plutôt un trait d'humour pour MR-SMOOT (débutant) que je comptais plonger dans une amusante perplexité.
Ce trait est d'ailleurs repris avec autant d'humour par disedorgue qui utilise, lui, de l'itératif caché derrière des outils de répétition...:plusser:

PS: un code moins crado pour BufferBob qui a suggéré la possibilité exec...
Code:

1 2 3 4 5 6 #!/bin/bash res=${2:-1} test $1 -gt 1 && exec $0 $(($1 - 1)) $(($1 * $res)) echo $res

Citation:

Envoyé par xflr6

- Je ne connaissais pas le printf dans une variable [mon man non plus d'ailleurs ?],

Ici, j'utilise la builtin bash, donc tu peux le voir en utilisant le help de bash qui est très utile:
Code:

1 2 3 4 5 6 7 8 9 $ help printf printf: printf [-v var] format [arguments] Formats and prints ARGUMENTS under control of the FORMAT. Options: -v var assign the output to shell variable VAR rather than display it on the standard output ... ...
Citation:

Envoyé par Flodelarab

Toute boucle ne pourrait-elle pas être considérée comme récursive car se rebranchant sur son début continuellement ?

Sve@r à déjà très bien débattu ce point, mais rappelons aussi que la boucle fait partie intégrante des instructions processeur via ces débranchements conditionnels.

14/05/2015, 11h50
xflr6

Citation:

Envoyé par Sve@r

le jour où j'ai voulu écrire mon compilateur Brainfuck

Je vois un soupçon de récursivité là-dedans :lol:
14/05/2015, 11h52
jack-ft
Citation:

Envoyé par Flodelarab

Seuls ceux qui ont eu le plaisir de faire exploser une pile par "stack overflow" comprennent que la récursivité, ça n'est joli que pour les mathématiciens. Sinon, c'est une horreur.

C'est du troll ou quoi? :mouarf:

Pour ma part, il me semble intéressant de distinguer les différents "types" de récursivité en fonction du nombre de réentrances (appels de "foo" dans l'implémentation de "foo")
- 1
  Lorsqu'il n'y en a qu'une (comme pour la factorielle), l'algo peut la plupart du temps être transformé en récusivité terminale voire en simple itération (donc pas besoin de pile).
- 2 ou plus (mais fixe)
  Lorsque le nombre d'appels est fixe, mais supérieur à 1, c'est déjà plus délicat.
  Le cas simple est "fibonacci" qui, de récursif (à 2 appels réentrants):
  Code:
  
  1 2 3 4 5 define fibonacci (N) if N == 0 or N == 1 then return N else return fibonacci (N - 1) + fibonacci (N - 2) fi
  peut facilement (mais astucieusement) être converti en itératif:
  Code:
  
  1 2 3 4 5 6 7 8 9 10 define fibonacci (N) fibN-2 := 0 fibN-1 := 1 fibN := fibN-2 for I from 1 to N do fibN := fibN-1 + fibN-2 fibN-2 := fibN-1 fibN-1 := fibN done return fibN
  Pour l'exploration d'un arbre binaire, c'est déjà moins simple et le récursif s'impose généralement:
  Code:
  
  1 2 3 4 define GRD (tree) if left(tree) is_a_tree then GRD(left(tree)) fi racine(tree) if right(tree) is_a_tree then GRD(right(tree)) fi
- X (variable)
  Le cas le plus courant est celui de l'exploration d'un arbre N-aire
  Par exemple, dans beaucoup de jeux, dans chaque position, j'ai un certain nombre de coups à ma disposition. Pour chacun de ces coups, j'obtiens une nouvelle position, et je plonge jusqu'à... soit trouver ce que je cherche (solution, gain, perte, etc.) soit j'arrête à une profondeur donnée ou après un temps donné parce que sinon ça va coûter trop cher!
  Dans ces cas-là, l'écriture récursive est beaucoup plus simple à écrire, lire et maintenir, et on laisse le compilateur ou l'interpréteur gérer le boulot (trivial) de la récursivité (empilement, gestion du contexte et des valeurs de retour).
  Code:
  
  1 2 3 4 define explore (tree) for subtree in subtrees(tree) do explore subtree done
  Et puis il y a les cas "tordus"...
  Challenge: Quelqu'un a-t-il une implémentation non récursive de la fonction d'Ackermann? :mouarf:
Citation:

Mais de nos jours, les piles sont très grosses.

Comme ça, on peut repousser les limites pour la profondeur d'exploration!
15/05/2015, 00h09
BufferBob
Citation:

Envoyé par jack-ft

Lorsqu'il n'y en a qu'une (comme pour la factorielle), l'algo peut la plupart du temps être transformé en récusivité terminale voire en simple itération (donc pas besoin de pile).

oui, c'est ce que font certains compilateurs d'ailleurs, ils "transforment" ou "considèrent" les fonctions récursives terminales comme des itérations (c'est le cas du compilateur Scheme par exemple: "Ce que dit très précisément la norme de Scheme, c'est qu'une récursivité terminale sera traitée comme une itération, donc sans pile.")

du coup est-ce qu'on considère toujours qu'il s'agit d'un code récursif ? (le code en lui même ne change pas, il s'appelle bien lui même etc. mais le code généré, le traitement lui est une itération)
- si "oui", ça veut dire que la récursion tient à la forme du code, donc tout code qui fait mine de s'appeler lui même, y compris un 10 goto 10, est considéré comme récursif, une forme particulière de récursion, c'est ce que dit Flodelarab
- si "non", ça veut dire que la différence entre l'itération et la récursion tient bel et bien à la notion de pile, la seule différence entre une itération et une fonction récursive terminale étant que l'une sort directement par le dernier appel tandis que l'autre remonte toute la pile d'appel avant de sortir, et dans ce cas ça veut dire qu'autant le code avec source $0 peut facilement être considéré comme récursif compte tenu du fait que bash doit pouvoir revenir à la suite du premier appelant pour sortir, autant le code avec exec $0 ne l'est pas, puisqu'il n'empile rien, quand bien même il s'agit du même processus tout du long
mieux encore; le source $0 étant la dernière instruction, si bash est suffisament intelligent il peut éventuellement envisager de dérouler le tout comme une itération lui aussi (du coup pour avoir la réponse à la question initiale posée par N_BaH, il va falloir se palucher les sources de bash, qui est chaud ? :mouarf:)

finalement ça revient essentiellement à une question de fond et de forme...

Citation:

Envoyé par BufferBob

oui, c'est ce que font certains compilateurs d'ailleurs, ils "transforment" ou "considèrent" les fonctions récursives terminales comme des itérations (c'est le cas du compilateur Scheme par exemple: "Ce que dit très précisément la norme de Scheme, c'est qu'une récursivité terminale sera traitée comme une itération, donc sans pile.")

Oui, c'est ce que faisait déjà le compilateur Le_Lisp (dans les années 70-80). Comme le pseudo-assembleur virtuel LLM3 généré était "facile" à lire, on pouvait vérifier que le compilateur utilisait un "goto" (sans pile) et non un "gosub" (avec empilement du contexte).

Attention toutefois à certains pièges. J'ai dit:

Citation:

Envoyé par jack-ft

Lorsqu'il n'y en a qu'une (comme pour la factorielle), l'algo peut la plupart du temps être transformé en récusivité terminale voire en simple itération (donc pas besoin de pile).
Code:

1 2 3 4 5 define factorielle (N) if N == 0 then return 1 else return N * factorielle (N - 1) fi
Ce code n'est pas récursif terminal, contrairement à ce qu'il pourrait sembler à première vue!
(voir le premier contre-exemple de http://fr.wikipedia.org/wiki/Récursion_terminale)

En effet, bien que l'appel de factorielle (N - 1) semble apparaitre en dernier dans le code, il faut d'abord calculer N et factorielle (N - 1) avant de les multiplier entre eux. Dans ce cas, le compilateur ne peut pas se passer de pile (pour empiler N et la référence de l'appel à la multiplication, puis N-1 et la référence de l'appel à la multiplication, etc.)!
Je serais surpris, voire impressionné, si un compilateur arrivait à transformer ce code en itération!
Alors qu'un bête être humain le fait sans problème en énumérant les nombres à multiplier (soit de 1 à N, soit de N à 1):
Code:

1 2 3 4 5 6 7 define factorielle (N) RESULT := 1 for I from 1 to N do RESULT *= I I++ done return RESULT
D'ailleurs, dans toutes les formules données par récurrence (au sens mathématique), comme factorielle ou fibonacci, il est plus simple de calculer les valeurs dans l'ordre croissant, en mémorisant/stockant celles qui seront utiles pour le calcul de l'élément suivant.
Ainsi, il suffit de garder (dans un coin) factorielle(n) pour calculer factorielle(n+1).
Il suffit de garder (dans 2 coins) fibo(n-1) et fibo(n) pour calculer le suivant fibo(n+1). (voir algo précédemment donné)
Évidemment, dans des cas plus compliqués, comme la fonction d'Ackermann (ou d'autres fonctions à plus d'un argument), le nombre de coins peut exploser!

Ce procédé peut d'ailleurs plus ou moins être automatisé en remplaçant les fonctions par des "fonctions-mémoire", qui se souviennent de tous les éléments déjà calculés et retournent la valeur calculée et stockée plutôt que de la recalculer.

Pour la factorielle, ce n'est pas intéressant si on n'a qu'un seul calcul de factorielle à effectuer. En revanche, si on en a un 2ème, si le nombre est plus petit, le résultat est immédiatement retourné, et s'il est plus grand, seules les multiplications supplémentaires seront effectuées.

Pour fibonacci, c'est intéressant dès le premier calcul:
Code:

1 2 3 4 5 6 7 8 9 10 11 define fibonacci (N) if is_stored_fibonacci(N) then return stored_value_fibonacci(N) elsif N == 0 then store_fibonacci(0, 1) return 1 elsif N == 1 then store_fibonacci(1, 1) return 1 else return fibonacci (N - 1) + fibonacci (N - 2) fi
Ce code (qui reste récursif) ne fait que 2*N additions, alors que, dans le code récursif traditionnel, le nombre d'additions est exponentiel (de l'ordre de ((sqrt(5)+1)/2)**N probablement (à vérifier...)).

Citation:

Envoyé par jack-ft

D'ailleurs, dans toutes les formules données par récurrence (au sens mathématique), comme factorielle ou fibonacci, il est plus simple de calculer les valeurs dans l'ordre croissant, en mémorisant/stockant celles qui seront utiles pour le calcul de l'élément suivant.
Ainsi, il suffit de garder (dans un coin) factorielle(n) pour calculer factorielle(n+1).
Il suffit de garder (dans 2 coins) fibo(n-1) et fibo(n) pour calculer le suivant fibo(n+1). (voir algo précédemment donné)

Ce procédé peut d'ailleurs plus ou moins être automatisé en remplaçant les fonctions par des "fonctions-mémoire", qui se souviennent de tous les éléments déjà calculés et retournent la valeur calculée et stockée plutôt que de la recalculer.

Ce qui, en Python, est très facile à faire grâce aux décorateurs. Suffit de l'écrire puis on le positionne sur la fonction de son choix (qui, elle, reste inchangée dans son code)...
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #!/usr/bin/env python # -*- coding: utf-8 -*- def optimize(func): def wrapper(n): print "début wrapper" # Si le nombre n'a pas déjà été traité if n not in wrapper.__tab.viewkeys(): # On le traite et on le mémorise wrapper.__tab[n]=func(n) # if print "fin wrapper" # Ici le nombre a été traité et son résultat mémorisé - On le renvoie return wrapper.__tab[n] # wrapper() wrapper.__tab={} return wrapper # optimize() @optimize # Positionnement du décorateur sur la factorielle (on ne change absolument rien à son code d'origine) def factorielle(n): print "inside fact", n if n < 2: return 1 return n * factorielle(n-1) # factorielle() @optimize # Positionnement du décorateur sur la fibonacci def fibonacci(n): print "inside fib", n if n <= 2 : return 1 return fibonacci(n-2)+fibonacci(n-1) # fibonacci() print factorielle(5) # Ici la fonction fera tout le calcul en récursif print factorielle(4) # Ici son décorateur prendra le relai et renverra la valeur déjà calculée lors de 5 * fact(4) print fibonacci(7) # Ici la fonction fera tout le calcul en récursif (mais fera appel au décorateur à chaque fois qu'un fib(X) déjà calculé sera redemandé) print fibonacci(4) # Ici son décorateur prendra le relai et renverra la valeur déjà calculée lors de fibonacci(4) + fibonacci(5)
Le calcul d'un fibonacci(41) prend 27 secondes en récursif standard... et il est instantané en utilisant les décorateurs. Dommage qu'il n'y ait pas de décorateur en shell...

Citation:

Envoyé par jack-ft

Alors qu'un bête être humain le fait sans problème en énumérant les nombres à multiplier (soit de 1 à N, soit de N à 1):

Oui. Mais l'humain un peu moins bête fait alors partir son énumération à 2 et non 1 ;)

17/05/2015, 00h42
disedorgue

Citation:

Envoyé par jack-ft

Et puis il y a les cas "tordus"...
Challenge: Quelqu'un a-t-il une implémentation non récursive de la fonction d'Ackermann? :mouarf:

Pour ceux que cela peut intéresser, il y a le lien ci-dessous qui donne l'écriture de la fonction d'Ackermann dans un nombre impressionnant de langage et dont une version itérative en perl ainsi que d'autres versions qui utilise la "mémoïsation":
http://rosettacode.org/wiki/Ackermann_function