Recursion: a Function That Calls Itself

Bob learned in Module 7 that a function can call any other function. Then a bold thought: can a function call itself? He wants 1 + 2 + 3, and he notices that it is 3 plus the sum 1 + 2.

So he writes a function that adds n to its own answer for n - 1, and presses Run. Nothing appears. After 10 seconds the Playground stops the program, and the badge reads Time limit exceeded.

His book promised a dramatic "stack overflow" for a mistake like this. He got a quiet clock instead. This lesson finds the line Bob left out, and what really happened in those 10 seconds.

Recursion: a function that calls itself

A function that calls itself is recursive, and the idea is called recursion. It works when each call hands a smaller version of the same problem to the next call. Here is Bob's program, exactly as he ran it.

#include <stdio.h>

int sum_to(int n);

int main(void)
{
    printf("%d\n", sum_to(3));
    return 0;
}

int sum_to(int n)
{
    return n + sum_to(n - 1);
}

Follow it by hand. sum_to(3) needs sum_to(2), which needs sum_to(1), which needs sum_to(0). Nothing tells sum_to(0) to stop, so it asks for sum_to(-1), then sum_to(-2), with no end.

Think of a long queue at a ticket counter. You want to know your place, so you ask the person in front and add one. They do the same. The chain ends at the first person, who knows without asking: they are number 1.

So a recursive function needs one call that answers without asking anyone. In Bob's program every call asks, and no call ever answers.

The two rules: a base case and a step

Every recursive function that ends follows two rules. The base case is the smallest input, answered directly, with no call. The step calls the same function on a smaller input, one step closer to the base case. Some books call the step the recursive case.

type name(int n)
{
    if (n == smallest) {
        return answer;
    }
    return ... name(n - 1) ...;
}

Bob adds the missing rule. The sum of the numbers up to 0 is 0, so sum_to(0) returns 0 without a call. He also makes the answer a long long, because from n = 65536 the sum passes INT_MAX.

#include <stdio.h>

long long sum_to(int n);

int main(void)
{
    printf("%lld\n", sum_to(3));
    printf("%lld\n", sum_to(100));
    return 0;
}

long long sum_to(int n)
{
    if (n == 0) {
        return 0;
    }
    return n + sum_to(n - 1);
}

Trace it before you run it. Module 6 traced a loop with one row per pass. A recursion gets one row per call: the call, its parameter, what it waits for, and what it returns. Call it a frame table.

Fill the table in two passes. Go down the first three columns as the calls are made. Then fill the last column from the bottom up: a row can finish only after the row below it returns.

6
5050

So the base case is where the answers start. Without it, as in Bob's program, no row ever returns.

Countdown: work before the call

Bob's rocket game from Module 6 needs its countdown back, this time as a recursion. Counting down from n means: say n, then count down from n - 1. Counting down from 0 means just "liftoff".

#include <stdio.h>

void countdown(int n);

int main(void)
{
    countdown(3);
    return 0;
}

