Comment "fonctionne" la fonction récursive de Fibonacci ?

Question

Je suis novice en Javascript et j'étais en train de me documenter sur le sujet, lorsque je suis arrivé à un chapitre décrivant la récursion des fonctions. Il utilisait une fonction d'exemple pour trouver le nième nombre de la séquence de Fibonacci. Le code est le suivant :

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 ce que fait exactement cette fonction. Quelqu'un peut-il m'expliquer ce qui se passe ici ? Je suis bloqué à la 5e ligne, où la fonction s'appelle elle-même. Que se passe-t-il ici ?

Answer 1

La fonction s'appelle elle-même. C'est tout simplement la définition d'une fonction récursive. À la 5e ligne, elle se transfère l'exécution à elle-même en passant des paramètres qui donneront 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 que n'a pas s'appelle lui-même. Le but de votre code dans la question est d'effectuer les calculs d'une séquence de fibonacci.

Answer 2

Pour calculer le nième nombre de Fibonacci, la relation est la suivante 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)ième et le (n-1)ième nombre en utilisant la même méthode.

Chaque nombre suivant est la somme des deux nombres précédents. Ainsi, le septième nombre est la somme des sixième et cinquième nombres. Plus généralement, le nième nombre est la somme de n - 2 y n - 1 pour autant que n > 2 . Comme les fonctions récursives ont besoin d'une condition d'arrêt pour arrêter la récursion, ici n<2 est la condition.

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

in turn, F(6) = F(5) + F(4)

F(5) = F(4) + F(3)...

cela continue jusqu'à ce que n<2

F(1) returns 1

Answer 3

   /\*
\* Steps Fibonacci recursion
\* 1) 3 gets passed. (3 is printed to the screen during this call)
\* 2) Fibonacci A gets decrements by 2 and recursion happens passing 1 as a param. (1 is printed to the screen during this call)
\* 3) Fibonacci A hits the base case returning 1 and it "unwinds". (No recursion here)
\* 4) Fibonacci B gets called, decrementing the previous value of n (3 was the previous value of n before A made the returning call) to 2. (2 is printed to the screen during this call)
\* 5) Fibonacci A is called again subtracting 2 from n (2-2=0) and passes 0 as a param. (1 is printed to the screen during this call since it's converted from 0)
\* 6) Fibonacci A hits the base case and "unwinds" (no recursion here)
\* 7) Fibonacci B is called subtracting 1 from 2 (2 was the previous value of n before A made the returning call) and passes 1 as a param. (1 is printed to the screen during this call)
\* 7) Fibonacci B now hits the base case, returning 1 and "unwinds" (no recursion here)
\* 8) Fibonacci B retraces it's steps back through All previous fucntion calls and values of n (n=2 in our case) and adds \[them\] to the copy of n=1 stored in its local scope
\* 9) Once Fibonacci B completes the "unwinding" process, it returns the calculated value to the original caller (no recursion here)

 Note\* 
    Each instance of Fibonacci recursion creates its own scope and stores the returned value in a copy of n (in our case 1). 
    As it the function "unwinds" it executes subsequent code that receive the value of n at that time. (all functions that call other functions "unwind" back through previous calls once they return)

    In the last call of our Fibonacci example, Fibonacci B receives the value of n=2 as Fibonaccci A "unwinds" since that was the last value before it made the returning call.
    Once Fibonacci B reached the base case and "unwound", it retraced its steps back through all previous values of n (in our case just n=2) and added \[them\] to its local copy of n=1.

\* The result when passing the number 3 is: 
                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);

}

Answer 4

Ça va se passer comme ça :

7 - 2 = 5 --> fibonacci(5)
7 - 1 = 6 --> fibonacci(6)

Comme indiqué dans la mise en œuvre, le côté gauche diminuera toujours par

2 et la main droite diminue de 1 donc il sera casé de cette façon jusqu'à ce qu'il atteigne 1 une fois qu'il aura atteint 1 il l'ajoutera aux sorties de la fonction de droite. 1 + fibonacci(n-1); qui, elle aussi, s'arrêtera toujours à 1 conformément à la mise en œuvre :

if (n < 2){
  return 1;
}

Finalement, ils finissent tous par avoir 1 en mémoire et commencez à les additionner de gauche à droite... considérez la représentation en cascade ci-dessous, en additionnant tous les 1 en bas de l'écran feront en sorte que 21 .

if n > 2 ______________Gauche toujours n - 2 __________&____________Right always n - 1 ________ else n = 1

                                        7

                        5                              6
                   3          4                  4              5
                 1    2    2     3            2     3      3        4
               1     1 1  1 1  1   2         1 1  1  2   1  2    2    3
                                  1 1               1 1    1 1  1 1  1  2
                                                                       1 1

               1+    1+1+ 1+1 1+  1+1+       1+1+ 1+1+1+ 1+1+1+ 1+1+ 1+1+1 = 21

La 7ème position dans la séquence de Fibonacci est 21, nous pouvons la tester avec le tableau :

const fibArray = [1, 1, 2, 3, 5, 8, 13, 21]
console.log(fibArray[7]) //-> 21

Answer 5

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));