展开递归项会改变时间复杂度吗？两类递归式复杂度疑问

嘿，这个问题抓得特别准——其实核心点在于数学表达式等价，但算法的实际执行路径完全不同，咱们掰开揉碎了说：

首先得明确：从纯数学角度，f(n) = 2f(n-1)和f(n) = f(n-1) + f(n-1)是完全等价的，但时间复杂度是衡量代码实际执行的步骤数/调用次数，不是看数学公式，所以这两种写法的复杂度差异真实存在。

第一种情况：f(n) = 2 * f(n-1)的线性复杂度 #

如果你的代码实现是先计算一次f(n-1)，再乘以2返回，那递归调用链是线性的：

function f(n):
    if n == 0:
        return 1  # 假设基础 case 为1
    sub_result = f(n-1)
    return 2 * sub_result

这里每一层的f(n)只会触发1次f(n-1)调用，从n到0总共就n次递归调用，时间复杂度是O(n)。

第二种情况：f(n) = f(n-1) + f(n-1)的指数复杂度 #

如果直接按这个表达式写递归，问题就来了：每次计算f(n)时，会独立触发两次f(n-1)调用，而且这两次调用是完全分开的，不会共享结果：

function f(n):
    if n == 0:
        return 1
    return f(n-1) + f(n-1)

这时候递归会展开成一棵二叉树：计算f(n)需要算f(n-1)两次，每个f(n-1)又需要算f(n-2)两次，以此类推。总调用次数是2^0 + 2^1 + ... + 2^n = 2^(n+1)-1，时间复杂度是O(2^n)，比前者高得多。

关键补充：记忆化能抹平差异 #

如果给第二种写法加个缓存（记忆化），把已经计算过的f(k)结果存起来，那第二次调用f(n-1)时直接取缓存，不用再递归，这时候时间复杂度也会降到O(n)，和第一种写法完全一致。但如果是无缓存的原生递归，后者的复杂度确实远高于前者。

所以你之前看到的说法是完全正确的——差异本质是是否重复计算了相同的子问题，而非数学公式的不同。

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