这是怎么得到8的？

Question

这是代码:

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

输出是8.输出应该是8但是当我看这个时我觉得它应该是7((5-1) +(5-2)).

为什么输出8？我认为获得8后面的推理会使递归可能不再让我感到困惑.

Answer 1

让我们把它当成代数,我会写f(n)而不是fibonacci(n)为了节省空间:

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 2

因为它是一个递归调用,所以每个参数不是0或1的调用再次调用它.

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

等等.

想想这样的逻辑,你应该能够弄清楚它实际返回到初始调用者的内容.

Answer 3

它正在回归fibonacci(n-1),而不是n-1.用5来调用它时,你得到:

return fib(4) + fib(3);

fib(4)返回:

return fib(3) + fib(2);

fib(3)返回:

return fib(2) + fib(1);

fib(2)返回:

return fib(1) + fib(0);

一旦达到fib(1)或fib(0),你就返回1;

向后工作,fib(2)返回2:

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

通过相同的逻辑,fib(3)返回2 + 1或3. Fib(4)返回3 + 2,或5. Fib(5)因此返回5 + 3,这是你的8.

Answer 4

也许这个改编自计算机程序的结构和解释(SICP,或向导书)的插图将有助于:

alt text http://img58.imageshack.us/img58/8575/fib5.gif

SICP在切线方面走得非常深,虽然有时难以引入编程.由于它使用Lisp(而不是Scheme)作为其教学语言,因此始终使用递归.甚至Lisp中的迭代过程都基于递归调用:

(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

实际上是迭代的.注意:car返回列表的头部,同时cdr返回尾部.运算符使用前缀表示法 ; (- a b)是"a - b",(* a b)是"a*b".

这是你的Fibonacci程序在Scheme中的样子:

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