Past exam question: 2078 Chaitra (Regular), Q5
Open in the Padhaiko appExplain how recursion uses stack data structures, use factorial of number calculation to illustrate the concept.
Solution
How Recursion Uses the Call Stack: Whenever a function invokes itself recursively, the runtime system pushes a new activation record (stack frame) onto the system call stack. Each stack frame stores:
- Function arguments / local parameters (e.g.,
n). - Local variables.
- The return address (the instruction in the caller where execution resumes after the call finishes).
Because the most recent recursive call must finish before its caller can resume, execution naturally obeys LIFO order:
- Winding Phase: Recursive calls push frames onto the stack until the base case is reached.
- Unwinding Phase: Once the base case returns a value, frames are popped one by one in reverse order, combining intermediate results back to the original caller.
Recursive Factorial Definition:
int fact(int n) {
if (n <= 1) return 1; // Base case
return n * fact(n - 1); // Recursive case
}
Let us trace fact(4) on the call stack.
Stack Trace for fact(4):
- Winding (Pushing frames onto stack):
- Call
fact(4): push[n=4, ret -> main], wait forfact(3). - Call
fact(3): push[n=3, ret -> fact(4)], wait forfact(2). - Call
fact(2): push[n=2, ret -> fact(3)], wait forfact(1). - Call
fact(1): push[n=1, ret -> fact(2)]base case hit!
- Call
- Unwinding (Popping frames and multiplying):
fact(1)returns1and pops its frame.fact(2)resumes, computes , returns2, pops its frame.fact(3)resumes, computes , returns6, pops its frame.fact(4)resumes, computes , returns24tomain, stack becomes empty.
Recursion relies on the runtime call stack to push an activation record (parameters, local state, return address) for each nested call until the base case is hit (winding), then pops frames in LIFO order to compute and return the final result (unwinding). For fact(4), four frames are pushed down to fact(1) = 1, then popped to yield .