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

Regarde, la fibre est

t(n) = t(n - 1) + n ;

si n = 0 alors 1

pour voir comment la récursion fonctionne, je remplace simplement n en t(n) con n-1 et ainsi de suite. Il semble :

t(n-1) = t(n - 2) + n+1 ;

t(n-1) = t(n - 3) + n+1 + n ;

t(n-1) = t(n - 4) + n+1 + n+2 + n ;

.

.

.

t(n) = t(n-k)+ ... + (n-k-3) + (n-k-2)+ (n-k-1)+ n ;

nous savons que si t(0)=(n-k) est égal à 1 puis n-k=0 donc n=k nous remplaçons k con n :

t(n) = t(n-n)+ ... + (n-n+3) + (n-n+2)+ (n-n+1)+ n ;

si nous omettons n-n alors :

t(n)= t(0)+ ... + 3+2+1+(n-1)+n ;

donc 3+2+1+(n-1)+n est un nombre naturel. Il se calcule comme suit Σ3+2+1+(n-1)+n = n(n+1)/2 => n²+n/2

le résultat pour fib est : O(1 + n²) = O(n²)

C'est la meilleure façon de comprendre la relation récursive.

Answer 2

Partage d'un code plus simple pour fibrer en JS/ES6 en utilisant la récursion.

function fib(n, first = 1, second = 1) {
    if (n <= 2) return 1;
    [first, second] = [second, first + second];
    return (n - 2 === 1) ? second : fib(n - 1, first, second);
}

console.log(fib(10));