静态变量是否改变递归函数时间复杂度？附泰勒级数递归代码分析

问题背景 #

你写的这个递归函数通过泰勒级数计算e^x，核心用了静态变量f（存储阶乘）和p（存储x的幂次）。按数学常规思路，计算泰勒级数的时间复杂度应该是O(n²)，但实际跟踪递归过程后，乘法次数只有2n-1，复杂度是O(n)——这个差异确实是静态变量导致的，下面用递归树分步拆解。

先贴出你的代码：

int e(int x, int n)
{
  static int f=1, p=1; // f用于计算阶乘，p用于计算幂次
  int r;

  if(n==0){
    return 1;
  }

  else {
    r = e(x, n-1);
    p = p*x;
    f = f*n;
    return r + p/f;
  }
}

void main(){
  // 示例调用
  int n = 4;
  int x = 1;
  int r = e(1, 4);
}

先搞懂：常规无静态变量的O(n²)怎么来的 #

数学上e^x的泰勒展开式是：
$$e^x = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}$$
如果不用静态变量，每次递归计算第k项$\frac{x^{k}{k!}$时，都得重新算$x}k$（要乘k次）和$k!$（也要乘k次）。把所有项的乘法次数加起来，就是$\sum_{k=1}^n 2k = n(n+1)$，时间复杂度自然是O(n²)。

带静态变量的递归树分步分析 #

以你示例里的n=4、x=1为例，递归的执行逻辑是先往深调用到基准情况（n=0），再一层一层回溯执行后续的乘法和累加。关键是静态变量f和p只会在第一次调用函数时初始化一次，回溯时直接复用之前的结果，不用重新计算。

递归树的执行全流程 #

1. 第一层（e(1,4)）：进入else分支，先调用e(1,3)
2. 第二层（e(1,3)）：进入else分支，先调用e(1,2)
3. 第三层（e(1,2)）：进入else分支，先调用e(1,1)
4. 第四层（e(1,1)）：进入else分支，先调用e(1,0)
5. 基准情况（e(1,0)）：直接返回1，此时f=1、p=1（初始化的值）

接下来开始回溯，每一层都执行两次乘法（更新p和f），再累加返回：

• 第四层回溯（e(1,1)）：执行p=1*1=1（1次乘法）、f=1*1=1（1次乘法），返回1 + 1/1 = 2
• 第三层回溯（e(1,2)）：执行p=1*1=1（1次）、f=1*2=2（1次），返回2 + 1/2 = 2.5
• 第二层回溯（e(1,3)）：执行p=1*1=1（1次）、f=2*3=6（1次），返回2.5 + 1/6 ≈ 2.6667
• 第一层回溯（e(1,4)）：执行p=1*1=1（1次）、f=6*4=24（1次），返回2.6667 + 1/24 ≈ 2.7083

乘法次数与复杂度推导 #

从上面的流程能看到，除了基准情况（n=0），每一层递归回溯时都只做2次乘法。对于输入n来说，总共有n层这样的回溯操作，总乘法次数是2n（如果把乘以1的操作也算上），即使忽略乘以1的无效操作，次数也是2n-1，整体时间复杂度是O(n)。

根本原因就是静态变量f和p的“状态保持”：计算x的k次幂时，是在k-1次幂的基础上再乘x；计算k!时，是在(k-1)!的基础上再乘k——相当于用递推的方式复用了之前的计算结果，避免了重复计算，把时间复杂度从O(n²)降到了O(n)。

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