Ackermann function (Forth)
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 else 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, ...).
= swap ?dup if else then swap 1- recurse
If n=0, the second parameter is simply one. ?dup had already eaten the zero argument.
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 ).
= 1- over recurse