使用带记忆化的正向递归计算第n个斐波那契数可行吗？

问题 #

能否使用带记忆化的正向递归计算第n个斐波那契数？若可行，如何实现？若不可行，原因是什么？

背景 #

多数学习资料与书籍（如CLRS、DPV等）采用反向递归介绍动态规划（DP）：从目标出发向基准案例推进；而正向递归则是从基准案例出发向目标推进，二者核心差异在于索引推进方向、目标与基准案例的位置相反。

以经典打家劫舍问题为例，两种递归方式的实现如下：

反向递归实现 #

def rob(nums):
    def dp(house):
        if house <= 1:
            return max(nums[:house+1])
        
        if house in memo:
            return memo[house]
        
        memo[house] = max(nums[house] + dp(house - 2), dp(house - 1))
        return memo[house]
        
    memo = dict()
    return dp(len(nums) - 1)

正向递归实现 #

def rob(nums):
    def dp(house):
        if house >= n:
            return 0
        
        if house in memo:
            return memo[house]
        
        memo[house] = max(nums[house] + dp(house + 2), dp(house + 1))
        return memo[house]
        
    n = len(nums)
    memo = dict()
    return dp(0)

反向递归从最后一间房屋出发回溯到第一间；正向递归从第一间房屋出发推进到最后一间，二者是同一思路的不同表现形式。

回到斐波那契数问题，反向递归的实现十分直观：

def fib(n):
    def dp(i):
        if i < 2:
            return i
        
        if i in memo:
            return memo[i]
        
        memo[i] = dp(i - 1) + dp(i - 2)
        return memo[i]
    
    memo = dict()
    return dp(n)

但如何将正向递归思路应用到斐波那契数计算中？以下是尝试实现的代码：

def fib(n):
    def dp(i):
        if i >= n:
            return i - n
        
        if i in memo:
            return memo[i]
        
        memo[i] = dp(i + 1) + dp(i + 2)
        return memo[i]
    
    memo = dict()
    return dp(0)

这段代码能正确计算斐波那契数，但逻辑看起来反直觉（如memo[n-1] = dp(n) + dp(n+1)），需要通过dp(n)=0、dp(n+1)=1满足基准案例。疑问在于：这段代码是否是带记忆化的正向递归求解斐波那契数的合理实现？还是误解了正向递归的定义？

解答 #

结论：完全可行，你的尝试代码符合正向递归定义 #

可以使用带记忆化的正向递归计算第n个斐波那契数，你提供的尝试代码完全符合正向递归逻辑，只是通过逆向序列映射的方式实现，导致直觉上的违和感。

正向递归的核心定义 #

正向递归的核心是：从起点（基准案例对应的索引）出发，递归调用更大的索引，向目标推进，直到触发终止条件。对应到你的代码：

• 起点是i=0，目标是i=n
• 递归调用方向是i+1、i+2，逐步向目标n靠近
• 终止条件是i >=n，返回的i-n刚好对应标准斐波那契的基准值（F(0)=0、F(1)=1）

代码逻辑的本质 #

你的代码中，dp(i)等价于标准斐波那契序列的逆向映射：dp(i) = F(n - i)，其中F(k)是标准斐波那契数（F₀=0、F₁=1、Fₖ=Fₖ₋₁+Fₖ₋₂）：

• 当i=n时，dp(n)=0=F(0)
• 当i=n-1时，dp(n-1)=dp(n)+dp(n+1)=0+1=1=F(1)
• 当i=n-2时，dp(n-2)=dp(n-1)+dp(n)=1+0=1=F(2)
• ...以此类推，最终dp(0)=F(n)，正好是需要的结果

这种逆向映射完全符合正向递归“从起点向目标推进”的要求，只是因为斐波那契数的依赖关系是“前项推导后项”，而正向递归的调用方向是“后项推导前项”，所以通过逆向映射适配递归逻辑。

更符合直觉的正向递归实现 #

如果想要更贴合“从基准案例逐步推导到目标”的直觉，可以采用跟踪当前已计算项的方式实现：

def fib(n):
    memo = {0: 0, 1: 1}
    
    def forward_dp(k):
        # 若已计算到目标n，直接返回
        if k == n:
            return memo[k]
        # 计算下一个斐波那契数
        next_k = k + 1
        memo[next_k] = memo[k] + memo[k-1]
        # 递归推进到下一个索引
        return forward_dp(next_k)
    
    if n < 2:
        return n
    return forward_dp(1)

这段代码从基准案例F(0)、F(1)出发，递归计算F(2)、F(3)...直到F(n)，完全遵循“从起点向目标推进”的正向递归逻辑，且通过memo存储已计算项避免重复计算。

内容的提问来源于stack exchange，提问作者Daniel W. Farlow