PadhaikoAll subjects

Past exam question: 2075 Baisakh (Back), Q5

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Recursion

Question

How recursive algorithm uses STACK to store intermediate results, illustrate with an example? Distinguish between normal function and recursive function.

Solution

How Recursion Stores Intermediate Results on the Stack: Each recursive invocation creates an activation record pushed onto the system call stack holding its argument values, local variables, and return address. Because inner calls must complete before outer calls resume, these intermediate contexts unwind in strict LIFO order.

Example (fact(3)):

  1. fact(3) pushes [n=3, pending: 3 * fact(2)].
  2. fact(2) pushes [n=2, pending: 2 * fact(1)].
  3. fact(1) pushes [n=1], hits base case, returns 1.
  4. Stack pops fact(2) ; pops fact(3) .

Normal (Iterative) Function vs. Recursive Function:

AspectNormal (Non-Recursive) FunctionRecursive Function
InvocationCalled once by another function; repeats work via loopsCalls itself directly or indirectly until a base case
TerminationControlled by loop conditionsControlled by base-case condition (else infinite recursion)
Stack UsageSingle stack frame ( call overhead)One stack frame per active depth ( space)
Speed & OverheadFaster, zero recursive call overheadSlower per step due to frame push/pop overhead
Code ClarityLonger for tree/divide-and-conquer problemsConcise and natural for trees, TOH, DFS, divide-and-conquer
Answer:

Recursive algorithms preserve each call's state and pending operations as activation records on the LIFO call stack until base cases unwind. Normal functions execute once per call with loop iteration ( stack overhead), whereas recursive functions invoke themselves down to a base case ( stack frames).

All past exam questions for Data Structure and Algorithms