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:

GET "libhdr"

LET ack(m, n) = m=0 -> n+1,
                n=0 -> ack(m-1, 1),
                ack(m-1, ack(m, n-1))

LET start() = VALOF
{ FOR i = 0 TO 6 FOR m = 0 TO 3 DO
    writef("ack(%n, %n) = %n*n", m, n, ack(m,n))
  RESULTIS 0
}