这是代码：
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 的原因可能会使递归不再让我感到困惑。
让我们把它当作代数，我会写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
因为是递归调用，所以每次调用参数不是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)
...
等等。
想想这样的逻辑，你应该能够计算出它实际返回给初始调用者的内容。
它回来了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)returns2 + 1或 Fib(4)3.returns3 + 2或 Fib(5)5.reforreturns 5 + 3，也就是你的 8.
也许这个改编自计算机程序结构和解释（SICP，或向导书）的插图会有所帮助：
切线切线，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”。
这是您的斐波那契程序在 Scheme 中的样子：
(define (fibonacci n)
(if (or (= n 1) (= n 2))
1
(+ (fibonacci (- n 1)) (fibonacci (- n 2)))
)
不是((5-1) + (5-2))，而是(finonacci(5-1) + fibonacci(5-2))
并finonacci(5-1)减少到fibonacci(4)，变成(finonacci(4-1) + fibonacci(4-2))，等等。
我还没有看到这种方法。想象一下，您正在存储结果并构建它，f[i]调用的结果在哪里fibonacci(i)。0 和 1 是基本情况，其余的都建立在它之上：
f[0] = 1
f[1] = 1
f[2] = f[1] + f[0] = 1 + 1 = 2
f[3] = f[2] + f[1] = 2 + 1 = 3
f[4] = f[3] + f[2] = 3 + 2 = 5
f[5] = f[4] + f[3] = 5 + 3 = 8
return fibonacci (n-1) + fibonacci (n-2);
这实际上不仅仅是在做 (n-1) + (n-2)，而是再次递归调用斐波那契函数。
所以它在做斐波那契 (4) + 斐波那契 (3)。然后该 fib(4) 被评估为 fib(3) + fib(2)，因此它最终返回 fib (3) + fib (2) + fib (3)。同样，这些 fib(3) 中的每一个实际上都是 fib (2) + fib (1)，依此类推。它一直像那样崩溃，直到它击中
if (n == 0 || n == 1)
所以它最终是一堆 fib (1) + fib (0) + fib (1)...，即 1 + 1 + 1...，如果你真的把它全部打破，它最终会变成 8一路下来。
递归实际上与归纳证明的数学概念密切相关——事实上，斐波那契数列是递归定义的，因此在某种程度上，您必须已经用递归术语进行思考才能理解它是如何工作的。
为了更好地理解代码，您可以应用beta 缩减——即将每个函数调用替换为函数本身的主体。
如果fibonacci(n)转换为fibonacci(n - 1) + fibonacci(n - 2)则：
fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(5) = (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
很容易看出这将永远持续下去，除非我们做了一个特殊情况。在这里，我们知道fibonacci(1)转换为1，fibonacci(0)也转换为1。所以我们一直在减少beta，直到我们只剩下一个，看起来像：
fibonacci(5) = ((1 + 1) + (1 + (1 + 1))) + ((1 + 1) + 1)
所以：
fibonacci(5) = 8
函数的结果不是(5 - 1) + (5 - 2), 而是fibonacci( 5 - 1 ) + fibonacci( 5 - 2 )or fibonacci( 4 ) + fibonacci( 3 ), 即 5 + 3。序列为：
1 1 2 3 5 8
0 1 2 3 4 5
第一个斐波那契数是 1,1,2,3,5,8,... 任何其他数字都会出乎意料。