Past exam question: 2075 Baisakh (Back), Q5
Open in the Padhaiko appHow 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)):
fact(3)pushes[n=3, pending: 3 * fact(2)].fact(2)pushes[n=2, pending: 2 * fact(1)].fact(1)pushes[n=1], hits base case, returns1.- Stack pops
fact(2); popsfact(3).
Normal (Iterative) Function vs. Recursive Function:
| Aspect | Normal (Non-Recursive) Function | Recursive Function |
|---|---|---|
| Invocation | Called once by another function; repeats work via loops | Calls itself directly or indirectly until a base case |
| Termination | Controlled by loop conditions | Controlled by base-case condition (else infinite recursion) |
| Stack Usage | Single stack frame ( call overhead) | One stack frame per active depth ( space) |
| Speed & Overhead | Faster, zero recursive call overhead | Slower per step due to frame push/pop overhead |
| Code Clarity | Longer for tree/divide-and-conquer problems | Concise and natural for trees, TOH, DFS, divide-and-conquer |
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).