Past exam question: 2077 Chaitra (Regular), Q4
Open in the Padhaiko appQuestion
Illustrate the use of stack in recursion taking any recursive program of your choice.
Solution
Role of the System Stack in Recursion: Every recursive call pauses the caller and pushes an activation record (stack frame) onto the call stack containing its parameters, local variables, and return address. Once the base case returns, frames are popped in LIFO order to finish suspended computations.
Example Program: Recursive Sum of First Natural Numbers:
int sumN(int n) {
if (n == 1) return 1; // Base case
return n + sumN(n - 1); // Recursive call
}
Let us trace sumN(4):
- Winding (Pushing stack frames):
sumN(4)pushes frame[n=4, ret->main], callssumN(3).sumN(3)pushes frame[n=3, ret->sumN(4)], callssumN(2).sumN(2)pushes frame[n=2, ret->sumN(3)], callssumN(1).sumN(1)pushes frame[n=1, ret->sumN(2)], hits base case and returns1.
- Unwinding (Popping stack frames):
- Pop
sumN(1)sumN(2)computes . - Pop
sumN(2)sumN(3)computes . - Pop
sumN(3)sumN(4)computes and returns10tomain.
- Pop
Answer:
Recursion uses the LIFO call stack to preserve each pending call's parameter and return address during the winding phase until the base case triggers unwinding. In sumN(4), four frames stack down to sumN(1) = 1, then pop back to yield .