void countdown(int n)
{
    if (n == 0) {
        printf("liftoff\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);
}

3
2
1
liftoff

Each call prints first and calls second, so the numbers appear in the order the calls are made. The base case prints liftoff at the bottom. A void function returns no value, so its base case ends with a plain return;.

So work placed before the call happens on the way down, in the order the calls are made.

Work after the call happens on the way back up

Now put the work below the call. A line after the call cannot run until that call has returned. So lines after the call run in the opposite order, on the way back up.

Alice wants to watch sum_to build its answer. She keeps each total in a local variable and prints it after the call.

#include <stdio.h>

long long sum_to(int n);

int main(void)
{
    long long total = sum_to(3);

    printf("total: %lld\n", total);
    return 0;
}

long long sum_to(int n)
{
    long long total = 0;

    if (n == 0) {
        return 0;
    }
    total = n + sum_to(n - 1);
    printf("sum to %d is %lld\n", n, total);
    return total;
}

The calls are made from the top row down, but the prints happen from the bottom row up. sum_to(1) prints first, because it is the first call to get its answer.

sum to 1 is 1
sum to 2 is 3
sum to 3 is 6
total: 6

Every call gets its own boxes for its parameters and local variables (Module 7). That set of boxes is the call's frame. The frames of calls still waiting pile up in a part of memory called the stack, one frame per call. Lesson 2 opens the stack up; here is the picture.

The left arrows are the calls, on the way down. The right arrows are the answers, on the way back up. A frame disappears when its call returns.

So work before the call runs along the left arrows, and work after it along the right ones.

Factorial, with a long long

Module 6 asked you for Kenji's factorial as a loop, and promised it would come back. The factorial of n, written n!, is 1 x 2 x ... x n, and 0! is 1. Read it the recursive way: n! is n times (n - 1)!, and 0! is the base case.

#include <stdio.h>

long long factorial(int n);

int main(void)
{
    for (int i = 0; i <= 20; i++) {
        printf("%d! = %lld\n", i, factorial(i));
    }
    return 0;
}

long long factorial(int n)
{
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

Here is the frame table for one of those calls, factorial(4).

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000

The answer grows fast. 12! = 479001600 fits an int, but 13! = 6227020800 is past INT_MAX, which is 2147483647. That is why factorial returns a long long.

A long long stops at 20!. LLONG_MAX is 9223372036854775807, and 20! is about a quarter of it. 21! is 21 times 20!, about 5.1 x 10^19, more than five times LLONG_MAX. Working it out is signed overflow, which is undefined behaviour (Module 2), so this lesson never prints it.

So a recursive factorial needs the base case 0! = 1 and a type big enough for the answer: an int up to 12!, a long long up to 20!.

The missing base case, measured

Back to Bob's program. His book says a function with no base case shows the error "Stack overflow". C prints no such message, and on the Playground Bob's program did not crash at all. Here is why.

The Playground compiles with GCC 12 at -O2, which optimises. It rewrites your program into faster machine code that does the same job. GCC 12 saw that each call only adds a number to the next call's answer. So it replaced the calls with a loop, and that loop has no way out.

Here is that machine code, called a listing, as GCC 12 printed it on Compiler Explorer at the Playground's -O2:

main:
.L2:
        jmp     .L2
sum_to:
.L5:
        jmp     .L5

jmp .L2 means "jump to the label .L2", and .L2 is that same line. So main jumps to itself forever and never reaches its printf. No call is left, nothing piles up, and the program spins until the 10 second limit.

What you see depends on what the function does around its call:

The machine code also depends on the build. Build Bob's file with no optimisation, at -O0, and every call gets a real frame. On Compiler Explorer's GCC 12 that build crashed in 193 ms (one run) with Program terminated with signal SIGSEGV (11).

In a Linux terminal the same crash prints Segmentation fault. That is how the operating system reports a program that touched memory it may not use. Lesson 5 explains the signal and the stack's limit.

None of these results mentions recursion, but the compiler can name it. The Playground stays silent. A local gcc -Wall on GCC 12 says warning: infinite recursion detected [-Winfinite-recursion], with a note pointing at the call. That warning is new in GCC 12.

So a missing base case can look like a time limit, an output error or a memory limit. -Wall names the real problem before you run.

#include <stdio.h>

void stars(int n);

int main(void)
{
    stars(3);
    printf("\n");
    return 0;
}

void stars(int n)
{
    if (n == 0) {
        return;
    }
    printf("*");
    stars(n - 1);
}

***

#include <stdio.h>

long long pyramid(int layers);

int main(void)
{
    printf("4 layers: %lld oranges\n", pyramid(4));
    printf("10 layers: %lld oranges\n", pyramid(10));
    return 0;
}

long long pyramid(int layers)
{
    if (layers == 0) {
        return 0;
    }
    return layers * layers + pyramid(layers - 1);
}

4 layers: 30 oranges
10 layers: 385 oranges

#include <stdio.h>

long long sum_range(int a, int b);

int main(void)
{
    int a = 0;
    int b = 0;

    scanf("%d %d", &a, &b);
    printf("%lld\n", sum_range(a, b));
    return 0;
}

long long sum_range(int a, int b)
{
    if (a > b) {
        return 0;
    }
    return a + sum_range(a + 1, b);
}

25

long long every_other(int n)
{
    if (n == 0) {
        return 0;
    }
    return n + every_other(n - 2);
}

long long sum_to(int n)
{
    if (n == 0) {
        return 0;
    }
    n + sum_to(n - 1);
}

long long factorial(int n)
{
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

#include <stdio.h>

void f(int n);

int main(void)
{
    f(3);
    printf("\n");
    return 0;
}

void f(int n)
{
    if (n == 0) {
        return;
    }
    f(n - 1);
    printf("%d ", n);
}

#include <stdio.h>

long long sum_to(int n);

int main(void)
{
    int n = 0;
    scanf("%d", &n);

    printf("%lld\n", sum_to(n));
    return 0;
}

long long sum_to(int n)
{
    /* The base case comes first: what is the sum of the numbers up to 0?
       Then return n plus one call with a smaller n. */
    return 0;
}

#include <stdio.h>

long long factorial(int n);

int main(void)
{
    int n = 0;

    while (scanf("%d", &n) == 1) {
        printf("%lld\n", factorial(n));
    }
    return 0;
}

long long factorial(int n)
{
    /* The base case comes first. Which n is the smallest one allowed?
       Every other n is n times the factorial of n - 1. */
    return 0;
}

#include <stdio.h>

void down_and_up(int n);

int main(void)
{
    int n = 0;
    scanf("%d", &n);

    down_and_up(n);
    return 0;
}

void down_and_up(int n)
{
    /* One function that prints on both sides of its own call.
       How many times must 1 be printed? */
}

Next, Amara draws the frames on paper, one box per call, and predicts the output before she presses Run.