Page History: Deeply Recursive Ackermann Function with Memoization
Compare Page Revisions
Page Revision: 2020/09/13 02:34
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 https://en.wikipedia.org/wiki/Ackermann_function 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 **************************************
Option BASE 0 : OPTION EXPLICIT
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 : 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
Else
MemAck(m,n) = MemAck(m-1,1) ' Memoize the existing value
EndIf
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 there
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!
Endif
Ack = MemAck(m,n) ' Set return value for function to memoized value
End Function
' ********** Main Body of Program ***************************************
CLS
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
End