Recursion
Open in the Padhaiko app2.4 Recursion
2.4.1 Concept of recursion
Recursion
Recursion is a problem-solving and programming technique in which a function calls itself—either directly or indirectly—to solve smaller instances of the same problem until a trivial base problem is reached.
Every valid recursive function requires two essential parts:
- Base Case: A non-recursive terminating condition whose answer is known directly. Without a reachable base case, the function recurses indefinitely until the call stack overflows.
- Recursive Case: A self-call operating on a strictly smaller or simpler subproblem that converges monotonically toward the base case.
int factorial(int n) {
if (n <= 1) /* Base case: 0! = 1, 1! = 1 */
return 1;
return n * factorial(n - 1); /* Recursive case */
}Mathematically, this mirrors the recurrence relation:
2.4.2 Recursion and stack
When a program invokes a function, the CPU and runtime system allocate an activation record (stack frame) on the system call stack. Each stack frame stores:
- The function's arguments (parameters) and local variables,
- The return address (where execution resumes in the caller), and
- Any pending intermediate expression waiting for the callee's return value.
Because the most recently invoked recursive call must finish and return first before its caller can resume, function calls strictly follow LIFO order—making the stack the exact data structure required to execute recursion.
Top -> +-----------------------------+
| factorial(1): returns 1 | <-- Base case reached
+-----------------------------+
| factorial(2): 2 * [pending] | <-- Waits for factorial(1)
+-----------------------------+
| factorial(3): 3 * [pending] | <-- Waits for factorial(2)
+-----------------------------+
| main() |
+-----------------------------+If recursion depth exceeds the fixed call-stack limit (for example, due to a missing base case or nested calls), the program terminates with a Stack Overflow.
2.4.3 Recursion vs iteration
Both recursion and iteration (for, while, do-while loops) repeat computations, yet they trade memory and call overhead against structural clarity.
int factorial_iter(int n) {
int result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}| Aspect | Recursion | Iteration |
|---|---|---|
| Mechanism | Function calls itself repeatedly | Loop constructs (for, while, do-while) repeat a code block |
| Memory Usage | stack frames for recursion depth | fixed memory (single set of loop variables) |
| Execution Speed | Slower due to stack-frame creation, argument passing, and return jumps | Faster with zero function-call overhead |
| Termination | Stops when the base case is satisfied | Stops when the loop condition becomes false |
| Code Clarity | Concise and natural for trees, DFS, Divide & Conquer, TOH | Straightforward for linear counting; complex for branching problems |
| Failure Mode | Stack Overflow on excessive depth or missing base case | Infinite loop if loop variable does not progress |
2.4.4 Execution of recursive calls
Every non-tail recursive call executes in two distinct phases:
- Winding (Calling) Phase: Execution moves downward from the initial call toward the base case, pushing a new activation record onto the call stack at each call. Statements written before the recursive call execute during winding.
- Unwinding (Returning) Phase: Once the base case returns a concrete value, frames are popped one by one from the stack in LIFO order. Each caller completes its pending operations (such as
n * returned_value) and statements written after the recursive call execute during unwinding.
2.4.5 Types of recursions
Recursive functions are categorized by how they call themselves and where the recursive call appears:
Classification of Recursion
- Direct Recursion: A function
f()calls itself directly inside its own body (f() -> f()). - Indirect (Mutual) Recursion: Function
f()calls another functiong(), which in turn callsf()(f() -> g() -> f()). - Tail Recursion: The recursive call is the very last operation executed in the function, leaving no pending computation after the call returns. Because nothing remains to be done in the caller's frame, optimizing compilers can replace the call with a loop jump (Tail Call Optimization, stack space).
- Non-Tail (Head) Recursion: Further work (such as multiplication or addition) remains to be performed after the recursive call returns (e.g.,
return n * factorial(n - 1);). - Tree Recursion: A function makes two or more recursive calls within its body, creating a branching tree of calls whose total count often grows exponentially (e.g., naive
fibonacci(n)or Tower of Hanoi).
/* Tail recursion: accumulator carries the partial product */
int tail_factorial(int n, int acc) {
if (n <= 1)
return acc;
return tail_factorial(n - 1, n * acc); /* Last operation: no pending work */
}
/* Tree recursion: two recursive calls per invocation */
int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}| Feature | Tail Recursion | Tree Recursion |
|---|---|---|
| Recursive Calls per Frame | Single call as the final statement | Multiple calls inside the function body |
| Call Structure | Linear chain of calls | Branching tree of calls |
| Stack Memory | with tail-call optimization; otherwise | stack depth; exponential total calls |
| Typical Examples | Tail-recursive factorial, Euclid's gcd(a, b) | Recursive fibonacci(n), Tower of Hanoi, tree traversals |
2.4.6 Applications of recursion: Tower of Hanoi
The Tower of Hanoi (TOH) is a classic recursive puzzle demonstrating how a multi-step problem decomposes cleanly into smaller identical subproblems.
Problem Setup and Rules
- Three rods: Source (
S), Auxiliary/Intermediate (I), and Destination (D). - distinct disks of decreasing sizes initially stacked on rod
S(largest at the bottom, smallest at the top). - Goal: Transfer all disks from
StoDobeying three rules:- Only one disk may be moved at a time.
- Only the topmost disk of any rod can be lifted.
- No larger disk may ever be placed on top of a smaller disk.
Recursive Algorithm for Disks
- Base Case (): Move the single disk directly from
StoD. - Recursive Case ():
- Recursively move the top disks from
StoIusingDas auxiliary:TOH(n - 1, S, I, D). - Move the largest (-th) disk directly from
StoD. - Recursively move the disks from
ItoDusingSas auxiliary:TOH(n - 1, I, D, S).
- Recursively move the top disks from
#include <stdio.h>
void TOH(int n, char S, char D, char I) {
if (n == 1) {
printf("Move disk 1 from %c to %c\n", S, D);
return;
}
TOH(n - 1, S, I, D);
printf("Move disk %d from %c to %c\n", n, S, D);
TOH(n - 1, I, D, S);
}
int main(void) {
int n = 3;
TOH(n, 'A', 'C', 'B');
return 0;
}Minimum Number of Moves
Each call with disks performs two sub-calls of size plus direct disk move, giving the recurrence:
Unrolling this recurrence yields moves ( time, call-stack space).
Other major applications of recursion include tree and graph traversals (pre-order, in-order, post-order, DFS), divide-and-conquer sorting (Merge Sort, Quick Sort), backtracking puzzles (-Queens, Sudoku), and dynamic programming.
Worked Examples
1
Trace the call stack (winding and unwinding phases) for factorial(4) using the recursive definition factorial(n) = n * factorial(n - 1) with base case factorial(1) = 1.
Winding phase (pushing activation records onto the stack): Each call pauses at n * factorial(n - 1) and pushes a new frame until n == 1:
main()callsfactorial(4)frame(n = 4, pending: 4 * ?)pushed.factorial(4)callsfactorial(3)frame(n = 3, pending: 3 * ?)pushed.factorial(3)callsfactorial(2)frame(n = 2, pending: 2 * ?)pushed.factorial(2)callsfactorial(1)frame(n = 1)pushed; base case met, returns1.
Unwinding phase (popping frames in LIFO order):
| Event | Active Stack Frames (bottom -> top) | Returned Value |
|---|---|---|
Push factorial(4) | [main, fac(4)] | — |
Push factorial(3) | [main, fac(4), fac(3)] | — |
Push factorial(2) | [main, fac(4), fac(3), fac(2)] | — |
Push factorial(1) (base) | [main, fac(4), fac(3), fac(2), fac(1)] | 1 |
Pop fac(1) resume fac(2) | [main, fac(4), fac(3), fac(2)] | 2 * 1 = 2 |
Pop fac(2) resume fac(3) | [main, fac(4), fac(3)] | 3 * 2 = 6 |
Pop fac(3) resume fac(4) | [main, fac(4)] | 4 * 6 = 24 |
Pop fac(4) resume main | [main] | 24 |
factorial(4) reaches a peak stack depth of frames beyond main() and returns .
2
Construct the recursion tree for fibonacci(5) (with base cases fibonacci(0) = 0 and fibonacci(1) = 1), determine the returned value, and count the total number of function calls made.
Drawing the tree-recursion call structure: Each node F(k) with branches into F(k - 1) on the left and F(k - 2) on the right:
F(5)
/ \
F(4) F(3)
/ \ / \
F(3) F(2) F(2) F(1)
/ \ / \ / \
F(2) F(1) F(1) F(0) F(1) F(0)
/ \
F(1) F(0)Counting calls per argument value:
F(5): callF(4): callF(3): callsF(2): callsF(1): calls (each returns )F(0): calls (each returns )
Total calls calls.
Evaluating bottom-up from the leaves:
fibonacci(5) returns and requires total function calls (demonstrating redundant subproblem evaluations such as F(2) computed times).
3
Construct the recursion tree and show the complete sequence of disk moves for the Tower of Hanoi problem with disks moving from rod A (Source) to rod C (Destination) via rod B (Auxiliary).
Building the recursion tree for TOH(3, A, C, B): In TOH(n, S, D, I), the left branch executes TOH(n - 1, S, I, D), the middle prints the move of disk n from S to D, and the right branch executes TOH(n - 1, I, D, S):
TOH(3, A->C, aux B)
/ | \
TOH(2, A->B, C) [Move 3: A->C] TOH(2, B->C, A)
/ | \ / | \
TOH(1,A->C) [2:A->B] TOH(1,C->B) TOH(1,B->A) [2:B->C] TOH(1,A->C)Tracing all moves in execution order (in-order traversal of the tree):
| Move # | Disk Moved | Action | Rod A | Rod B | Rod C |
|---|---|---|---|---|---|
| Initial | — | Start configuration | [3, 2, 1] | [] | [] |
| Disk | A -> C | [3, 2] | [] | [1] | |
| Disk | A -> B | [3] | [2] | [1] | |
| Disk | C -> B | [3] | [2, 1] | [] | |
| Disk | A -> C | [] | [2, 1] | [3] | |
| Disk | B -> A | [1] | [2] | [3] | |
| Disk | B -> C | [1] | [] | [3, 2] | |
| Disk | A -> C | [] | [] | [3, 2, 1] |
All disks move from rod A to rod C in moves: 1: A->C, 2: A->B, 1: C->B, 3: A->C, 1: B->A, 2: B->C, 1: A->C.
Exercises
Exercises
Explain how a recursive algorithm uses the stack data structure to manage intermediate states, illustrating your answer with the calculation of factorial(5).
Role of the call stack in recursion: Each recursive invocation creates a new activation record on the runtime call stack holding the parameter n, local variables, and the return address. Because inner calls must finish before outer callers can multiply by n, frames are pushed during the winding phase and popped in LIFO order during the unwinding phase.
Stack trace for factorial(5):
- Winding (pushes):
fac(5)fac(4)fac(3)fac(2)fac(1)(peak depth: frames). - Base case:
fac(1)returns1. - Unwinding (pops):
fac(2)computes and returns2.fac(3)computes and returns6.fac(4)computes and returns24.fac(5)computes and returns120.
The runtime call stack preserves each call's parameters and pending computations in LIFO activation records; factorial(5) pushes frames down to factorial(1) = 1 and unwinds to return .
Distinguish between recursion and iteration. Write both recursive and iterative C functions to find the -th Fibonacci number () and compare their time and space efficiencies.
Key differences:
- Control mechanism: Recursion uses self-calling functions and the call stack; iteration uses explicit loops (
for/while) and local state variables. - Memory & overhead: Recursion consumes stack frames with function-call overhead; iteration uses space and executes faster.
C implementations:
int fib_rec(int n) {
if (n <= 1) return n;
return fib_rec(n - 1) + fib_rec(n - 2);
}
int fib_iter(int n) {
if (n <= 1) return n;
int a = 0, b = 1, c = 0;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}Efficiency comparison:
fib_rec(n)recomputes overlapping subproblems exponentially, taking time and stack space.fib_iter(n)computes each term once in a single loop, taking time and space.
Recursive Fibonacci runs in time, stack space, whereas iterative Fibonacci runs in time, space without function-call overhead.
Explain direct, indirect, tail, and tree recursion with a short C code snippet for each.
Definitions and C examples:
- Direct Recursion: A function calls itself directly (
countdown(n)callscountdown(n - 1)). - Indirect Recursion:
even(n)callsodd(n - 1)andodd(n)callseven(n - 1). - Tail Recursion: The recursive call is the final action with no pending arithmetic or post-processing.
- Tree Recursion: A function makes multiple recursive calls per invocation, creating a call tree.
/* 1. Direct */
void countdown(int n) {
if (n <= 0) return;
printf("%d ", n);
countdown(n - 1);
}
/* 2. Indirect */
int isOdd(int n);
int isEven(int n) { return (n == 0) ? 1 : isOdd(n - 1); }
int isOdd(int n) { return (n == 0) ? 0 : isEven(n - 1); }
/* 3. Tail */
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
/* 4. Tree */
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}Direct recursion calls itself (countdown), indirect recursion cycles across functions (isEven/isOdd), tail recursion makes the recursive call its final operation (gcd), and tree recursion spawns two or more recursive branches (fib).
Draw the recursion tree for fibonacci(4) (where fibonacci(0) = 0, fibonacci(1) = 1), and find both the final value and the total number of function calls.
Constructing the recursion tree for F(4):
F(4)
/ \
F(3) F(2)
/ \ / \
F(2) F(1) F(1) F(0)
/ \
F(1) F(0)Counting calls and evaluating bottom-up:
- Calls:
F(4)(),F(3)(),F(2)(),F(1)(),F(0)() total calls. - Values:
F(2) = 1 + 0 = 1,F(3) = 1 + 1 = 2,F(4) = 2 + 1 = 3.
fibonacci(4) returns and executes total function calls.
Write the recursive algorithm for the Tower of Hanoi (TOH) problem with disks, derive the recurrence for the minimum number of disk moves , and calculate the exact number of moves required for disks.
Recursive TOH algorithm:
- If , move disk from
StoDand return. - Recursively move disks from
StoIusingD. - Move disk from
StoD. - Recursively move disks from
ItoDusingS.
Deriving the move-count formula :
Computing for disks:
The Tower of Hanoi requires moves; for disks, moves are required.
Convert the non-tail recursive function sumN(n) (which computes ) into a tail-recursive C function using an accumulator, and compute the result for . Why does tail recursion allow stack space under compiler optimization?
Comparing non-tail and tail-recursive versions in C:
/* Non-tail recursive: addition happens AFTER recursive call returns */
int sumN_nontail(int n) {
if (n <= 0) return 0;
return n + sumN_nontail(n - 1);
}
/* Tail recursive: accumulator holds running total; no pending operation */
int sumN_tail(int n, int acc) {
if (n <= 0) return acc;
return sumN_tail(n - 1, acc + n);
}Tracing sumN_tail(10, 0) and tail-call optimization:
- Calling
sumN_tail(10, 0)passes(9, 10) -> (8, 19) -> ... -> (0, 55), returning55(matching ). - Because no arithmetic or state update occurs after
sumN_tail(n - 1, acc + n)returns, an optimizing compiler overwrites the current stack frame's parameters (n = n - 1,acc = acc + n) and jumps back to the start of the function—reusing a single frame ( stack space).
The tail-recursive function sumN_tail(n, acc) returns acc when and otherwise returns sumN_tail(n - 1, acc + n). For , sumN_tail(10, 0) returns ; with tail-call optimization, the compiler reuses the same stack frame in space.