Does the presence of static variables change the time complexity of a recursive function? If so how does it do so, and if no, explain the below code

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);
}

Trying to find the Taylor series of e^x using recursion (involving static variables) Now, when we count the number of multiplications here, then mathematically we count it by writing the series and adding the total number of multiplications involved, which gives a total of n(n+1)/2 multiplications, i.e. O(n^2) multiplications and so is the time complexity

But if I try to count the number of multiplications by tracing this recursion, then I get 2*n - 1 multiplications, i.e. O(n) multiplications only,

So, now I'm starting to think that this happened because of the static variables. If I'm wrong by any means, then please explain me step by step to find the time complexity of this recursive function by tracing its recursion tree.

Answer 1

To say the result, there's nothing related with the static values. And your mathematically counting is wrong.

I have tried your code with python. This is the code what I have tried.

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)

And I get this result.

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

As you see the result, the recursion is just called for n+1 times. The recursion tree is simple: It calls the params as (x, n-1), (x,n-2), ... (x,0). And at each call, the multiplications are not done n times. It is just done 2 times. So total count is 2*n times. Your mistake was that in every call the multiplication is done for n times (n - given parameter, not original n).

Answer 2

I see O(N) time and some mistakes for example:

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

should probably be:

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

or just:

int r = e(1, 4);

first for taylor I would expect the x to be floating point type (and all derived variables/stuff from it too) otherwise you got rounding to integer invalidating result...

Your e function does not init static variables so you can not use it more than once...

To remedy your code (putting all together) I would:

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

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

well I would not use recursion for this at all really instead simple iteration loop would be much faster and clear see:

• taylor sin approximate C++ template
• taylor sin approximate C++