Describe the picture

The first time you see a function that calls itself, it feels like a trick. How can a function use itself before it is finished?

The secret is the call stack — the part of memory where C keeps track of every function call that is still running. Once you can picture the stack, recursion becomes surprisingly easy to follow.

What is recursion?

A recursive function solves a problem by calling itself on a smaller version of the same problem.

Think of a stack of 100 exam papers to count. You could count them one by one — or you could say:

The number of papers = 1 + the number of papers in the rest of the stack.

Your friend uses the same rule on the rest, and so on, until someone is handed zero papers and simply answers "0". Then the answers come back up the chain: 0 + 1 + 1 + …

Every recursive solution has the same two parts:

  1. Base case — the smallest problem, answered directly, without calling again ("zero papers → 0").
  2. Recursive case — the problem expressed using a smaller version of itself ("1 + count(the rest)").

The classic example: factorial

The factorial of n is n × (n − 1) × … × 1. So 4! = 4 × 3 × 2 × 1 = 24.

Notice that 4! = 4 × 3!, and 3! = 3 × 2!, and so on. That is a recursive definition:

#include <stdio.h>

long long fact(int n)
{
    if (n <= 1)                 // base case
        return 1;
    return n * fact(n - 1);     // recursive case
}

int main(void)
{
    printf("%lld\n", fact(4));  // 24
    return 0;
}

We use long long because factorials grow very fast — 13! is already too big for an int.

Watching it on the call stack

Every time a function is called, C puts a new frame on the call stack. A frame holds that call's own parameters and local variables — so each call of fact has its own n.

Going down (winding):

main        calls fact(4)
fact(4)     n = 4   waits for fact(3)
fact(3)     n = 3   waits for fact(2)
fact(2)     n = 2   waits for fact(1)
fact(1)     n = 1   base case → returns 1

At this moment there are five frames on the stack: main and four calls of fact, each with a different n, each paused in the middle of its return line.

Coming back up (unwinding):

fact(1) returns 1
fact(2) returns 2 × 1 = 2
fact(3) returns 3 × 2 = 6
fact(4) returns 4 × 6 = 24  → back in main

The last call made is the first one to finish. That "last in, first out" order is exactly why it is called a stack.

What if you forget the base case?

long long fact(int n)
{
    return n * fact(n - 1);     // no base case!
}

Nothing ever stops the calls: fact(4) calls fact(3), then fact(2), fact(1), fact(0), fact(-1), fact(-2) … Every call adds a frame, until the stack memory is full and the program crashes with a stack overflow (on Linux: Segmentation fault).

A similar bug: a base case that can be jumped over.

if (n == 1) return 1;           // fact(0) never reaches n == 1!

Using n <= 1 catches 1, 0 and any negative number.

Code before vs after the recursive call

Where you place your code changes the order of the output. Compare:

void down(int n)
{
    if (n == 0) return;
    printf("%d ", n);    // BEFORE the call
    down(n - 1);
}

void up(int n)
{
    if (n == 0) return;
    up(n - 1);
    printf("%d ", n);    // AFTER the call
}

down(3) prints 3 2 1 — each call prints on the way down.

up(3) prints 1 2 3 — each call waits for the deeper calls first, then prints on the way back up.

This is a favourite exam question, and the call stack makes it easy to answer.

Fibonacci: beautiful but slow

The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13 … — each one is the sum of the two before it. The recursive version reads just like the definition:

int fib(int n)
{
    if (n < 2) return n;                 // fib(0) = 0, fib(1) = 1
    return fib(n - 1) + fib(n - 2);
}

But draw the calls for fib(5) and you get a tree:

                fib(5)
            /          \
        fib(4)          fib(3)
        /    \          /    \
    fib(3)  fib(2)  fib(2)  fib(1)
     ...      ...     ...

fib(3) is calculated twice, fib(2) three times, and so on. fib(5) makes 15 calls; fib(40) makes more than 300 million. Each call does almost nothing new.

A simple loop needs only n rounds:

int fibLoop(int n)
{
    int a = 0, b = 1;
    for (int i = 0; i < n; i++)
    {
        int next = a + b;
        a = b;
        b = next;
    }
    return a;
}

Recursion or a loop?

Anything you can write with recursion can also be written with a loop. So when should you use which?

Recursion is a good fit when the problem naturally splits into smaller copies of itself:

  • trees (every subtree is a tree)
  • the Tower of Hanoi
  • divide-and-conquer sorting such as merge sort and quick sort
  • exploring all possibilities (backtracking)

A loop is usually better when the problem is a straight line of steps — sums, counting, factorial, Fibonacci. Loops use no extra stack memory and are faster.

How to write a recursive function — a recipe

  1. Find the smallest case whose answer you know. Write it first.
  2. Describe the answer for n using the answer for something smaller (n − 1, n / 10, the rest of an array).
  3. Check that every call gets closer to the base case.
  4. Trust the recursive call. Assume sumDigits(n / 10) returns the right answer — don't try to trace every level in your head.
  5. Test with a tiny input (n = 0, 1, 2) and draw the frames on paper.

Example — the sum of the digits of a number:

int sumDigits(int n)
{
    if (n < 10) return n;                 // one digit: its own sum
    return n % 10 + sumDigits(n / 10);    // last digit + sum of the rest
}

sumDigits(4096) = 6 + sumDigits(409) = 6 + 9 + sumDigits(40) = 6 + 9 + 0 + 4 = 19.

Watch the stack grow and shrink

Recursion clicks fastest when you can see the frames. In our free interactive lab you can step through factorial and watch each frame appear and disappear, tick "no base case" to watch the stack overflow, see the Fibonacci call tree grow, and solve the Tower of Hanoi with its pegs:

Quick summary

  • A recursive function calls itself on a smaller problem.
  • It needs a base case that stops the calls.
  • Each call gets its own frame (its own variables) on the call stack.
  • The stack winds down to the base case, then unwinds — last in, first out.
  • No base case → stack overflow.
  • Naive recursive Fibonacci repeats work; a loop is much faster.

Practice

  1. Write int power(int b, int e) recursively (base case: e == 0).
  2. Write a recursive function that prints the digits of a number in reverse.
  3. Count how many times fib is called for n = 6 by adding a global counter.
  4. Write void hanoi(int n, char from, char to, char via) and check that 3 disks need 7 moves (2³ − 1).

Recursion is not about being clever. It is about trusting a smaller version of the problem — and letting the call stack do the bookkeeping.