Ackermann function (Forth)
From LiteratePrograms
The Ackermann function or Ackermann-Péter function is defined recursively for non-negative integers m and n as follows:
- 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases}"/>
In the theory of computation, the Ackermann function is a simple example of a recursive function that is not primitively recursive. Note that this function grows very quickly -- even A(4, 3) cannot be feasibly computed on ordinary computers.
This is a simple recursive version of the Ackermann function. Cell sized integers are used, so stack and integer overflow is likely. The function is easiest to implement and most stack efficient if the parameter m is on top of the stack.
<<ackermann.f>>= : ack ( n m -- a ) ?dup if ackermann (m>0) else ackermann (m=0) then ; 2 3 ack . \ 29
The easy case: m=0. The use of ?dup earlier has already thrown the zero argument away. The return value is the second argument incremented.
<<ackermann (m=0)>>= 1+
When m>0, we will be invoking the Ackermann function recursively, with different behavior depending on whether n>0. swap ?dup brings n to the top to be examined. Afterward, swap 1- recurse calls Ackermann(m-1, ...).
ackermann (m>0)= swap ?dup if ackermann (m>0 n>0) else ackermann (m>0 n=0) then swap 1- recurse
If n=0, the second parameter is simply one. ?dup had already eaten the zero argument.
ackermann (m>0 n=0)=
1
If n>0, the second parameter is a further recursive call to Ackermann(m, n-1). We had previously swapped m and n so the stack currently has ( m n ).
ackermann (m>0 n>0)=
1- over recurse