The Ackerman function is a famous example in computer science and mathematics. It is mentioned in your syllabus because it is the "ultimate" example of recursion.

Its main properties are:

·         It is a very simple function to define.

·         It is computable (a computer can, in theory, find the answer).

·         It grows unimaginably fast—faster than factorials, faster than exponentiation (e.g., nn), faster than any function you've probably ever seen.

·         It is the classic example of a function that is "computable" but not "primitive recursive." This is an advanced topic, but it basically means the function is too complex to be solved using only simple for loops. It *requires* a more powerful form of recursion.

The function is defined as A(m, n) and has three rules, all of which are recursive base cases or recursive steps.

Rule 1 (Base Case): If m = 0:

A(0, n) = n + 1

Rule 2 (Recursive Step 1): If m > 0 and n = 0:

A(m, 0) = A(m - 1, 1)

Rule 3 (Recursive Step 2): If m > 0 and n > 0:

A(m, n) = A(m - 1, A(m, n - 1))

Notice that Rule 3 is a double recursion, and the inner recursive call, A(m, n - 1), must be solved *before* the outer call can even begin. This nesting is what causes the explosive growth.

The C code is almost a direct, 1-to-1 translation of the mathematical definition. We use unsigned int because the function is only defined for non-negative integers.

/*

 * Example: The Ackerman function in C.

 * WARNING: Do not try to compute this for large numbers!

 * Even A(4, 2) is too large for a computer to handle.

 */

#include <stdio.h>

// Use 'unsigned int' as the function is for non-negative integers

unsigned int ackerman(unsigned int m, unsigned int n) {

    // Rule 1: A(0, n) = n + 1

    if (m == 0) {

        return n + 1;

    }

    // Rule 2: A(m, 0) = A(m - 1, 1)

    else if (m > 0 && n == 0) {

        return ackerman(m - 1, 1);

    }

    // Rule 3: A(m, n) = A(m - 1, A(m, n - 1))

    else { // m > 0 and n > 0

        return ackerman(m - 1, ackerman(m, n - 1));

    }

}

int main() {

    // We can only compute a few, very small values.

    printf("A(0, 5) = %u\n", ackerman(0, 5)); // Rule 1

    printf("A(1, 2) = %u\n", ackerman(1, 2));

    printf("A(2, 2) = %u\n", ackerman(2, 2));

    printf("A(3, 3) = %u\n", ackerman(3, 3));

    // *** DANGER ZONE ***

    // The line below will likely crash your program (Stack Overflow)

    // or run for an impossibly long time. DO NOT RUN IT.

    // printf("A(4, 2) = %u\n", ackerman(4, 2));

    return 0;

}

The best way to understand the Ackerman function is to see what it "unrolls" into for each level of m.

Let's look at the numbers this produces. Even for m=4, the numbers are beyond comprehension:

·         A(4, 0) = A(3, 1) = 2(1+3) - 3 = 24 - 3 = 16 - 3 = 13

·         A(4, 1) = A(3, A(4, 0)) = A(3, 13) = 2(13+3) - 3 = 216 - 3 = 65,536 - 3 = 65,533

·         A(4, 2) = A(3, A(4, 1)) = A(3, 65,533) = 2(65,533+3) - 3 = 2^65,536 - 3

How big is 2^65,536?

This number is so large that it cannot be written down. It has 19,729 digits.

For comparison, the number of atoms in the entire observable universe is estimated to be 1080 (a 1 with 80 zeros). A(4, 2) is a number with 19,729 zeros (when written in binary). It is astronomically larger.

And that's just A(4, 2). The value A(4, 3) is so large that A(4, 2) looks like zero in comparison.

You are not asked to learn the Ackerman function to *use* it. You learn it for three reasons:

1.    It's a perfect example of recursion: It shows how a few simple recursive rules can create unbelievably complex behavior.

2.    It shows the danger of recursion: This function will cause a Stack Overflow (the program runs out of memory for function calls) almost immediately. It teaches you to be careful and to *always* have a simple, reachable base case.

3.    It's a limit case: It proves that some problems, while "simple" to write, are not "simple" to solve. It shows the very boundary of what is practically computable.