无法理解Michael Goodrich《算法》中特殊递归斐波那契算法的运行逻辑

嘿，我来帮你拆解这个看起来有点反常规的斐波那契递归实现！其实它的核心秘密在于返回值不是单个数字，而是一对值——(fib(n), fib(n-1))，搞懂这一点，整个逻辑就通了。

先看基础情况 #

当n <= 1时，函数返回(n, 0)：

• 当n=1时，返回(1, 0)，对应fib(1)=1，fib(0)=0（符合斐波那契数列的常规定义：fib(0)=0，fib(1)=1）
• 当n=0时，返回(0, 0)，这里第二个值对应fib(-1)，不过递归过程中不会触发这个分支的后续调用，不用纠结它的实际意义

再看递归逻辑 #

当n > 1时，函数先调用fibonacci(n-1)得到一对值(a, b)，这里的a就是fib(n-1)，b是fib(n-2)。然后返回(a+b, a)：

• a + b = fib(n-1) + fib(n-2)，这正好是斐波那契数列的定义，也就是fib(n)
• a就是fib(n-1)，所以新返回的一对值就是(fib(n), fib(n-1))，完美完成递推链条

用n=5的例子一步步走一遍 #

我们直接模拟代码的执行过程，看每一层返回的是什么：

1. fibonacci(1) → 返回(1, 0)
2. fibonacci(2)：调用fibonacci(1)得到(1,0)，返回(1+0, 1) → (1, 1)（对应fib(2)=1，fib(1)=1）
3. fibonacci(3)：调用fibonacci(2)得到(1,1)，返回(1+1, 1) → (2, 1)（对应fib(3)=2，fib(2)=1）
4. fibonacci(4)：调用fibonacci(3)得到(2,1)，返回(2+1, 2) → (3, 2)（对应fib(4)=3，fib(3)=2）
5. fibonacci(5)：调用fibonacci(4)得到(3,2)，返回(3+2, 3) → (5, 3)

所以你运行print(fibonacci(5))会输出(5,3)，其中第一个值就是第5个斐波那契数（无论从fib(0)还是fib(1)开始计数，结果都是5）。

为什么这个算法更高效？ #

常规的递归斐波那契实现（def fib(n): return n if n<=1 else fib(n-1)+fib(n-2)）会重复计算大量子问题，时间复杂度是O(2^n)。而这个算法通过返回一对值，每一步只递归一次，时间复杂度是O(n)，和迭代法的效率一样，非常巧妙！

内容的提问来源于stack exchange，提问作者user9797560