---
title: "How recursion uses stack"
subject: "Data Structure and Algorithm"
chapter: 5
key: "semester_4/data_structure_and_algorithm:recursion-uses-stack"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/recursion-uses-stack
site: BCT Engineering
---

# How recursion uses stack

Data Structure and Algorithm · Chapter 5: Recursion

- Asked in: 2075 Baisakh, 5 marks; 2073 Bhadra, 8 marks (asked 2 times)
- Video: [Data Structures Using C++: Illustration of Recursive Function Calls (Call Stack)](https://www.youtube.com/watch?v=k0bb7UYy0pY) — ReelLearning
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/recursion-uses-stack
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-5

## Question

How does a recursive algorithm use STACK to store intermediate results? Illustrate with an example and a suitable stack diagram.

## Short answer

Each recursive call pushes an activation record with parameters and local variables onto the call stack, storing intermediate results. For factorial(3), frames for 3,2,1,0 are pushed; as the base case returns 1, each popped frame multiplies its n and returns the value, preserving partial computations.

## Answer

A recursive function calls itself. Every call creates an **activation record (stack frame)** holding the parameters, local variables and the return address. These frames are pushed on the system call stack when a function is called and popped when it returns. Because the last call to start is the first to finish (LIFO), the stack stores the pending work and intermediate results of each call.

#### Example: factorial
```c
int fact(int n) {
    if (n == 0) return 1;          /* base case */
    return n * fact(n - 1);        /* recursive case */
}
```
Calling `fact(3)`:

**Winding phase (calls, frames pushed)**
```text
 step1       step2       step3       step4
|       |   |       |   |       |   |fact(0)|
|       |   |       |   |fact(1)|   |fact(1)|
|       |   |fact(2)|   |fact(2)|   |fact(2)|
|fact(3)|   |fact(3)|   |fact(3)|   |fact(3)|
+-------+   +-------+   +-------+   +-------+
```
Each frame holds its own `n` and waits for the result of the call above it. The call `fact(0)` meets the base case and returns 1.

**Unwinding phase (returns, frames popped)**

| Frame popped | Computation | Value returned |
|---|---|---|
| fact(0) | base case | 1 |
| fact(1) | 1 × 1 | 1 |
| fact(2) | 2 × 1 | 2 |
| fact(3) | 3 × 2 | 6 |

Result: `fact(3) = 6`.

Another example is Fibonacci, where the stack holds the pending `fib(n-2)` calls while `fib(n-1)` is being computed. Maximum stack depth equals the depth of recursion (n + 1 frames for factorial), so very deep recursion may cause **stack overflow**. Without the stack the function could not remember where to resume or the partial products, which is why recursion needs a stack (and why any recursive algorithm can be made iterative by using an explicit stack).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does each recursive call push onto the system stack?
   A. An activation record with parameters, local variables and return address
   B. Only the final result
   C. Only the base case value
   D. The source code of the function
   Answer: A. Each call gets its own frame holding its parameters, locals and return address. (Key point: Activation record)

2. Why is a stack the right structure for recursive calls?
   A. The first call started is the first to finish
   B. The last call started is the first to finish (LIFO)
   C. Calls finish in random order
   D. Because arrays are faster than queues
   Answer: B. The most recent call must return first, which is last-in first-out behaviour. (Key point: LIFO order)

3. During unwinding of fact(3), what is the order of values returned?
   A. fact(3)=6 first, then fact(2), fact(1), fact(0)
   B. fact(0)=0, fact(1)=1, fact(2)=2, fact(3)=6
   C. fact(0)=1, fact(1)=1, fact(2)=2, fact(3)=6
   D. fact(1)=1, fact(2)=2, fact(3)=6, then fact(0)=1
   Answer: C. The base case fact(0) returns 1 first, then each frame multiplies and is popped: 1, 1, 2, 6. (Key point: Unwinding in fact(3))

4. How many frames are on the stack at the deepest point of fact(3), and what risk grows with depth?
   A. 3 frames; heap overflow
   B. 3 frames; underflow
   C. 6 frames; stack overflow
   D. 4 frames; stack overflow
   Answer: D. Frames for n=3,2,1,0 give n+1=4 frames. Very deep recursion can exhaust stack memory (stack overflow). (Key point: Stack depth and overflow)

## Related in Data Structure and Algorithm

- [Recursion properties, Fibonacci, TOH algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-properties-fibonacci-toh) — Data Structure and Algorithm, chapter 5
- [Recursion; iterative vs recursive choice](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adefine-recursion-iterative-vs-recursive) — Data Structure and Algorithm, chapter 5
- [Is recursion slow; recursive vs non-recursive](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-slow-compare) — Data Structure and Algorithm, chapter 5
- [TOH algorithm and recursion tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-algorithm-recursion-tree) — Data Structure and Algorithm, chapter 5, asked 2×
- [Recursion, Fibonacci and TOH](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-fibonacci-toh) — Data Structure and Algorithm, chapter 5
- [Normal vs recursive function](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Anormal-vs-recursive-function) — Data Structure and Algorithm, chapter 5

## Related in other subjects

- [Define influence line diagram and its uses](https://www.bctengineer.com/question.md?key=semester_4%2Ftheory_of_structures_i%3Adefine-ild-uses) — Theory of Structures I, chapter 5, asked 5×
- [Book store process model](https://www.bctengineer.com/question.md?key=semester_5%2Fsoftware_engineering%3Abook-store-process-model) — Software Engineering, chapter 2
- [Recursive/iterative query and DNS records](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Adns-recursive-iterative-records) — Computer Networks and Security, chapter 6
- [Single stack stepper motor principle](https://www.bctengineer.com/question.md?key=semester_4%2Felectrical_machine%3Astepper-motor-single-stack) — Electrical Machine, chapter 7