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:

// To use recursion definition and declaration must be on separate lines
var Ackermann 
Ackermann = Fn.new {|m, n|
    if (m == 0) return n + 1
    if (n == 0) return Ackermann.call(m - 1, 1)
    return Ackermann.call(m - 1, Ackermann.call(m, n - 1))
}

var pairs = [ [1, 3], [2, 3], [3, 3], [1, 5], [2, 5], [3, 5] ]
for (pair in pairs) {
    var p1 = pair[0]
    var p2 = pair[1]
    System.print("A[%(p1), %(p2)] = %(Ackermann.call(p1, p2))")
}