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:

Public Function Ackermann(m As Float, n As Float) As Float
  If m = 0 Then
    Return n + 1
  End If
  If n = 0 Then
    Return Ackermann(m - 1, 1)
  End If
  Return Ackermann(m - 1, Ackermann(m, n - 1))
End

Public Sub Main()
  Dim m, n As Float
  For m = 0 To 3
    For n = 0 To 4
      Print "Ackermann("; m; ", "; n; ") = "; Ackermann(m, n)
    Next
  Next
End