Ackermann function
The Ackermann function is a classic recursive example in computer science. It is a function that grows very quickly (in its value and in the size of its call tree). It is defined as follows:
You are encouraged to solve this task according to the task description, using any language you may know.
n+1 if m=0
A(m, n) = A(m-1, 1) if m>0 and n=0
A(m-1, A(m,n-1)) if m>0 and n>0
Its arguments are never negative and it always terminates. Write a function which returns the value of A(m, n). Arbitrary precision is preferred (since the funciton grows so quickly), but not required.
Java
<java>public static BigInteger ack(BigInteger m, BigInteger n){ if(m.equals(BigInteger.ZERO)) return n.add(BigInteger.ONE);
if(m.compareTo(BigInteger.ZERO) > 0 && n.equals(BigInteger.ZERO)) return ack(m.subtract(BigInteger.ONE), BigInteger.ONE);
if(m.compareTo(BigInteger.ZERO) > 0 && n.compareTo(BigInteger.ZERO) > 0) return ack(m.subtract(BigInteger.ONE), ack(m, n.subtract(BigInteger.ONE)));
return null; }</java>
Joy
From here
DEFINE
r-ack ==
[ [ [pop null] popd succ ]
[ [null] pop pred 1 r-ack ]
[ [dup pred swap] dip pred r-ack r-ack ] ]
cond.
Python
<python>Python 2.5.1 (r251:54863, May 2 2007, 08:46:07) [GCC 3.3.4 (pre 3.3.5 20040809)] on linux2 IDLE 1.2.1 >>> import sys
>>> def ack(M, N): return ( ( N + 1 ) if M == 0 else ( ( ack(M-1, 1) ) if N == 0 else ( ( ack(M-1, ack(M, N-1)) ) )))
>>> sys.setrecursionlimit(3000) >>> ack(0,0) 1 >>> ack(3,4) 125</python>
SNUSP
/==!/==atoi=@@@-@-----#
| | Ackermann function
| | /=========\!==\!====\ recursion:
$,@/>,@/==ack=!\?\<+# | | | A(0,j) -> j+1
j i \<?\+>-@/# | | A(i,0) -> A(i-1,1)
\@\>@\->@/@\<-@/# A(i,j) -> A(i-1,A(i,j-1))
| | |
# # | | | /+<<<-\
/-<<+>>\!=/ \=====|==!/========?\>>>=?/<<#
? ? | \<<<+>+>>-/
\>>+<<-/!==========/
# #