📈 Algorithms & Complexity

Recursion: functions that call themselves

⏱ 14 min · free interactive lesson · quizzes, visualizations & a real compiler

A recursive function solves a problem by calling itself on a smaller version of the same problem. It sounds like cheating — "to sort the array, sort the array" — but you already watched it work: quicksort and merge sort are recursion. The trick is that each call shrinks the job, until it's so small the answer is obvious.

The anatomy: base case + recursive case

Every correct recursive function has exactly two ingredients:

• Base case: an input so small you return the answer directly. This is the emergency brake.
• Recursive case: do a little work, then call yourself on a strictly smaller input that marches toward the base case.

#include <stdio.h>

long fact(int n) {
    if (n <= 1)                 /* BASE case: brake!     */
        return 1;
    return n * fact(n - 1);     /* RECURSIVE case:       */
}                               /*   shrink toward base  */

int main(void) {
    printf("4!  = %ld\n", fact(4));
    printf("10! = %ld\n", fact(10));
    return 0;
}

$ gcc fact.c -o fact && ./fact
4!  = 24
10! = 3628800

Watch the call stack breathe

Recursion works because of something you met in Part 0: every call gets its own stack frame with its own n. Four calls to fact means four separate ns alive at once. Step through and watch the stack grow, hit the base case, then unwind while multiplying:

▶ This spot has an interactive trace widget — open the interactive lesson to play with it.

Fibonacci: recursion's cautionary tale

The Fibonacci definition — fib(n) = fib(n−1) + fib(n−2) — translates to gorgeous, tragic C:

#include <stdio.h>

long long fib(int n) {          /* naive: TWO calls per call */
    if (n < 2) return n;        /* fib(0)=0, fib(1)=1        */
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    printf("fib(45) = %lld\n", fib(45));
    return 0;
}

$ gcc -O2 fib_naive.c -o fib_naive && time ./fib_naive
fib(45) = 1134903170

real    0m4.31s
# ~4 seconds — and every +1 to n multiplies the time by ~1.6

Four seconds?! For one number?! Look at what the calls actually do:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)   ← computed here…
│   │   └── fib(1)
│   └── fib(2)       ← …and again here…
└── fib(3)           ← this WHOLE subtree is a repeat!
    ├── fib(2)       ← …and again here
    └── fib(1)

15 calls for fib(5). fib(45) makes ~3.6 BILLION calls.

Every call spawns two more, and the same subproblems get recomputed again and again — fib(2) alone is computed 3 times in that tiny tree, and about a billion times in fib(45). The call count roughly doubles per level: exponential, about Θ(1.618ⁿ) (the golden ratio!), which the O(2ⁿ) curve bounds from above:

▶ This spot has an interactive bigo widget — open the interactive lesson to play with it.

The fix: remember what you computed

Memoization — cache each answer the first time, return the cached value ever after. One array turns an exponential algorithm into a linear one:

#include <stdio.h>

long long memo[93];   /* fib(92) is the last to fit long long */

long long fib(int n) {
    if (n < 2) return n;
    if (memo[n]) return memo[n];       /* cached? done: O(1) */
    return memo[n] = fib(n - 1) + fib(n - 2);
}

int main(void) {
    printf("fib(45) = %lld\n", fib(45));
    printf("fib(90) = %lld\n", fib(90));
    return 0;
}

$ gcc -O2 fib_memo.c -o fib_memo && time ./fib_memo
fib(45) = 1134903170
fib(90) = 2880067194370816120

real    0m0.002s
# each fib(k) computed once, then looked up: Θ(n). 2000x faster,
# and it reaches n=90 where the naive version needs ~centuries.

Recursion vs iteration

Anything recursive can be rewritten with a loop (plus, sometimes, an explicit stack — next lesson!), and vice versa. Rules of thumb:

• Naturally recursive shapes — trees, divide & conquer, nested structures — stay clearer as recursion.
• Linear passes (factorial, summing, fibonacci-with-memo) are usually better as plain loops: no stack-depth limit, less call overhead.
• A tail call — where the recursive call is the very last action, its result returned unchanged — can be optimized by compilers into a loop (gcc/clang do it at -O2). But C the language doesn't guarantee it, so never bet your stack on it.

The showpiece: Tower of Hanoi

Move n disks from peg A to peg C, one at a time, never placing a bigger disk on a smaller one. Iteratively: a nightmare. Recursively: three lines of pure elegance — move n−1 disks out of the way, move the big one, move the n−1 back on top.

#include <stdio.h>

void hanoi(int n, char from, char to, char via) {
    if (n == 0) return;              /* base: nothing to move */
    hanoi(n - 1, from, via, to);     /* clear the n-1 above   */
    printf("move disk %d: %c -> %c\n", n, from, to);
    hanoi(n - 1, via, to, from);     /* stack them back on    */
}

int main(void) {
    hanoi(3, 'A', 'C', 'B');
    return 0;
}

$ gcc hanoi.c -o hanoi && ./hanoi
move disk 1: A -> C
move disk 2: A -> B
move disk 1: C -> B
move disk 3: A -> C
move disk 1: B -> A
move disk 2: B -> C
move disk 1: A -> C

▶ This spot has an interactive editor widget — open the interactive lesson to play with it.

To trace recursion we kept talking about "the stack" — pushing frames, popping frames. That push/pop discipline is a data structure in its own right, and it's next.