DSA Tutorial
🔍
How Recursion Works
The Execution Model
When a recursive function runs, the computer executes it the same way it executes any function call — by creating a stack frame (a block of memory) to hold that call's state. The difference with recursion is that multiple frames for the same function co-exist simultaneously on the call stack.
When factorial(3) runs: CALL STACK at deepest point: ┌─────────────────────┐ ← top (most recent) │ factorial(0) │ n=0 → will return 1 ├─────────────────────┤ │ factorial(1) │ n=1 → waiting for factorial(0) ├─────────────────────┤ │ factorial(2) │ n=2 → waiting for factorial(1) ├─────────────────────┤ │ factorial(3) │ n=3 → waiting for factorial(2) ├─────────────────────┤ │ main() │ → waiting for factorial(3) └─────────────────────┘ ← bottom (first called) Each frame is independent — its own copy of n, its own return address.
Step 1: Building the Call Stack (Going Down)
Trace factorial(3) from the first call to the deepest point:
CALL: factorial(3) n=3 ≠ 0 → need factorial(2) → PAUSE, call factorial(2) CALL: factorial(2) n=2 ≠ 0 → need factorial(1) → PAUSE, call factorial(1) CALL: factorial(1) n=1 ≠ 0 → need factorial(0) → PAUSE, call factorial(0) CALL: factorial(0) n=0 == 0 → BASE CASE → return 1 immediately (no further call) ↑ Stack stops growing here. Maximum depth reached: 4 frames.
Java
1public class FactorialTrace {
2
3 public static long factorial(int n) {
4 System.out.println("Entering factorial(" + n + ")");
5
6 if (n == 0) {
7 System.out.println(" Base case! factorial(0) = 1");
8 return 1;
9 }
10
11 System.out.println(" factorial(" + n + ") is waiting for factorial(" + (n-1) + ")");
12 long result = n * factorial(n - 1);
13
14 System.out.println(" factorial(" + n + ") got " + (result/n) +
15 " from factorial(" + (n-1) + "), returns " + result);
16 return result;
17 }
18
19 public static void main(String[] args) {
20 System.out.println("=== Computing factorial(3) ===");
21 long answer = factorial(3);
22 System.out.println("Final answer: " + answer);
23 }
24}Output:
=== Computing factorial(3) ===
Entering factorial(3)
factorial(3) waiting for factorial(2)
Entering factorial(2)
factorial(2) waiting for factorial(1)
Entering factorial(1)
factorial(1) waiting for factorial(0)
Entering factorial(0)
Base case! factorial(0) = 1
factorial(1) got 1 from factorial(0), returns 1
factorial(2) got 1 from factorial(1), returns 2
factorial(3) got 2 from factorial(2), returns 6
Final answer: 6
Step 2: Unwinding the Call Stack (Coming Back Up)
Once the base case returns, each waiting frame resumes and completes:
RETURN SEQUENCE: factorial(0) → returns 1 to factorial(1) factorial(1): pending work was "1 × ?" Now gets the "?" = 1 Computes 1 × 1 = 1 → returns 1 to factorial(2) factorial(2): pending work was "2 × ?" Now gets the "?" = 1 Computes 2 × 1 = 2 → returns 2 to factorial(3) factorial(3): pending work was "3 × ?" Now gets the "?" = 2 Computes 3 × 2 = 6 → returns 6 to main() STACK EVOLUTION (left = bottom, right = top): Max depth: [main | f(3) | f(2) | f(1) | f(0)] f(0) returns 1 After f(0) pops: [main | f(3) | f(2) | f(1) ] f(1) computes 1×1, returns 1 After f(1) pops: [main | f(3) | f(2) ] f(2) computes 2×1, returns 2 After f(2) pops: [main | f(3) ] f(3) computes 3×2, returns 6 After f(3) pops: [main ] main() has the final answer: 6
Each Frame Is Independent
The key insight about the call stack: every recursive call gets its own frame with its own copy of every parameter and local variable. They do not share.
Java
1public class FrameIndependence {
2
3 // Each call has its own: n, result, and any local variables
4 public static int countdown(int n) {
5 // This n belongs ONLY to this frame
6 int doubled = n * 2; // This local variable belongs ONLY to this frame
7
8 System.out.printf("Frame for n=%d: n=%d, doubled=%d%n", n, n, doubled);
9
10 if (n == 0) return 0;
11
12 int subResult = countdown(n - 1); // Completely separate frame runs here
13 // When we return here, n and doubled are UNCHANGED — they were preserved
14
15 System.out.printf("Back in frame n=%d: n still=%d, doubled still=%d%n",
16 n, n, doubled);
17 return n + subResult;
18 }
19
20 public static void main(String[] args) {
21 int result = countdown(3);
22 System.out.println("Sum 0+1+2+3 = " + result);
23 }
24}Output:
Frame for n=3: n=3, doubled=6
Frame for n=2: n=2, doubled=4
Frame for n=1: n=1, doubled=2
Frame for n=0: n=0, doubled=0
Back in frame n=1: n still=1, doubled still=2
Back in frame n=2: n still=2, doubled still=4
Back in frame n=3: n still=3, doubled still=6
Sum 0+1+2+3 = 6
Pending Operations — What Waits in the Frame
When a recursive call is made, the calling frame pauses with pending work saved in its frame. This pending work is completed only after the recursive call returns.
factorial(4) calls factorial(3):
factorial(4)'s frame state while waiting:
┌─────────────────────────────────┐
│ factorial(4) │
│ n = 4 │
│ pending: 4 × ??? (return val) │
│ return address: line X │
└─────────────────────────────────┘
↓ called factorial(3)
After factorial(3) returns 6:
┌─────────────────────────────────┐
│ factorial(4) │
│ n = 4 │
│ result = 4 × 6 = 24 │ ← pending work resolved
│ → return 24 │
└─────────────────────────────────┘
The frame stores the "hole" (???) that will be filled
when the recursive call returns. This is what "pending work" means.
Two Recursive Calls: Execution Order
When a function makes TWO recursive calls, the calls run one at a time — left first, then right. The second call does not start until the first is completely done.
Java
1public class FibonacciTrace {
2
3 public static int fib(int n, int depth) {
4 String indent = " ".repeat(depth);
5 System.out.println(indent + "fib(" + n + ") called");
6
7 if (n <= 1) {
8 System.out.println(indent + "fib(" + n + ") = " + n + " [base case]");
9 return n;
10 }
11
12 System.out.println(indent + "fib(" + n + ") → calling fib(" + (n-1) + ") first");
13 int left = fib(n - 1, depth + 1); // Left branch runs COMPLETELY first
14
15 System.out.println(indent + "fib(" + n + ") → now calling fib(" + (n-2) + ")");
16 int right = fib(n - 2, depth + 1); // Right branch runs AFTER left is done
17
18 int result = left + right;
19 System.out.println(indent + "fib(" + n + ") = " + left + " + " + right + " = " + result);
20 return result;
21 }
22
23 public static void main(String[] args) {
24 System.out.println("fib(4) = " + fib(4, 0));
25 }
26}Output:
fib(4) called
fib(4) → calling fib(3) first
fib(3) called
fib(3) → calling fib(2) first
fib(2) called
fib(2) → calling fib(1) first
fib(1) = 1 [base case]
fib(2) → now calling fib(0)
fib(0) = 0 [base case]
fib(2) = 1 + 0 = 1
fib(3) → now calling fib(1)
fib(1) = 1 [base case]
fib(3) = 1 + 1 = 2
fib(4) → now calling fib(2)
fib(2) called
fib(2) → calling fib(1) first
fib(1) = 1 [base case]
fib(2) → now calling fib(0)
fib(0) = 0 [base case]
fib(2) = 1 + 0 = 1
fib(4) = 2 + 1 = 3
fib(4) = 3
How Return Values Travel Back Up
Return values do not jump to the original caller — they travel one frame at a time:
fib(4) execution return chain: fib(1) → returns 1 to fib(2) fib(0) → returns 0 to fib(2) fib(2) computes 1+0=1 → returns 1 to fib(3) [first branch] fib(1) → returns 1 to fib(3) fib(3) computes 1+1=2 → returns 2 to fib(4) [first branch of fib(4)] fib(1) → returns 1 to fib(2) [right branch of fib(4)] fib(0) → returns 0 to fib(2) fib(2) computes 1+0=1 → returns 1 to fib(4) fib(4) computes 2+1=3 → returns 3 to main() KEY POINT: Every frame only communicates with its IMMEDIATE caller. fib(1) does not know about fib(4). fib(4) does not receive fib(1)'s result directly. Results propagate upward one hop at a time.
What a Stack Frame Contains
Understanding what is stored in each frame explains why frames are independent:
Stack frame for factorial(n): ┌──────────────────────────────┐ │ PARAMETER: n │ ← copy of the argument passed in │ LOCAL VARS: result, temp... │ ← any variables declared in the function │ RETURN ADDRESS │ ← where to resume in the CALLER after return │ RETURN VALUE slot │ ← where the returned value will be stored └──────────────────────────────┘ For factorial(3), the frames on the stack simultaneously: factorial(3): n=3, return_addr=main line 5 factorial(2): n=2, return_addr=factorial line 7 factorial(1): n=1, return_addr=factorial line 7 factorial(0): n=0, return_addr=factorial line 7 ← top (currently executing) Each n is completely separate. Changing n in one frame has absolutely zero effect on n in any other frame.
Visualising the Full Stack Lifecycle
Step-by-step stack for factorial(3): Step 1: main() calls factorial(3) Stack: [main] [f(3) n=3] Step 2: f(3) calls factorial(2) Stack: [main] [f(3) n=3] [f(2) n=2] Step 3: f(2) calls factorial(1) Stack: [main] [f(3) n=3] [f(2) n=2] [f(1) n=1] Step 4: f(1) calls factorial(0) Stack: [main] [f(3) n=3] [f(2) n=2] [f(1) n=1] [f(0) n=0] ← MAXIMUM DEPTH: 5 frames (including main) Step 5: f(0) hits base case, returns 1 Stack: [main] [f(3) n=3] [f(2) n=2] [f(1) n=1] ← f(0) popped f(1) receives 1, computes 1×1=1 Step 6: f(1) returns 1 Stack: [main] [f(3) n=3] [f(2) n=2] ← f(1) popped f(2) receives 1, computes 2×1=2 Step 7: f(2) returns 2 Stack: [main] [f(3) n=3] ← f(2) popped f(3) receives 2, computes 3×2=6 Step 8: f(3) returns 6 Stack: [main] ← f(3) popped main() receives 6 — done! Total stack operations: 5 pushes + 5 pops = 10 operations
How Parameters Are Passed
Parameters are passed by value in most contexts — the recursive call gets a copy of the argument. Modifying the parameter in the recursive call does not affect the caller's copy.
def countdown(n):
if n == 0: return
n -= 1 ← modifies THIS frame's copy of n only
countdown(n) ← passes the modified value to the next frame
# n is still the modified value here, but has no effect on callers
Correct way to reduce: pass n-1 as argument
countdown(n - 1) ← creates a new value n-1, passes it to next frame
n in THIS frame is unchanged
Java
1public class ParameterPassing {
2
3 // Correct: pass n-1 as argument
4 public static void correctCountdown(int n) {
5 System.out.println("n=" + n);
6 if (n == 0) return;
7 correctCountdown(n - 1); // This frame's n is unchanged after the call
8 System.out.println("After call, n=" + n + " (unchanged)");
9 }
10
11 // Illustrating independence
12 public static int withLocal(int n) {
13 int doubled = n * 2; // Local to this frame
14 if (n == 0) return 0;
15 int sub = withLocal(n - 1);
16 // doubled is still n*2 — the recursive call did not touch it
17 System.out.println("n=" + n + " doubled=" + doubled + " sub=" + sub);
18 return doubled + sub;
19 }
20
21 public static void main(String[] args) {
22 correctCountdown(3);
23 System.out.println("---");
24 System.out.println(withLocal(3));
25 }
26}Output:
n=3
n=2
n=1
n=0
After call, n=1 (unchanged)
After call, n=2 (unchanged)
After call, n=3 (unchanged)
---
n=1 doubled=2 sub=0
n=2 doubled=4 sub=2
n=3 doubled=6 sub=6
12
Dry Run: Binary Search Recursion
Tracing binarySearch(arr, 7) on arr=[1,3,5,7,9,11,13]:
arr = [1, 3, 5, 7, 9, 11, 13] target = 7
0 1 2 3 4 5 6
CALL: search(lo=0, hi=6)
mid=3, arr[3]=7 == target → return 3 immediately
↑ found in the FIRST call — no further recursion needed
Now with target = 11:
CALL: search(lo=0, hi=6)
mid=3, arr[3]=7 < 11 → search right half
CALL: search(lo=4, hi=6)
mid=5, arr[5]=11 == target → return 5
← returns 5 to first call → first call returns 5
Stack trace:
[main] [search(0,6)] → search(4,6) called
[main] [search(0,6)] [search(4,6)] → arr[5]=11 found, return 5
[main] [search(0,6)] → receives 5, returns 5
[main] → answer: index 5 = value 11 ✓
Java
1public class BinarySearchTrace {
2
3 public static int search(int[] arr, int target, int lo, int hi, int depth) {
4 String pad = " ".repeat(depth);
5 System.out.println(pad + "search(lo=" + lo + ", hi=" + hi + ")");
6
7 if (lo > hi) {
8 System.out.println(pad + " lo > hi → not found, return -1");
9 return -1;
10 }
11
12 int mid = lo + (hi - lo) / 2;
13 System.out.println(pad + " mid=" + mid + " arr[mid]=" + arr[mid]);
14
15 if (arr[mid] == target) {
16 System.out.println(pad + " FOUND at index " + mid);
17 return mid;
18 } else if (arr[mid] < target) {
19 System.out.println(pad + " arr[mid] < target → search right half");
20 return search(arr, target, mid + 1, hi, depth + 1);
21 } else {
22 System.out.println(pad + " arr[mid] > target → search left half");
23 return search(arr, target, lo, mid - 1, depth + 1);
24 }
25 }
26
27 public static void main(String[] args) {
28 int[] arr = {1, 3, 5, 7, 9, 11, 13};
29 System.out.println("Searching for 11:");
30 int idx = search(arr, 11, 0, arr.length - 1, 0);
31 System.out.println("Found at index: " + idx);
32 }
33}Output:
Searching for 11:
search(lo=0, hi=6)
mid=3 arr[mid]=7
arr[mid] < target → search right half
search(lo=4, hi=6)
mid=5 arr[mid]=11
FOUND at index 5
Found at index: 5
The Mental Model: Trust the Recursion
When reading or writing recursive code, the most powerful technique is trusting the recursive call:
HOW TO READ ANY RECURSIVE FUNCTION:
1. Read the base case. What trivial input does it handle?
2. Read the recursive call. What smaller problem is delegated?
3. ASSUME the recursive call returns the correct answer.
Do not trace its execution — trust it.
4. Ask: given the correct answer for the smaller problem,
how does THIS function compute its own answer?
Example: reverse("hello")
Base case: reverse("") = "" ← known directly
Recursive call: reverse("ello") ← TRUST this returns "olle"
This level's computation: "olle" + 'h' = "olleh" ← final answer ✓
You did not need to trace how reverse("ello") became "olle".
You simply trusted it and used the result.
This is how recursive functions are designed and read.
Common Questions About Execution
Q: Do recursive calls run in parallel?
No. Standard recursive functions run sequentially in a single thread. fib(n-1) must complete entirely before fib(n-2) begins. The appearance of "branching" is a structural description — physically, one call at a time runs on the CPU.
Q: When does a frame get destroyed?
A stack frame is popped (destroyed) the moment its function returns. As soon as factorial(0) executes return 1, its frame is popped and factorial(1) resumes. Frames are never left "half-alive."
Q: What if a recursive function modifies a mutable data structure?
Modifications to mutable objects (arrays, lists, objects passed by reference) ARE visible to all frames and to the caller — they are not copied. Only primitive values (int, float, bool) and immutable values (strings in Java/Python) get their own copy per frame. This distinction is critical for backtracking algorithms where you must undo modifications before returning.
Summary
Recursion works through the call stack — a LIFO structure of frames:
Going down (building the stack):
- ›Each recursive call creates a new stack frame
- ›The frame stores: parameters (own copies), local variables, return address
- ›The calling frame pauses with pending work stored in its frame
- ›Frames accumulate until the base case is reached
Coming back up (unwinding the stack):
- ›The base case returns without creating another frame
- ›Each returning frame completes its pending work using the returned value
- ›Return values travel one frame at a time to the immediate caller
- ›Frames are destroyed (popped) as they return — LIFO order
Key properties:
- ›Every frame is independent — its own copy of every parameter and local variable
- ›Two recursive calls run sequentially — left branch fully completes before right starts
- ›Parameters are passed by value (primitives) or by reference (objects/arrays)
- ›Maximum simultaneous frames = recursion depth = O(n) linear or O(log n) divide-and-conquer
In the next topic, you will explore the Call Stack in detail — memory layout, frame size, stack overflow conditions, stack depth limits per language, and how tail call optimisation eliminates stack frame accumulation.
Suggested Quiz
When factorial(3) is called, in what order are the stack frames created and destroyed?
1/6