Past exam question: 2073 Bhadra (Regular), Q5
Open in the Padhaiko appQuestion
Explain how a recursive algorithm uses stack with suitable illustrative stack diagram.
Solution
Call Stack Mechanism in Recursion: Each recursive call pushes an activation record (stack frame) containing its local parameters, local variables, and return address onto the runtime stack. When the base case returns, frames pop in LIFO order to resume pending work.
Illustrative Stack Diagram (fact(3) where fact(n) = n * fact(n-1)):
Winding (Pushing frames) Unwinding (Popping & returning)
| n=1, ret->fact(2) | -> returns 1 [popped] -> fact(2) = 2*1 = 2
| n=2, ret->fact(3) | [popped] -> fact(3) = 3*2 = 6
| n=3, ret->main | [popped] -> main receives 6
+-------------------+
Call StackAnswer:
Recursion uses the LIFO call stack to push a new activation record (arguments, locals, return address) for each call down to the base case, then unwinds by popping frames in reverse order to combine intermediate results (fact(3) -> 1 -> 2 -> 6).