Suite récursive de Fibonacci en Java

Question

Veuillez expliquer ce code simple :

public int fibonacci(int n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
      return 1;
   else
      return fibonacci(n - 1) + fibonacci(n - 2);
}

Je suis confus avec la dernière ligne surtout parce que si n = 5 par exemple, alors fibonacci(4) + fibonacci(3) serait appelé et ainsi de suite mais je ne comprends pas comment cet algorithme calcule la valeur à l'indice 5 par cette méthode. Veuillez m'expliquer avec beaucoup de détails !

Answer 1

Dans la suite de Fibonacci, chaque élément est la somme des deux précédents. Donc, vous avez écrit un algorithme récursif.

Donc,

fibonacci(5) = fibonacci(4) + fibonacci(3)

fibonacci(3) = fibonacci(2) + fibonacci(1)

fibonacci(4) = fibonacci(3) + fibonacci(2)

fibonacci(2) = fibonacci(1) + fibonacci(0)

Maintenant, vous savez déjà fibonacci(1)==1 and fibonacci(0) == 0 . Vous pouvez donc calculer les autres valeurs par la suite.

Maintenant,

fibonacci(2) = 1+0 = 1
fibonacci(3) = 1+1 = 2
fibonacci(4) = 2+1 = 3
fibonacci(5) = 3+2 = 5

Et de la séquence de Fibonacci 0,1,1,2,3,5,8,13,21.... nous pouvons voir que pour 5th element la séquence de fibonacci revient 5 .

Voir ici pour Tutoriel sur la récursion .

Answer 2

Il y a deux problèmes avec votre code :

1. Le résultat est stocké dans int qui ne peut traiter que les 48 premiers nombres de fibonacci, après cela l'entier remplit le bit moins et le résultat est faux.
2. Mais vous ne pouvez jamais exécuter fibonacci(50).
   Le code
   fibonacci(n - 1) + fibonacci(n - 2)
   est très mauvaise.
   Le problème est qu'il appelle Fibonacci non pas 50 fois mais beaucoup plus.
   Au début, il appelle fibonacci(49)+fibonacci(48),
   suivant fibonacci(48)+fibonacci(47) et fibonacci(47)+fibonacci(46)
   A chaque fois, il est devenu fibonacci(n) pire, donc la complexité est exponentielle.

L'approche du code non-récursif :

 double fibbonaci(int n){
    double prev=0d, next=1d, result=0d;
    for (int i = 0; i < n; i++) {
        result=prev+next;
        prev=next;
        next=result;
    }
    return result;
}

Answer 3

En pseudo-code, où n = 5, le processus suivant se déroule :

fibonacci(4) + fibonnacci(3)

Cela se décompose en :

(fibonacci(3) + fibonnacci(2)) + (fibonacci(2) + fibonnacci(1))

Cela se décompose en :

(((fibonacci(2) + fibonnacci(1)) + ((fibonacci(1) + fibonnacci(0))) + (((fibonacci(1) + fibonnacci(0)) + 1))

Cela se décompose en :

((((fibonacci(1) + fibonnacci(0)) + 1) + ((1 + 0)) + ((1 + 0) + 1))

Cela se décompose en :

((((1 + 0) + 1) + ((1 + 0)) + ((1 + 0) + 1))

Cela se traduit par : 5

Étant donné que la séquence de Fibonnacci est 1 1 2 3 5 8 ... Vous pouvez utiliser la même méthodologie pour déterminer les autres itérations.

Answer 4

La récursion peut être difficile à appréhender parfois. Il suffit de l'évaluer sur une feuille de papier pour un petit nombre :

fib(4)
-> fib(3) + fib(2)
-> fib(2) + fib(1) + fib(1) + fib(0)
-> fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
-> 1 + 0 + 1 + 1 + 0
-> 3

Je ne sais pas exactement comment Java évalue cela, mais le résultat sera le même.

Answer 5

C'est la meilleure vidéo que j'ai trouvée qui explique de manière complète la récursion et la séquence de Fibonacci en Java.

http://www.youtube.com/watch?v=dsmBRUCzS7k

C'est son code pour la séquence et son explication est meilleure que ce que je pourrais faire en essayant de la taper.

public static void main(String[] args)
{
    int index = 0;
    while (true)
    {
        System.out.println(fibonacci(index));
        index++;
    }
}
    public static long fibonacci (int i)
    {
        if (i == 0) return 0;
        if (i<= 2) return 1;

        long fibTerm = fibonacci(i - 1) + fibonacci(i - 2);
        return fibTerm;
    }