PadhaikoAll subjects

Past exam question: 2073 Bhadra (Regular), Q5

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Recursion

Question

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 Stack
Answer:

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).

All past exam questions for Data Structure and Algorithms