Recursion

A recursive function is a function that calls itself. That sounds like a loop that never ends, but it works because each call solves a slightly smaller version of the same problem, until the problem becomes so small that the answer is obvious.

Recursion is a natural way to express problems that contain smaller copies of themselves: factorials, folders inside folders, family trees and many searching and sorting algorithms. In this lesson you will write recursive functions, watch how the computer runs them, and learn when a simple loop is the better choice.

Base case and recursive case

Every recursive function needs two parts:

• A base case: a small input whose answer is known directly, without another call.
• A recursive case: the function calls itself on a smaller input and uses that result.

The factorial of n, written n!, is n × (n-1) × ... × 1. Notice that 5! is just 5 × 4!. That is the recursive case, and 1! = 1 (and 0! = 1) is the base case.

#include <stdio.h>

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

int main(void)
{
    printf("5! = %lld\n", factorial(5));
    printf("10! = %lld\n", factorial(10));
    printf("20! = %lld\n", factorial(20));
    return 0;
}

5! = 120
10! = 3628800
20! = 2432902008176640000

Factorials grow very fast, so the function returns long long. 20! is the largest factorial that fits; 21! would overflow, which for a signed type is undefined behaviour.

How the computer runs recursion

Each function call gets its own stack frame: a small area of memory, on a region called the call stack, that holds that call's parameters and local variables. When factorial(4) calls factorial(3), the first call pauses and waits, with its own n still equal to 4. Adding a few printf calls makes this visible:

#include <stdio.h>

long long factorial(int n)
{
    printf("factorial(%d) called\n", n);
    if (n <= 1) {
        printf("factorial(%d) returns 1\n", n);
        return 1;
    }
    long long result = n * factorial(n - 1);
    printf("factorial(%d) returns %lld\n", n, result);
    return result;
}

int main(void)
{
    long long answer = factorial(4);
    printf("4! = %lld\n", answer);
    return 0;
}

factorial(4) called
factorial(3) called
factorial(2) called
factorial(1) called
factorial(1) returns 1
factorial(2) returns 2
factorial(3) returns 6
factorial(4) returns 24
4! = 24

The calls go down until the base case, then the answers come back up in reverse order, each waiting call finishing its multiplication. This "down, then back up" shape is the key to understanding every recursive function.

A faster recursive power function

Recursion can also make an algorithm much faster. Calculating 3 to the power 13 by repeated multiplication takes 12 multiplications. But x to the power n equals (x to the power n/2) squared, with one extra multiplication by x when n is odd. Each call halves the exponent:

#include <stdio.h>

long long power(long long base, int exp)
{
    if (exp == 0) {
        return 1;                           // anything to the power 0 is 1
    }
    long long half = power(base, exp / 2);
    if (exp % 2 == 0) {
        return half * half;
    }
    return half * half * base;
}

int main(void)
{
    printf("2 to the power 10 = %lld\n", power(2, 10));
    printf("3 to the power 13 = %lld\n", power(3, 13));
    printf("7 to the power 0 = %lld\n", power(7, 0));
    return 0;
}

2 to the power 10 = 1024
3 to the power 13 = 1594323
7 to the power 0 = 1

For an exponent of 13, the calls use exponents 13, 6, 3, 1 and 0: only five calls instead of twelve multiplications. For an exponent of a million, about twenty calls are enough. This idea, called fast exponentiation, is used in cryptography.

When recursion is slow: repeated work

The Fibonacci numbers start 0, 1, and each next number is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, 13 and so on. The direct recursive version is short but recalculates the same values again and again:

#include <stdio.h>

long long calls = 0;

long long fib_slow(int n)
{
    calls++;
    if (n < 2) {
        return n;
    }
    return fib_slow(n - 1) + fib_slow(n - 2);
}

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

int main(void)
{
    long long slow = fib_slow(30);
    printf("fib_slow(30) = %lld, using %lld calls\n", slow, calls);
    printf("fib_fast(30) = %lld, using a loop of 30 steps\n", fib_fast(30));
    return 0;
}

fib_slow(30) = 832040, using 2692537 calls
fib_fast(30) = 832040, using a loop of 30 steps

Over 2.6 million calls for one answer! fib_slow(30) calls fib_slow(28) twice, fib_slow(27) three times, and so on. The loop version does 30 steps. The lesson: recursion is elegant, but check that it does not solve the same small problem many times. (Notice also that slow is stored before the printf; C does not promise the order in which function arguments are evaluated, so reading calls in the same call could show 0.)

Tower of Hanoi

Some problems are much easier to solve recursively than with loops. In the Tower of Hanoi puzzle, you move a stack of disks from peg A to peg C, one disk at a time, never placing a larger disk on a smaller one. The recursive idea: move the top n-1 disks out of the way to B, move the biggest disk to C, then move the n-1 disks from B onto it.

#include <stdio.h>

void hanoi(int n, char from, char via, char to)
{
    if (n == 0) {
        return;
    }
    hanoi(n - 1, from, to, via);
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, via, from, to);
}

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

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Three disks need 7 moves, and n disks need 2 to the power n, minus 1. You never had to plan the moves yourself: the base case and one recursive rule did all the work.

Stack overflow

Each waiting call uses stack memory, and the stack is limited, often 8 MB on Linux and 1 MB for the main thread on Windows. A recursion that goes too deep, or never reaches its base case, uses it all up. This is a stack overflow, and the program crashes, usually with "Segmentation fault" on Linux. Calling factorial(-5) on a version whose base case is n == 1 would recurse forever and crash. Choose base cases that catch every small or invalid input, as n <= 1 does.

Recursion or loop?

Common mistakes

• No base case, or one that is never reached. The function calls itself until the stack overflows.
• Not making the problem smaller. f(n) calling f(n) again never ends.
• Forgetting to return the recursive result. Writing factorial(n - 1); without return and multiplication throws the answer away.
• Recomputing the same values. Naive Fibonacci is exponential; use a loop or store results.

Key points

• A recursive function calls itself on a smaller input and stops at a base case.
• Each call has its own stack frame with its own parameters and locals.
• Calls go down to the base case, then the results come back up in reverse order.
• Recursion can be fast (power by halving) or very slow (naive Fibonacci) depending on repeated work.
• Very deep recursion causes a stack overflow; prefer loops for simple repetition.

#include <stdio.h>

int gcd(int a, int b)
{
    if (b == 0) {
        return a;            // base case
    }
    return gcd(b, a % b);    // recursive case
}

int main(void)
{
    printf("gcd(84, 36) = %d\n", gcd(84, 36));
    printf("gcd(1071, 462) = %d\n", gcd(1071, 462));
    return 0;
}

gcd(84, 36) = 12
gcd(1071, 462) = 21