PadhaikoAll subjects

Past exam question: 2077 Chaitra (Regular), Q4

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Recursion

Question

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

  1. Winding (Pushing stack frames):
    • sumN(4) pushes frame [n=4, ret->main], calls sumN(3).
    • sumN(3) pushes frame [n=3, ret->sumN(4)], calls sumN(2).
    • sumN(2) pushes frame [n=2, ret->sumN(3)], calls sumN(1).
    • sumN(1) pushes frame [n=1, ret->sumN(2)], hits base case and returns 1.
  2. Unwinding (Popping stack frames):
    • Pop sumN(1) sumN(2) computes .
    • Pop sumN(2) sumN(3) computes .
    • Pop sumN(3) sumN(4) computes and returns 10 to main.
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 .

All past exam questions for Data Structure and Algorithms