求斐波那契数列Top-Down解法的T(n)递推关系及验证

1. 调用次数T(n)的递推关系及初始条件 #

代码逻辑分析 #

带记忆化的自顶向下解法通过memo数组缓存已计算的斐波那契值，避免重复递归计算。每次进入FibHelper函数时，全局变量totalCalls都会加1，因此调用次数是所有进入FibHelper函数的次数总和。

递推关系与初始条件 #

结合给定的调用次数数据（T(3)=5、T(4)=7、T(5)=9...）及代码执行流程：

• 初始条件：
  • T(0) = 1（仅调用FibHelper(0)1次）
  • T(1) = 1（仅调用FibHelper(1)1次）
• 递推关系：当n ≥ 2时，T(n) = T(n-1) + 2
  解释：计算F(n)时，首先调用FibHelper(n)（+1次），随后触发FibHelper(n-1)的完整调用流程（对应T(n-1)次调用），最后调用FibHelper(n-2)时，该值已被缓存，仅需1次调用。总增量为2次，因此递推关系为T(n) = T(n-1) + 2。

数值验证：

• T(2) = T(1) + 2 = 1+2=3（符合实际执行结果）
• T(3) = T(2)+2=3+2=5（与给定数据一致）
• T(4)=T(3)+2=5+2=7（与给定数据一致）

2. 验证公式T(n)=2F(n+1)-1是否成立 #

公式背景说明 #

该公式是无记忆化递归斐波那契解法的调用次数公式，例如无记忆化时T(5)=15，2F(6)-1=2*8-1=15，完全符合。但带记忆化的解法通过缓存避免了大量重复调用，调用次数增长模式完全不同，我们通过给定数据验证：

显然，带记忆化的自顶向下解法调用次数不满足T(n)=2F(n+1)-1的公式，其调用次数呈线性增长，而非无记忆化解法的指数增长。

相关代码 #

带记忆化的自顶向下解法代码

totalCalls = 0

def FibHelper(n, memo):
   global totalCalls
   totalCalls+=1 
   if memo[n] == -1:
       if n < 2: 
           memo[n] = n
       else:
           left = FibHelper(n-1, memo)
           right = FibHelper(n-2, memo)
           memo[n] = left + right
   return memo[n]

def Fib(n):
   global totalCalls
   totalCalls = 0
   print("The fibonacci number of (%d) is: %d" % (n, FibHelper(n, [-1] * (n+1))))
   print("The total number of calls in TD is: ",totalCalls)

无记忆化递归解法代码

totalCalls = 0

def F(n):
    global totalCalls
    totalCalls+=1    
    if n <= 1: 
        return n
    else:
        return F(n-1) + F(n-2)

def FStart(n):
    global totalCalls
    totalCalls = 0
    print("The fibonacci number of (%d) is: %d" % (n, F(n)))
    print("The total number of calls is: ",totalCalls)

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