Comment fonctionne la fonction récursive de fibonacci?

Je suis nouveau sur Javascript et je lisais à ce sujet lorsque je suis arrivé à un chapitre qui décrivait la récursion des fonctions. Il a utilisé un exemple de fonction pour trouver le nième numéro de la séquence de Fibonacci. Le code est comme suit:

function fibonacci(n) { if (n < 2){ return 1; }else{ return fibonacci(n-2) + fibonacci(n-1); } } console.log(fibonacci(7)); //Returns 21 

J’ai du mal à comprendre exactement ce que fait cette fonction. Quelqu’un peut-il expliquer ce qui se passe ici? Je suis coincé sur la 5ème ligne, où la fonction s’appelle elle-même. Qu’est-ce qu’il se passe ici?

Vous définissez une fonction en soi. En général, fibonnaci(n) = fibonnaci(n - 2) + fibonnaci(n - 1) . Nous représentons simplement cette relation dans le code. Donc, pour fibonnaci(7) on peut observer:

  • fibonacci(7) est égal à fibonacci(6) + fibonacci(5)
  • fibonacci(6) est fibonacci(5) à fibonacci(5) + fibonacci(4)
  • fibonacci(5) est fibonacci(4) à fibonacci(4) + fibonacci(3)
  • fibonacci(4) est égal à fibonacci(3) + fibonacci(2)
  • fibonacci(3) est égal à fibonacci(2) + fibonacci(1)
  • fibonacci(2) est fibonacci(1) à fibonacci(1) + fibonacci(0)
  • fibonacci(1) est égal à 1
  • fibonacci(0) est égal à 1

Nous avons maintenant toutes les pièces nécessaires pour évaluer fibonacci(7) , ce qui était notre objective initial. Notez que le cas de basereturn 1 lorsque n < 2 - est ce qui rend cela possible. C'est ce qui arrête la récursivité, afin que nous puissions lancer le processus de déroulement de la stack et faire la sum des valeurs renvoyées à chaque étape. Sans cette étape, nous continuerions à appeler fibonacci sur des valeurs de plus en plus petites jusqu'à ce que le programme tombe en panne.

Il pourrait être utile d'append des instructions de consignation illustrant ceci:

 function fibonacci(n, c) { var indent = ""; for (var i = 0; i < c; i++) { indent += " "; } console.log(indent + "fibonacci(" + n + ")"); if (n < 2) { return 1; } else { return fibonacci(n - 2, c + 4) + fibonacci(n - 1, c + 4); } } console.log(fibonacci(7, 0)); 

Sortie:

 fibonacci(7) fibonacci(5) fibonacci(3) fibonacci(1) fibonacci(2) fibonacci(0) fibonacci(1) fibonacci(4) fibonacci(2) fibonacci(0) fibonacci(1) fibonacci(3) fibonacci(1) fibonacci(2) fibonacci(0) fibonacci(1) fibonacci(6) fibonacci(4) fibonacci(2) fibonacci(0) fibonacci(1) fibonacci(3) fibonacci(1) fibonacci(2) fibonacci(0) fibonacci(1) fibonacci(5) fibonacci(3) fibonacci(1) fibonacci(2) fibonacci(0) fibonacci(1) fibonacci(4) fibonacci(2) fibonacci(0) fibonacci(1) fibonacci(3) fibonacci(1) fibonacci(2) fibonacci(0) fibonacci(1) 

Les valeurs au même niveau d'indentation sont additionnées pour produire le résultat pour le niveau d'indentation précédent.

Il y a beaucoup de bonnes réponses ici, mais j’ai fait ce diagramme qui aide à mieux expliquer le résultat de la fonction. Les seules valeurs qui seront jamais retournées sont 1 ou 0 (votre exemple renvoie 1 pour n <2, mais devrait plutôt renvoyer n).

Cela signifie que chaque appel récursif finira par retourner un 0 ou un 1. Ceux-ci finissent par être “mis en cache” dans la stack et “transférés” dans l’invocation d’origine et ajoutés ensemble.

Donc, si vous deviez dessiner ce même diagramme pour chaque valeur de ‘n’, vous pourriez trouver la réponse manuellement.

