静态变量的存在会改变递归函数的时间复杂度吗？如果是的话，它是如何做到的，如果不是，请解释下面的代码

Question

int e(int x, int n)
{
  static int f=1, p=1; // f for factorial evaluation & p for power evaluation
  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(){
  // Just for example
  int n = 4;
  int x = 1;
  int r = e(1, 4);
}

尝试使用递归求e^x的泰勒级数（涉及静态变量） 现在，当我们计算这里的乘法次数时，我们在数学上计算它 通过编写级数并添加所涉及的乘法总数，得出 总共 n(n+1)/2 次乘法，即 O(n^2) 次乘法，时间复杂度也是如此

但是如果我尝试通过跟踪这个递归来计算乘法的次数，那么我会得到 2*n - 1 乘法，即仅 O(n) 次乘法，

所以，现在我开始认为这是由于静态变量而发生的。如果我错了，请一步步解释我，通过追踪递归树来找到这个递归函数的时间复杂度。

Answer 1

要说结果，与静态值没有任何关系。 而且你的数学计数是错误的。

我已经用 python 尝试过你的代码。 这是我尝试过的代码。

f = 1
p = 1
multi = 0

def e(x, n):
    global f
    global p
    global multi
    
    print('calling e', x, n)
    if n==0:
      return 1

    r = e(x, n-1)
    p = p*x
    f = f*n
    multi += 2 # there's 2 multiples
    print('multiply done', multi)
    return r + p/f

r = e(1, 4)

我得到了这个结果。

calling e 1 4
calling e 1 3
calling e 1 2
calling e 1 1
calling e 1 0
multiply done 2
multiply done 4
multiply done 6
multiply done 8

正如你所看到的结果，递归只调用了 n+1 次。 递归树很简单： 它将参数称为 (x, n-1), (x,n-2), ... (x,0)。 并且在每次调用时，乘法不会执行 n 次。只做了2次。 所以总次数是2*n次。 你的错误是，在每次调用中，乘法都会进行 n 次（n - 给定参数，而不是原始 n）。

Answer 2

我看到

O(N)

时间和一些错误......

首先对于泰勒来说，我希望

x

是浮点类型（以及所有从中派生的变量/内容）。代码

int n = 4;
int x = 1;
int r = e(1, 4);

大概应该是：

int n = 4;
int x = 1;
int r = e(x, n);

或者只是：

int r = e(1, 4);

您的

e

函数不会初始化

static

变量，因此您不能多次使用它......为了纠正您的代码，我会：

int e(float x, int n,bool init=true)
  {
  static float f,p; // f for factorial evaluation & p for power evaluation
  int r;
  if (init){ f=1.0; p=1.0; }
  if(n==0) return 1;
  else 
    {
    r = e(x, n-1,false);
    p *= x;
    f *= n;
    return r + p/f;
    }
}

void main()
  {
  // Just for example
  int n = 4;
  float x = 1;
  float r = e(x, n);
  }

好吧，我根本不会使用递归，相反，简单的迭代循环会更快、更清晰，请参阅：

• taylor sin 近似 C++ 模板
• 泰勒·辛近似C++