The Ackermann Function is a simple recursive function that produces incredibly large values with very simple inputs. Here is a short description, a way to calculate some of its values using simple formulas, and a very large number.

This is the definition of the function, A(m, n):

m = 0	A(0, n) = n+1
m > 0, n = 0	A(m, 0) = A(m-1, 1)
m > 0, n > 0	A(m, n) = A(m-1, A(m, n-1))

This can be easily implemented in any programming language. Calculating some values for the first four lines yields the following table:

	n
m	0	1	2	3	4	5	6	7	8	9	10
0	1	2	3	4	5	6	7	8	9	10	11
1	2	3	4	5	6	7	8	9	10	11	12
2	3	5	7	9	11	13	15	17	19	21	23
3	5	13	29	61	125	253	509	1021	2045	4093	8189

This is the table that can be found in many books on programming and/or recursion. The Ackermann function is more like an array than a usual function, the results of lower recursion levels are used to access other parts of the array. This is easy to see when writing the function slightly differently, with square brackets instead of parentheses (i.e., using a notation similar to C, Java, etc.):

m = 0	A[0, n] = n+1
m > 0, n = 0	A[m, 0] = A[m-1, 1]
m > 0, n > 0	A[m, n] = A[m-1, A[m, n-1]]

The first line can be thought of as the initialization for line 0 of the array, and it appears that this function contains hardly any calculations of actual values, but mostly of their indices. Coding this into a computer program is pretty straight-forward, but the range of values that can be computes using most programming languages is rather limited. It also takes surprisingly long to calculate the numbers in the third row, because the number of recursive steps is considerable.

Looking at the array of numbers above, the first three lines follow simple patterns that could be expressed as simple, non-recursive formulas. The fourth line (m=3) shows a much more interesting behavior, though. Suddenly, the numbers grow very quickly, in fact, they more than double from n to n+1.

Using the table above, it is possible to derive functions that calculate the values of A(m, n) for fixed values of m from 0 to 3 (where 'x^y' stands for 'x to the power of y'):

m	A(m, n) = f(n)
0	A(0, n) = n+1
1	A(1, n) = n+2
2	A(2, n) = 3+2*n
3	A(3, n) = 5+8*(2^n-1)

Using these formulas, these values can all be calculated in constant time, rather than with a complexity that is growing rapidly with m and n. In practice, the values quickly exceed 2^32-1, which is the limit for integers in many programming languages. Using the formulas above, we can easily find out the largest n for any largest number that can be represented, L ('ld' is the 'logarithmus dualis', the base 2 logarithm). The right column in the following table lists the values for L=2^32-1 and L=2^64-1 (i.e., 32-bit and 64-bit integers):

m	A(m, n) < L <=>	A(m, n) < 2^32-1 <=>	A(m, n) < 2^64-1 <=>
0	n <= L-1	n <= 2^32-2	n <= 2^64-2
1	n <= L-2	n <= 2^32-3	n <= 2^64-3
2	n <= (L-3)/2	n <= 2147483646 = 2^31-2	n <= (2^64-3)/2 ~ 2^63
3	n <= ld((L-5)/8+1)	n <= 29	n <= 61

Not surprisingly, using 64 bits does not buy much room for larger values of n on the fourth line. Also, we still only have formulas for values of m up to three. Using the table from the very top of this article, we see that A(4, n) = A(3, A(4, n-1)), and if n-1 = 0, we can use A(m, 0) = A(m-1, 1), so A(4, 0) = A(3, 1) – which we can look up in the second table or calculate easily.

Using this results, we find that A(4, 0) = 13. A(4, 1) is a lot larger, A(4, 1) = A(3, A(4, 0)) = A(3, 13) = 65533. It gets interesting with A(4, 2) = A(3, A(4, 1)) = A(3, 65533) = 5+8*(2^65533-1). The result is a number with 19729 digits! We can go one line further, to A(5, 0) = A(4, 1) = 65533, but A(5, 2) = A(4, A(5, 1)) = A(4, 65533) which is far beyond our reach, we can't even calculate A(4, 3) = A(3, A(4, 2))!
This is also true for A(6, 0) = A(5, 1) - which means, that we can't calculate a single value from the seventh line, or those beyond! So this is the final table (A(4, 2) links to the actual number):

	n
m	0	1	2	3	4	5	6	7	8	9
0	1	2	3	4	5	6	7	8	9	10
1	2	3	4	5	6	7	8	9	10	11
2	3	5	7	9	11	13	15	17	19	21
3	5	13	29	61	125	253	509	1021	2045	4093
4	13	65533	A(4, 2)
5	65533

Programs

The following programs were used to calculate the numbers above, including A(4, 2). They were written in LISP, for its ability to work with arbitrarily large numbers; the LISP interpreter I used was CLISP, which is freeware, and runs on many operating systems. Please note that Emacs LISP is not able to handle large numbers, so anything above A(3, 29) will not work.

Here is the basic program using the simple formulas for m <= 3:

(defun ackermann (m n) "The Ackermann Function"
(cond ((= m 0) (+ n 1))
      ((= m 1) (+ n 2))
      ((= m 2) (+ 3 (* n 2)))
      ((= m 3) (+ 5 (* 8 (- (expt 2 n) 1))))
      (t (cond ((= n 0) (ackermann (- m 1) 1))
               (t (ackermann (- m 1) (ackermann m (- n 1))))
         ))
))

It is run using the following line, with m and n replaced with numbers:

(ackermann m n)

The following function is used for counting the number of digits in a number, and is very inefficient and also horrible LISP style. It gets the job done, though:

(defun digits (num) "number of digits of num"
(setq a 0)
(loop
 (setq a (+ a 1))
 (setq num (floor (/ num 10)))
 (when (= num 0) (return a))
))

Invoking it with

(digits (ackermann m n))

will return the number of digits of A(m, n).