Problem Statement
Which data structure is used for implementing recursion?
Explanation
A stack is used to implement recursion because function calls follow the Last In First Out principle. When a function calls itself recursively, each call is pushed onto the call stack.
When a recursive function returns, the most recent call is popped from the stack first. This is why stack overflow errors occur when recursion depth is too large, as the call stack runs out of memory. The stack maintains the execution context, local variables, and return addresses for each recursive call.
Code Solution
SolutionRead Only
// Recursive function - uses stack internally
int factorial(int n) {
if (n <= 1) return 1; // Base case
return n * factorial(n - 1); // Recursive call pushed to stack
}
// Call stack visualization:
// factorial(5)
// factorial(4)
// factorial(3)
// factorial(2)
// factorial(1) -> returns 1
// returns 2
// returns 6
// returns 24
// returns 120