User Tools

Site Tools


Deeply Recursive Ackermann Function with Memoization

Wilhelm Ackermann explored recursive functions, such as Fibonacci, but looked further at much more complicated, potentially doubly recursive functions. He invented the Ackermann Function, which grows memory and stack use (much!) faster than exponential. More recently, people have sped up the evaluation of the Ackermann function by memoization. Recognizing that such a deeply recursive algorithm often covers the same evaluations many, many times, memoization stores evaluated results, and allows a non-naive algorithm to determine whether further recursion is needed. This mmBasic implementation uses memoization to evaluate the Ackermann function. Because of the design of the function, evaluation grows much faster “vertically” than “horizontally”. The Ackermann memoization array is defined five times deeper than it is wide. mmBasic's own implementation limits recursive calls to ~100 deep. Once it gets that deep, the program will crash.

' ***************************************************************************\\
'   Deeply Recursive Ackermann Sequence using Memoization in MMBasic
'   See for more information
'   Steven F. Johnson                                          September 2020
'   A(m, n):  m = 0	    A(0, n) = n+1                (No recursion    )
'             m > 0, n = 0  A(m, 0) = A(m-1, 1)          (Single recursion)
'             Otherwise     A(m, n) = A(m-1, A(m, n-1))  (Double recursion)
' ***************************************************************************

' **********  Initialization Section   **************************************
Dim INTEGER i, j, MemAck(20,1000)' Allocate space for Results

For i=0 to 19
  For j=0 to 999
    MemAck(i,j)=-99  ' indicate that this is not yet evaluated
  Next j
Next i

' **********   Function Definitions   ***************************************
Function Ack(m, n) As INTEGER ' Implements Ackermann Function

  If (m=0) Then                        ' Simplest case - no recursion
    MemAck(m,n) = n+1                  ' Memoize it!
  ElseIf ((m>0) And (n=0)) Then        ' Medium case - single recursion
    If MemAck(m-1,1) < 0 Then          ' Check to see if value already there
      MemAck(m,n) = Ack(m-1,1)         ' Calculate, then Memoize it
      MemAck(m,n) = MemAck(m-1,1)      ' Memoize the existing value

  Else                                 ' Most complicated - potential double recursion
    If MemAck(m, n-1) < 0 Then MemAck(m, n-1) = Ack(m, n-1)                                        ' See if Right Hand already evaluated
    If MemAck(m-1, MemAck(m, n-1)) < 0 Then MemAck(m-1, MemAck(m, n-1)) = Ack(m-1, MemAck(m, n-1)) ' Check for Left Hand value
    MemAck(m,n) = MemAck(m-1,MemAck(m, n-1))                                                       ' Memoize it!


  Ack = MemAck(m,n)                    ' Set return value for function to memoized value

End Function

' **********   Main Body of Program   ***************************************

Print "Press Ctrl-C to interrupt execution"

For i = 0 to 9
  For j = 0 to 9
    Print "   Ack("; i; ", "; j; " ): "; Ack(i,j)
  Next j
Next i

mmbasic/deeply_recursive_ackermann_function_with_memoization.txt · Last modified: 2024/01/19 09:30 by