# Ackermann function (Forth)

The **Ackermann function** or **Ackermann-Péter function** is defined recursively for non-negative integers *m* and *n* as follows:

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 ) ?dupifackermann (m>0)elseackermann (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?dupifackermann (m>0 n>0)elseackermann (m>0 n=0)thenswap1-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 **swap**ped *m* and *n* so the stack currently has ( m n ).

ackermann (m>0 n>0)= 1-overrecurse

Download code |