AdvancedC Programming · Lesson 17 of 21 · Updated ·
Recursion and Stack Frames in C — How the Call Stack Works, Tail Recursion, Tower of Hanoi
The functions lesson showed that a recursive function calls itself and needs a base case. This lesson explains how that works inside the machine, using the call stack. Once you can picture the stack, recursive output questions become easy to trace, and you can tell when recursion is a good idea and when a loop is better.
1. Every call gets a stack frame
When a function is called, the program reserves a block of memory on the stack called a stack frame (or activation record). It holds:
- the function's parameters and local variables,
- the return address — where to continue in the caller when this call finishes.
When the call returns, its frame is removed. The stack works like a pile of plates in a canteen: the last frame pushed is the first one removed (LIFO, last in first out).
Because each call has its own frame, every recursive call has its own copy of n. They do not overwrite each other.
2. Winding and unwinding
A recursive call has two phases:
- Winding — calls go deeper and frames are pushed, until the base case is reached.
- Unwinding — calls return one by one and frames are popped.
Code written before the recursive call runs while winding (top to bottom). Code written after it runs while unwinding (in reverse order). This one fact explains most "predict the output" questions.
#include <stdio.h>
void show(int n) {
if (n == 0)
return; /* base case */
printf("in %d\n", n); /* runs while winding */
show(n - 1);
printf("out %d\n", n); /* runs while unwinding */
}
int main(void) {
show(3);
return 0;
}
in 3
in 2
in 1
out 1
out 2
out 3
The frame for n = 3 waits, paused at the line show(n - 1), until everything below it has finished. Then it continues with "out 3".
3. Returning values up the stack
#include <stdio.h>
long fact(int n) {
if (n <= 1)
return 1;
return n * fact(n - 1); /* multiply AFTER the inner call returns */
}
int sum_digits(int n) {
if (n == 0)
return 0;
return n % 10 + sum_digits(n / 10);
}
int main(void) {
printf("%ld\n", fact(4));
printf("%ld\n", fact(10));
printf("%d\n", sum_digits(9045));
return 0;
}
24
3628800
18
fact(4) cannot finish its multiplication until fact(3) returns, which waits for fact(2), and so on. The answers come back up: 1, then 2 × 1 = 2, then 3 × 2 = 6, then 4 × 6 = 24.
4. Recursion trees and counting calls
When a function calls itself more than once, the calls form a tree. The classic example is Fibonacci:
int fib(int n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }
The tree shows the problem: fib(3) is computed twice and fib(2) three times. The number of calls grows roughly like 1.6ⁿ — exponential time. A simple loop does the same job in O(n):
#include <stdio.h>
int calls = 0;
int fib(int n) {
calls++;
return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
int fib_loop(int n) {
int a = 0, b = 1;
for (int i = 0; i < n; i++) {
int t = a + b;
a = b;
b = t;
}
return a;
}
int main(void) {
int r = fib(5); /* call first: C does not fix the order of printf's arguments */
printf("fib(5) = %d using %d calls\n", r, calls);
calls = 0;
r = fib(25);
printf("fib(25) = %d using %d calls\n", r, calls);
printf("loop: %d %d\n", fib_loop(5), fib_loop(25));
return 0;
}
fib(5) = 5 using 15 calls
fib(25) = 75025 using 242785 calls
loop: 5 75025
Nearly a quarter of a million calls for fib(25), against 25 loop steps. The fix is either a loop or memoisation (remember answers you already computed), which you will meet in dynamic programming.
5. Stack overflow and tail recursion
The stack is small — often around 1 MB on Windows and 8 MB on Linux by default, depending on the system. Each frame uses some of it. If recursion goes too deep (or never reaches the base case), the stack runs out: a stack overflow, and the program crashes. So recursion of depth 1,000,000 is risky in C, even with a correct base case.
A call is a tail call if it is the very last thing the function does — nothing is left to compute after it returns.
/* NOT tail recursive: the multiply happens after the call returns */
long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }
/* tail recursive: the answer is carried in acc */
long fact_tail(int n, long acc) { return n <= 1 ? acc : fact_tail(n - 1, n * acc); }
Optimising compilers (for example GCC or Clang with -O2) can turn a tail call into a jump, so the stack does not grow. The C standard does not require this, so do not rely on it for very deep recursion. When depth can be large, write a loop.
| Recursion | Loop | |
|---|---|---|
| Code for trees, divide-and-conquer, backtracking | short and natural | long, needs your own stack |
| Memory | one frame per active call | constant |
| Risk | stack overflow if too deep | none from depth |
| Speed | call overhead | usually faster |
6. Tower of Hanoi
Move n discs from peg A to peg C, using B as a helper. Rules: move one disc at a time, and never put a bigger disc on a smaller one.
The recursive idea in three steps:
- Move the top n − 1 discs from A to B (using C).
- Move the biggest disc from A to C.
- Move the n − 1 discs from B to C (using A).
#include <stdio.h>
int moves = 0;
void hanoi(int n, char from, char to, char via) {
if (n == 0)
return;
hanoi(n - 1, from, via, to);
printf("disc %d: %c -> %c\n", n, from, to);
moves++;
hanoi(n - 1, via, to, from);
}
int main(void) {
hanoi(3, 'A', 'C', 'B');
printf("moves = %d\n", moves);
return 0;
}
disc 1: A -> C
disc 2: A -> B
disc 1: C -> B
disc 3: A -> C
disc 1: B -> A
disc 2: B -> C
disc 1: A -> C
moves = 7
The number of moves is 2ⁿ − 1: 7 for 3 discs, 1023 for 10 discs.
7. Backtracking: all permutations
Recursion is the natural tool when you must try every choice. To list all arrangements of "ABC": fix each letter in the first position, arrange the rest recursively, then undo the swap (backtrack) before trying the next letter.
#include <stdio.h>
#include <string.h>
void swap(char *a, char *b) { char t = *a; *a = *b; *b = t; }
void permute(char *s, int k, int n) {
if (k == n) {
printf("%s\n", s);
return;
}
for (int i = k; i < n; i++) {
swap(&s[k], &s[i]); /* choose */
permute(s, k + 1, n); /* explore */
swap(&s[k], &s[i]); /* undo */
}
}
int main(void) {
char s[] = "ABC";
permute(s, 0, (int)strlen(s));
return 0;
}
ABC
ACB
BAC
BCA
CBA
CAB
There are 3! = 6 arrangements. The depth of the recursion is only n, so the stack stays small even though the number of results grows fast.
Common mistakes
- No base case, or a base case that is never reached (for example
fact(-1)withif (n == 0)): infinite recursion and a stack overflow. - Changing the argument the wrong way (
f(n + 1)instead off(n - 1)). - Forgetting
returnin front of the recursive call when a value is needed. - Using plain recursion for Fibonacci-like problems with overlapping calls — exponential time.
- Forgetting to undo the choice in backtracking.
- Assuming the compiler will always optimise tail calls.
Quick recap
- Each call gets its own stack frame with its own parameters, locals and return address.
- Code before the recursive call runs while winding; code after it runs while unwinding, in reverse.
- Multiple recursive calls form a tree; naive Fibonacci makes an exponential number of calls.
- Deep recursion can overflow the stack; tail calls may be optimised, but C does not promise it.
- Tower of Hanoi takes 2ⁿ − 1 moves; backtracking = choose, explore, undo.