斐波那契类递归函数recurC的时间复杂度T(n)如何推导？

首先给出原Java函数：

public static int recurC(int n) {
   if(n==1)
      return 1;
   return n + recurC(n-1) + recurC(n-2);
}

递推关系确认 #

你当前整理的递推式是正确的：

T(n) = C + T(n-1) + T(n-2)
其中：

• C 是常数耗时，对应单次函数调用内非递归操作的开销（条件判断、数值加法、返回操作等，耗时与n无关）
• 边界条件：T(0) = O(1)、T(1) = O(1)，输入小于等于1时直接返回，没有额外递归调用

递推式求解步骤 #

1. 结构匹配 #

该递推式和斐波那契数列的递推结构完全一致，仅多了一个可被吸收的常数项C，我们可以先忽略常数项得到核心递推关系：T(n) ≈ T(n-1) + T(n-2)

2. 增长阶推导 #

斐波那契数列的增长速度为指数级，底数是黄金分割比 φ = (1+√5)/2 ≈ 1.618，我们可以用代入法严格验证上界：
假设存在足够大的常数k，使得 T(n) ≤ k * φⁿ - C，代入递推式可得：

T(n) = C + T(n-1) + T(n-2)
≤ C + (k*φⁿ⁻¹ - C) + (k*φⁿ⁻² - C)
= k*φⁿ⁻²*(φ + 1) - C

由于φ满足数学性质 φ² = φ + 1，因此上式可化简为 k*φⁿ - C，和我们的假设完全匹配，上界成立。

3. 最终结论 #

该递归函数的时间复杂度为 O(φⁿ)，属于指数级复杂度。如果需要更宽松的通用上界表述，也可以写作 O(2ⁿ)。 #

调用关系辅助理解 #

你可以把整个递归过程展开为一棵递归树：每个非叶子节点都会分裂出2个子节点，分别对应recurC(n-1)和recurC(n-2)的调用，树的深度为n，总节点数的增长速度和斐波那契数列第n项的大小完全对应，也能直观对应推导得到的指数级复杂度。

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