Problem Statement

The Ackermann function is a classic example of a recursive function, notable especially because it is not a primitive recursive function. It grows very quickly in value, as does the size of its call tree.

The Ackermann function is usually defined as follows:

Its arguments are never negative and it always terminates.

Write a function which returns the value of

A ( m , n )

{\displaystyle A(m,n)}

. Arbitrary precision is preferred (since the function grows so quickly), but not required.

Let's start with the solution:

fn ackermann(m int, n int ) int {
    if m == 0 {
        return n + 1
    }
    else if n == 0 {
        return ackermann(m - 1, 1)
    }
    return ackermann(m - 1, ackermann(m, n - 1) )
}

fn main() {
    for m := 0; m <= 4; m++ {
        for n := 0; n < ( 6 - m ); n++ {
            println('Ackermann($m, $n) = ${ackermann(m, n)}')
        }
    }
}