Indirect and nested recursion

Is 4 even? It is if 3 is odd. Is 3 odd? It is if 2 is even. So two functions can answer by asking each other, back and forth, until one reaches 0. The program below does that first. Then it runs a stranger function, one whose recursive call takes another recursive call as its argument. Watch the colours of the cards, then watch the order in which the A cards come and go.

1#include <stdbool.h>2#include <stdio.h>3 4bool is_odd(int n);5 6bool is_even(int n)7{8    if (n == 0)9        return true;10    return is_odd(n - 1);11}12 13bool is_odd(int n)14{15    if (n == 0)16        return false;17    return is_even(n - 1);18}19 20int ack(int m, int n)21{22    if (m == 0)23        return n + 1;24    if (n == 0)25        return ack(m - 1, 1);26    int inner = ack(m, n - 1);27    return ack(m - 1, inner);28}29 30int main(void)31{32    bool e = is_even(4);33    printf("is_even(4) = %d\n", e);34    int a = ack(2, 1);35    printf("A(2, 1) = %d\n", a);36    return 0;37}

Two functions that call each other

Here are the two functions:

bool is_odd(int n);

bool is_even(int n)
{
    if (n == 0)
        return true;
    return is_odd(n - 1);
}

bool is_odd(int n)
{
    if (n == 0)
        return false;
    return is_even(n - 1);
}

Neither calls itself. is_even calls is_odd, and is_odd calls is_even. Together they are still recursive, because a call of is_even leads, through is_odd, to another call of is_even on a smaller n. This is indirect recursion, or mutual recursion.

In the clip the cards alternate in two colours: is_even(4), is_odd(3), is_even(2), is_odd(1), is_even(0). That is five calls, three of is_even and two of is_odd. is_even(0) answers true. Every other call returns whatever the call it made returned, so true travels back up unchanged, and is_even(4) is true. printf prints a bool as a number, so the program prints is_even(4) = 1.

The code and its cost

Calling a function before it is defined

C reads a file from top to bottom, and it must know a function’s name, its parameters and its return type before the first call to it. is_even calls is_odd, which is defined below it. So the program declares is_odd first, with one line and no body:

bool is_odd(int n);

This line is a prototype. It promises that is_odd exists and says how to call it; the body comes later. With it, the order of the two definitions no longer matters. A function does not have to be defined above every call to it, only declared.

bool, true and false come from <stdbool.h>, the first line of the program.

A call inside a call

The second part of the program is Ackermann’s function, A(m, n):

int ack(int m, int n)
{
    if (m == 0)
        return n + 1;
    if (n == 0)
        return ack(m - 1, 1);
    int inner = ack(m, n - 1);
    return ack(m - 1, inner);
}

The last two lines say A(m, n) = A(m − 1, A(m, n − 1)): a recursive call whose argument is another recursive call. This is nested recursion. As usual on this course, the inner result is stored in its own variable first, so the order is plain to see.

The outer call cannot start until its argument is known. Watch A(2, 1) in the clip. It first calls A(2, 0), its inner call, and waits with inner ”?”. A whole tower of cards rises and falls above it. Only when A(2, 0) has returned 3, and 3 has flown into inner, does the card for the outer call, A(1, 3), appear.

Watch, too, how the cards leave. The outer call return ack(m - 1, inner); is a tail call, as in Head and tail recursion (4.2): once it answers, the card that made it has nothing left to do. So in this build a card that made its outer call leaves at the same moment as the call it waited on, and at the end three cards go together as A(0, 4) answers 5.

How many calls

The fixture counts 14 calls of ack for A(2, 1), and at most 6 of its frames on the stack at once. We can check the 14 by hand. A(1, n) takes 2n + 2 calls, A(2, 0) takes 1 + 4 = 5 (itself and the 4 of A(1, 1)), and A(2, 1) takes itself, the 5 of A(2, 0) and the 8 of A(1, 3): 1 + 5 + 8 = 14.

The values grow fast. Working the rule out for each m:

A(4, 2) has 19,729 digits. A(4, 3) could not be written down with every atom in the universe.

Each row is built, roughly, by repeating the row above: adding 1 repeated gives adding, adding repeated gives multiplying by 2, and so on up to towers of powers. A function written with a fixed number of nested loops can only climb a fixed number of these steps. Ackermann’s function climbs one more step for each step of m, so it grows faster than any fixed nest of loops.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic mutual.c -o mutual
./mutual

It prints is_even(4) = 1, then A(2, 1) = 5.

Worked example

is_odd(3) by hand. is_odd(3) asks is_even(2), which asks is_odd(1), which asks is_even(0), which answers true. That true comes back unchanged through all of them, so 3 is odd: 4 calls. Before you read on: what does is_even(7) return, and in how many calls? (False, in 8 calls: n goes 7, 6, …, 0, and the call that reaches 0 is is_odd(0), which answers false.)

A(1, 2) by hand. Write each call and what it needs:

• A(1, 2) needs inner = A(1, 1) first.
• A(1, 1) needs inner = A(1, 0) first. A(1, 0) is A(0, 1) = 2.
• So A(1, 1) = A(0, 2) = 3.
• So A(1, 2) = A(0, 3) = 4.

The calls were A(1, 2), A(1, 1), A(1, 0), A(0, 1), A(0, 2) and A(0, 3): 6 calls, as 2n + 2 says for n = 2. The program ack-calls.c counts them and agrees: A(1, 2) = 4 in 6 calls. It also runs A(2, 2): A(2, 2) = 7 in 27 calls.

A(3, 3). The table says 2⁶ − 3 = 61. Counting the calls is harder by hand; ack33.c counts them while it runs: A(3, 3) = 61 in 2432 calls. One step up in m, and the 14 calls of A(2, 1) become thousands.

Where it’s used

Parsers. In arithmetic, an expression is made of terms added together, a term is made of factors multiplied together, and a factor can be a whole expression in brackets. A parser that reads such text has one function for each, and they call each other in a circle, exactly like is_even and is_odd.

State machines. A program that moves between a few states, such as “reading a word” and “reading spaces”, can be written as one function per state, each calling the function of the next state.

Testing compilers. Ackermann’s function makes a huge number of small calls, so it is used to test how well a compiler handles function calls and deep stacks.

Union–find. Ackermann’s function has an inverse, which grows so slowly that it is below 5 for any input that could fit in a computer. The cost of union–find (19.7) is stated with this inverse, which is why it is called almost constant time.

Reference card

Platform: C11, gcc on x86-64 Linux; bool from <stdbool.h>, printed as 0 or 1. The cards in the picture show names and values only.