斐波那契数列尾递归实现的设计思路及推导逻辑

首先给出你提到的实现代码：

def fib(n, a=0, b=1):
    return fib(n-1, b, a+b) if n > 0 else a

推导核心逻辑 #

尾递归的本质是把迭代过程的所有状态全部放到递归参数里传递，不需要回溯计算上一层的结果，完全可以从迭代版的斐波那契反过来推导得到。

第一步：对应迭代版逻辑 #

常规迭代版斐波那契实现如下：

def fib_iter(n):
    a, b = 0, 1
    # 每循环一次，向前递推一个斐波那契数
    for _ in range(n):
        a, b = b, a + b
    return a

对比两段代码可以直接看到对应关系：

• 迭代的循环次数n，对应尾递归的入参n
• 迭代每次循环的更新逻辑a, b = b, a+b，对应尾递归调用时的参数更新fib(n-1, b, a+b)
• 迭代循环结束后返回a，对应尾递归n=0时返回a

第二步：明确参数的含义 #

尾递归的两个默认参数a、b有明确的定义：

• 当调用fib(k, a, b)时，a就是第m个斐波那契数，b是第m+1个斐波那契数，剩余k次递推就能得到第m+k个斐波那契数
  初始调用fib(n)时，默认参数a=0、b=1，对应m=0，即a=fib(0)=0，b=fib(1)=1，剩余n次递推就能得到fib(0+n)=fib(n)，完全符合需求。

第三步：逐步骤验证过程 #

以计算fib(3)为例，完整执行过程如下：

最终返回结果2，和fib(3)的实际值一致。 #

补充说明 #

你提到的Python不支持尾调用优化是对的，所以Python里这段代码在n过大时还是会栈溢出，但这套尾递归的推导思路在支持TCO的语言（比如Scheme、Haskell）中可以实现和迭代完全一致的O(1)空间复杂度，不会出现栈溢出问题。 #

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