# Recursion and Stack Frames in C — How the Call Stack Works, Tail Recursion, Tower of Hanoi

Source: https://skills101.in/learn/c-programming/c-recursion-and-stack-frames — Skills101 free tutorial (C Programming). Updated 2026-11-21.

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.

![The call stack while computing fact of 4: frames for n = 4, 3, 2 and 1 are pushed one on top of the other; then they return 1, 2, 6 and 24 as the stack unwinds](https://skills101.in/learn-img/c-programming/stack-frames.svg)

## 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.

```c
#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;
}
```

```text
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

```c
#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;
}
```

```text
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:

```c
int fib(int n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }
```

![The recursion tree of fib of 5: fib 5 calls fib 4 and fib 3, which split again down to fib 1 and fib 0; fib 3 is computed 2 times and fib 2 is computed 3 times, 15 calls in total](https://skills101.in/learn-img/c-programming/fib-tree.svg)

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):

```c
#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;
}
```

```text
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.

```c
/* 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:

1. Move the top n − 1 discs from A to B (using C).
2. Move the biggest disc from A to C.
3. Move the n − 1 discs from B to C (using A).

```c
#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;
}
```

```text
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.

```c
#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;
}
```

```text
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)` with `if (n == 0)`): infinite recursion and a stack overflow.
- Changing the argument the wrong way (`f(n + 1)` instead of `f(n - 1)`).
- Forgetting `return` in 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.


Practice quiz and free certificate: https://skills101.in/learn/c-programming/c-recursion-and-stack-frames