Comment est-ce que ça a obtenu 8 ?

Question

Voici le code :

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

    public static void main(String[] arg) 
    {
        System.out.println(fibonacci(5));
    }
}

La sortie était de 8. La sortie devrait être 8 mais quand je regarde ça, je pense que ça devrait être 7 ( (5-1) +(5-2) ).

Pourquoi la sortie était-elle de 8 ? Je pense que le raisonnement derrière l'obtention de 8 fera que la récursion cessera peut-être d'être confuse pour moi.

Answer 1

Parce que c'est un appel récursif, donc chaque appel où l'argument n'est pas 0 ou 1 le rappelle.

fibonacci(7)
-> fibonacci(6) // recursively calls itself with (7-1)
   -> fibonacci(5) // recursively calls itself with (6-1)
      -> fibonacci(4) // recursively calls itself with (5-1)
         -> fibonacci(3) // recursively calls itself with (4-1)
            -> fibonacci(2) // recursively calls itself with (3-1)
               -> fibonacci(1) // recursively calls itself with (2-1)
   -> fibonacci(4) // recursively calls itself with (6-2)
        ...
-> fibonacci(5) // recursively calls itself with (7-2)
   -> fibonacci(4) // recursively calls itself with (5-1)
      -> fibonacci(3) // recursively calls itself with (4-1)
         -> fibonacci(2) // recursively calls itself with (3-1)
            -> fibonacci(1) // recursively calls itself with (2-1)
   -> fibonacci(3) // recursively calls itself with (5-2)
      ...

et ainsi de suite.

Pensez à la logique de cette façon, et vous devriez être en mesure de déterminer ce qu'elle renvoie réellement à l'appelant initial.

Answer 2

Traitons ça comme de l'algèbre, je vais écrire f(n) au lieu de fibonacci(n) pour gagner de l'espace :

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

Answer 3

C'est le retour fibonacci(n-1) pas n-1 . Quand vous appelez ça avec 5, vous obtenez :

return fib(4) + fib(3);

fib(4) revient :

return fib(3) + fib(2);

fib(3) revient :

return fib(2) + fib(1);

fib(2) retourne :

return fib(1) + fib(0);

Dès que vous atteignez fib(1) ou fib(0), vous retournez 1 ;

Travailler à l'envers, fib(2) retourne 2 :

return 1 /*fib(1)*/ + 1 /*fib(0)*/;

Par la même logique, fib(3) renvoie à 2 + 1 ou 3. Fib(4) renvoie à 3 + 2 ou 5. Fib(5) pour cela, il retourne 5 + 3 qui est votre 8.

Answer 4

Ce n'est pas ((5-1) + (5-2)) mais plutôt (finonacci(5-1) + fibonacci(5-2))

Y finonacci(5-1) réduit à fibonacci(4) ce qui donne (finonacci(4-1) + fibonacci(4-2)) etc.

Answer 5

Peut-être que cette illustration adaptée du Structure et interprétation des programmes informatiques (SICP, ou le livre Wizard) vous aidera :

Pour prendre la tangente, SICP est une introduction à la programmation fantastiquement profonde, bien que parfois difficile. Comme il utilise Lisp (plutôt Scheme) comme langage d'enseignement, la récursion est utilisée partout. Même les processus itératifs en Lisp sont basés sur des appels récursifs :

(define (factorial n)
  (define (fact-iter n product)
    (if (> n 1) 
        (fact-iter (- n 1) (* product n))
        product
  ) )
  (fact-iter n 1)
)

(factorial 5)
; returns 120

est en fait itératif . Notes : car renvoie la tête d'une liste, tandis que cdr renvoie la queue. Les opérateurs utilisent notation du préfixe ; (- a b) est "a - b", (* a b) est "a * b".

Voici à quoi ressemble votre programme Fibonacci en Scheme :

(define (fibonacci n)
  (if (or (= n 1) (= n 2))
      1
      (+ (fibonacci (- n 1)) (fibonacci (- n 2)))
  )