Using auxiliary space for recursive functions in C program?

Here we will see how recursive function calls require auxiliary space. How is it different from a normal function call?

Suppose we have a function as shown below -

long fact(int n){
   if(n == 0 || n == 1)
      return 1;
   return n * fact(n-1);
}

This function is a recursive function. When we call it like fact(5), it will store the address inside the stack as shown below -

fact(5) --->
fact(4) --->
fact(3) --->
fact(2) --->
fact(1)

As the recursive function calls itself again and again, the address is added to the stack. Therefore, if the function is called recursively n times, it will occupy O(n) auxiliary space. But this does not mean that if a normal function is called n times, the space complexity will be O(n). For normal functions, the address is pushed onto the stack when called. Once completed, the address is popped off the stack and entered into the caller function. Then call again. So its complexity is O(1).

The above is the detailed content of Using auxiliary space for recursive functions in C program?. For more information, please follow other related articles on the PHP Chinese website!