Ce diagramme illustre grossièrement comment chaque fonction est renvoyée pour fib (5).

! [Diagramme d'arborescence Javascript de Fibonacci

Cela montre le stream de contrôle, c’est-à-dire l’ordre d’exécution des fonctions. Rappelez-vous que le code est toujours exécuté de gauche à droite et de haut en bas. Donc, chaque fois qu’une nouvelle fonction est appelée, elle est mise en pause et l’invocation suivante se produit.

Ce qui suit illustre le stream de contrôle réel basé sur votre message d’origine. Veuillez noter que la condition de base est if (n <= 0) {return 0} else if (n <= 2) {return 1;} pour simplifier:

 1. fib(5) { return fib(4) + fib(3); 2. fib(4) { return fib(3) + fib(2); 3. fib(3) { return fib(2) + fib(1); 4. fib(2) { A= return 1; }; 5. fib(1) { B= return 1; }; C= return 2; // (1 + 1) }; 6. fib(2) { D= return 1; }; E= return 3; // (2 + 1) }; 7. fib(3) { return fib(2) + fib(1); 8. fib(2) { F= return 1; }; 9. fib(1) { G= return 1; }; H= return 2; // (1 + 1) }; I= return 5; // (3 + 2) }; 

Etape 1) Quand on appelle fibonacci(7) imaginez ce qui suit (remarquez comment j’ai changé tous les n à 7):

 function fibonacci(7) { if (7 < 2){ return 1; }else{ return fibonacci(7-2) + fibonacci(7-1); } } 

Etape 2) Puisque (7 < 2) est évidemment faux, on passe à fibonacci(7-2) + fibonacci(7-1); qui se traduit par fibonacci(5) + fibonacci(6); Puisque fibonacci(5) vient en premier, cela s'appelle (change le n à 5 cette fois):

 function fibonacci(5) { if (5 < 2){ return 1; }else{ return fibonacci(5-2) + fibonacci(5-1); } } 

Etape 3) Et ou bien, fibonacci(6) également appelé, alors ce qui est arrivé est pour tout le monde appel de fibonacci 2 nouveaux fibonacci sont appelés.

Visualisation:

  fibonacci(7) ____|_____ | | fibonacci(5) fibonacci(6) ____|____ ____|_____ | | | | fib(3) fib(4) fib(4) fib(5) 

Voyez comment ça se twig? Quand est-ce que ça va s'arrêter? Lorsque n devient inférieur à 2, c'est pourquoi vous avez if (n < 2) . À ce stade, le twigment s'arrête et tout est ajouté.

J’espère que les aides suivantes. Appel:

 fibonacci(3) 

ira à la ligne 5 et fera:

 return fibonacci(1) + fibonacci(2); 

la première expression appelle à nouveau la fonction et renvoie 1 (depuis n < 2 ).

La seconde appelle à nouveau la fonction, arrive à la 5ème ligne et fait:

 return fibonacci(0) + fibonacci(1); 

les deux expressions renvoient 1 (puisque n < 2 pour les deux), donc cet appel à la fonction renvoie 2.

Donc, la réponse est 1 + 2, qui est 3.

Je pense que ces deux fonctions m’ont donné une explication beaucoup plus claire de la récursivité (à partir de cet article de blog ):

 function fibDriver(n) { return n === 0 ? 0 : fib(0, 1, n); } function fib(a, b, n) { return n === 1 ? b : fib(b, a + b, n-1); } 

Pour calculer le nième nombre de fibonacci, la relation est F (n) = F (n-2) + F (n-1).

Si nous implémentons la relation dans le code, pour le nième nombre, nous calculons le (n-2) ème et (n-1) e nombre en utilisant la même méthode.

Chaque numéro suivant est la sum des deux nombres précédents. Ainsi, le septième nombre est la sum des sixième et cinquième chiffres. Plus généralement, le nième nombre est la sum de n – 2 et n – 1, tant que n> 2. Comme les fonctions récursives ont besoin d’une condition d’arrêt pour arrêter la récurrence, ici n <2 est la condition.

f (7) = F (6) + F (5);

à son tour, F (6) = F (5) + F (4)

F (5) = F (4) + F (3) … continue jusqu’à n <2

F (1) renvoie 1

La fonction s’appelle elle-même. C’est simplement la définition d’une fonction récursive. Dans la 5ème ligne, il transfère l’exécution à lui-même en passant des parameters qui aboutissent à une valeur.

Pour s’assurer qu’une fonction récursive ne se transforme pas en une boucle sans fin, il doit y avoir une sorte de condition qui ne s’appelle pas elle-même. Le but de votre code dans la question est d’effectuer les calculs d’une séquence de fibonacci.

 
    / *
 * Étapes de récursion Fibonacci
 * 1) 3 est passé.  (3 est imprimé à l'écran pendant cet appel)
 * 2) Fibonacci A obtient des décréments de 2 et la récursivité se produit en passant 1 comme paramètre.  (1 est imprimé à l'écran pendant cet appel)
 * 3) Fibonacci A frappe le cas de base renvoyant 1 et il "se déroule".  (Pas de récursivité ici)
 * 4) Fibonacci B est appelé, décrémentant la valeur précédente de n (3 était la valeur précédente de n avant que A ne réponde à l'appel) à 2. (2 est imprimé à l'écran pendant cet appel)
 * 5) Fibonacci A est appelé à nouveau en soustrayant 2 de n (2-2 = 0) et passe 0 comme paramètre.  (1 est imprimé à l'écran pendant cet appel depuis qu'il est converti de 0)
 * 6) Fibonacci A frappe le cas de base et "se déroule" (pas de récursivité ici)
 * 7) Fibonacci B est appelé soustraire 1 de 2 (2 était la valeur précédente de n avant que A ne fasse l'appel retourné) et passe 1 comme paramètre.  (1 est imprimé à l'écran pendant cet appel)
 * 7) Fibonacci B frappe maintenant le cas de base, retournant 1 et "se déroule" (pas de récursivité ici)
 * 8) Fibonacci B retrace ses pas en arrière Tous les appels et valeurs de fucntion précédents de n (n = 2 dans notre cas) et ajoute [les] à la copie de n = 1 stockée dans sa scope locale
 * 9) Une fois que Fibonacci B a terminé le processus de "déroulement", il renvoie la valeur calculée à l'appelant d'origine (pas de récursivité ici)

  Remarque* 
     Chaque instance de récursivité Fibonacci crée sa propre scope et stocke la valeur renvoyée dans une copie de n (dans notre cas 1). 
     Comme la fonction "se déroule", elle exécute le code suivant qui reçoit la valeur de n à ce moment-là.  (toutes les fonctions qui appellent d'autres fonctions se "détendent" à travers les appels précédents une fois qu'elles reviennent)

     Dans le dernier appel de notre exemple de Fibonacci, Fibonacci B reçoit la valeur de n = 2 car Fibonaccci A "se déroule" car c'était la dernière valeur avant l'appel.
     Une fois que Fibonacci B a atteint le cas de base et "déroulé", il est revenu sur toutes les valeurs précédentes de n (dans notre cas, juste n = 2) et l'a ajouté à sa copie locale de n = 1.

 * Le résultat au passage du nombre 3 est le suivant: 
                 3
                  1
                  2
                   1
                   1
             (3)
 * /
 var div = document.getElementById('fib'); function fib( n, c ) { var indent = ""; for (var i = 0; i < c; i++) { indent += " "; } var v = n===0 ? 1 : n var el = document.createElement('div'), text = indent + "fibonacci(" + v + ")"; el.innerHTML = text; div.appendChild(el); if(n<2){ return 1; } return fib(n-2, c + 4) + fib(n-1, c + 4); 

}

Algorithme de Fibonacci avec fonction récursive basée sur ES6

 const fibonacci = ( n, k = 1, fib2 = 0, fib1 = 1 ) => { return k === n ? (() => { return fib1; })() : (() => { k++; return fibonacci(n, k, fib1, fib1 + fib2); })(); } console.info(' fibonacci ' + 11 + ' = ' + fibonacci(11));