Python递归斐波那契数列：现有代码可运行但原理存疑

问题背景 #

编程练习要求：编写递归函数输出斐波那契数列第n项，函数参数为n、current_number（对应F(0)）、next_number（对应F(1)），主程序需获取用户输入并按格式输出结果，示例如下：

fibon({n},{current_number},{next_number}) = {result}
fibon(5,4,5) = 37
fibon(5,0,1) = 5
fibon(10,0,1) = 55

用户写出的代码：

def fibon(n, current_number, next_number):
    #print(f'n is {n} from the outset')
    if n == 0:
        #print('n == 0 is true')
        return current_number
    elif n == 1:
        #print('n == 1 is true')
        return next_number
    else:
        n = n-1    
        #print(f'this is n-1 {fibon(n-1, current_number, next_number)}')
        #print(f'this is n {fibon(n, current_number, next_number)}')
        fib= fibon(n-1, current_number, next_number) + fibon(n, current_number, next_number)
        #print(fib)
        return(fib)

用户的困惑：无法理解该递归函数如何返回第n项，不清楚递归时的数值传递逻辑，疑惑非0、1位置的数值如何通过fibon(n-1,...) + fibon(n,...)得到。

现有代码的逻辑解析 #

你的代码本质是标准递归斐波那契的变形，但存在逻辑冗余和效率问题：

1. 递归终止条件：当n=0返回F(0)，n=1返回F(1)，这完全符合斐波那契数列的初始定义。
2. 递归过程的实际逻辑：
   • 你在else块里先将n减1，随后调用fibon(n-1,...)和fibon(n,...)——这里的n已经是原n-1，所以实际是调用了fibon(原n-2,...)和fibon(原n-1,...)，两者相加恰好符合斐波那契数列的核心定义：F(n) = F(n-1) + F(n-2)。
   • 非0、1位置的数值是通过逐层递归拆解得到的：比如计算fibon(2,0,1)时，会拆解为fibon(1,0,1) + fibon(0,0,1)，也就是1+0=1；计算fibon(3,0,1)时拆解为fibon(2,0,1)+fibon(1,0,1)=1+1=2，以此类推，最终通过终止条件的基础数值累加得到目标结果。
3. 核心问题：这种写法会触发大量重复递归调用，比如计算fibon(5,0,1)时，fibon(3,0,1)、fibon(2,0,1)等会被重复计算多次，时间复杂度达O(2ⁿ)，效率极低。

更优的递归实现方案 #

题目要求参数包含current_number（F(0)）和next_number（F(1)），最适配的高效写法是尾递归——递归调用位于函数最后，无需额外计算，利用参数传递保存当前和下一个数值，避免重复计算，时间复杂度O(n)，空间复杂度O(n)（若编译器支持尾递归优化则为O(1)）：

def fibon(n, current_number, next_number):
    if n == 0:
        return current_number
    # 递归推进：将next作为下一轮的current，current+next作为下一轮的next，n减1
    return fibon(n - 1, next_number, current_number + next_number)

逻辑说明 #

• 初始调用时，current_number是F(0)，next_number是F(1)
• 每递归一次，我们就向目标项推进一位：比如计算F(n)时，递归到F(n-1)，此时current更新为原来的next（即F(1)→F(1)，F(1)→F(2)，以此类推），next更新为原来的current+next（即F(0)+F(1)=F(2)，F(1)+F(2)=F(3)）
• 当n减到0时，current_number就是我们要的F(n)

以示例fibon(5,4,5)为例，递归流程如下：

• n=5 → 调用fibon(4,5,4+5=9)
• n=4 → 调用fibon(3,9,5+9=14)
• n=3 → 调用fibon(2,14,9+14=23)
• n=2 → 调用fibon(1,23,14+23=37)
• n=1 → 调用fibon(0,37,23+37=60)
• n=0 → 返回37，与示例结果一致

配套主程序实现 #

结合用户输入要求的主程序代码：

# 获取用户输入参数
n = int(input("请输入n: "))
current = int(input("请输入current_number(F(0)): "))
next_num = int(input("请输入next_number(F(1)): "))

# 计算并按格式输出结果
result = fibon(n, current, next_num)
print(f"fibon({n},{current},{next_num}) = {result}")

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