Recursion: The function calling itself is called recursion.
Stack: A stack is a data structure in which elements are inserted and deleted only at one end called the top of the stack. It follows the LIFO (Last In First Out) mechanism.
Recursive Stack Size:
When a recursive function is invoked, its parameters are stored in a data structure called activation records. Every time the recursive function is invoked, a new activation record is generated and stored in the memory. These activation records are stored in the special stack called the recursive stack. These activation records are deleted when the function execution is completed.
So, when a recursive function is invoked, it generates the activation records for different values of the recursive function hence, extending the recursion stack size. When the recursive function execution is completed one by one its activation records get deleted hence, contracting the recursive stack size. The recursive stack size depends on the number of activation records created and deleted.
Example:
C++
#include <bits/stdc++.h>using namespace std; int fact(int n){ if (n == 1) return 1; return fact(n - 1);}int main(){ int p; p = fact(2); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { static int fact(int n) { if (n == 1) return 1; return fact(n - 1); } public static void main (String[] args) { int p; p = fact(2); }}// This code is contributed by aadityaburujwale. |
Python3
def fact(n): if n == 1: return 1 return fact(n - 1)def main(): p = fact(2)if __name__ == "__main__": main()# This code is contributed by akashish__ |
C#
using System;public class GFG { public static int fact(int n) { if (n == 1) return 1; return fact(n - 1); } static public void Main() { int p; p = fact(2); }}// This code is contributed by akashish__ |
Javascript
function fact(n){ if (n == 1) return 1; return fact(n - 1);}let p;p = fact(2);// This code is contributed by akashish__ |
Time complexity: O(n)
Auxiliary space: O(n) // because we are using stack.
Illustration:
For the above program. Firstly, the activation record for main stack is generated and stored in the stack.
Initial state
In the above program, there is a recursive function fact that has n as the local parameter. In the above example program, n=2 is passed in the recursive function call.
First Step: First, the function is invoked for n =2 and its activation record are created in the recursive stack.
1st step
2nd Step: Then according to the recursive function, it is invoked for n=1 and its activation record is created in the recursive stack.
2nd step
3rd Step: After the execution of the function for value n=1 as it is a base condition, its execution gets completed and its activation record gets deleted.
3rd step
4th step: Similarly, the function for value n=2(its previous function) gets executed and its activation record gets deleted. It comes out from the recursive function to the main function.
4th step
So, in the above example for recursive function fact and value, n=2 recursive stack size excluding the main function is 2. Hence, for value n recursive stack size is n.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
