PadhaikoAll subjects

Past exam question: 2078 Chaitra (Regular), Q5

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Recursion

Question

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

  1. Function arguments / local parameters (e.g., n).
  2. Local variables.
  3. 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:

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

  1. Winding (Pushing frames onto stack):
    • Call fact(4): push [n=4, ret -> main], wait for fact(3).
    • Call fact(3): push [n=3, ret -> fact(4)], wait for fact(2).
    • Call fact(2): push [n=2, ret -> fact(3)], wait for fact(1).
    • Call fact(1): push [n=1, ret -> fact(2)] base case hit!
  2. Unwinding (Popping frames and multiplying):
    • fact(1) returns 1 and pops its frame.
    • fact(2) resumes, computes , returns 2, pops its frame.
    • fact(3) resumes, computes , returns 6, pops its frame.
    • fact(4) resumes, computes , returns 24 to main, stack becomes empty.
Answer:

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 .

All past exam questions for Data Structure and Algorithms