Ackermann–Péter function (2 arguments) - C/C++ - Recursive Implentation

Posted on by Kenny Cason
tags = [ ackermann, ackermann–péter, function, mathematics, recursive, total computable, wilhelm ]

This is an implementation of the 2 argument version of the Ackermann Function (i.e. Ackermann-Péter function). In essence, this is an example of a very simple recursive function is an example of a total computable function that is not primitive recursive. Instead of making the internet even more redundant with unnecessary text, just click the above link to view the entire Wikipedia article. Function’s like these are very fun to play with. I often think about the human brain and how it functions when I see these kinds of functions. Taking input from the environment and processing it, sometimes recursively (like in a thought cycle), then converging to some or many outputs. C Implentation: noteThis function grows extremely fast, such that it quickly out grows any primitive type in C, including the largest “unsigned long long” type. Though the program will likely crash with a 0xC0000005 error from too much recursion :) It should run fine from A(0,0) to A(4,0) and likely crash while computing A(4,1), which is 65533. A(4,0) is 13, so the number of recursive calls jumps up enormously! I will be working on a custom, larger data type as well as a way around the error caused by too much recursion.

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * Ackermann function - recursive implementation
 */
unsigned long long A(unsigned long long m, unsigned long long n) {
    if(m == 0) {
        return n + 1;
    }else if(n == 0) {
        return A(m - 1, 1);
    } else {
        return A(m - 1, A(m, n - 1));
    }
}
The entire source implentation can be found here I obtained a list of some of the expected values from this site -> http://www-users.cs.york.ac.uk/susan/cyc/a/ackermnn.htm Here are some of the values for 0 < m < 5, 0 < n < 6
n=0 n=1 n=2 n=3 n=4 n=5
m=0 1 2 3 4 5 6
m=1 2 3 4 5 6 7
m=2 3 5 7 9 11 13
m=3 5 13 29 61 125 253
m=4 13 65533 265536-3 2265536-3 A(3,2265536-3) A(3,A(4,4))


Some of the patterns formed are very amazing. For example: A(2, n), 0 <= n < infinite, will list odd numbers starting from 3 to infinite. To demonstrate this just insert the below loop into your code:

1
2
3
for(int n = 0; n < 100; n++) {
      std::cout << "A(2, " << n << ") = " << A(2, n) << std::endl;
}
comments powered by Disqus