Ackermann function
You are encouraged to solve this task according to the task description, using any language you may know.
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:
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.
Erlang
-module(main). -export([main/1]). main( [ A | [ B |[]]]) -> io:fwrite("~p~n",[ack(toi(A),toi(B))]). toi(E) -> element(1,string:to_integer(E)). ack(0,N) -> N + 1; ack(M,0) -> ack(M-1, 1); ack(M,N) -> ack(M-1,ack(M,N-1)).
It can be used with
|escript ./ack.erl 3 4 =125
Forth
: ack ( j i -- a ) ?dup if swap ?dup if 1- over recurse else 1 then swap 1- recurse else 1+ then ;
Haskell
ack 0 n = n + 1 ack m 0 = ack (m-1) 1 ack m n = ack (m-1) (ack m (n-1))
Example of use
Prelude> ack 0 0 1 Prelude> ack 3 4 125
J
As posted at the J wiki
ack=: c1`c1`c2`c3 @. (#.@(,&*)) c1=: >:@] NB. if 0=x, 1+y c2=: <:@[ ack 1: NB. if 0=y, (x-1) ack 1 c3=: <:@[ ack [ ack <:@] NB. else, (x-1) ack x ack y-1
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 ack == [ [ [pop null] popd succ ] [ [null] pop pred 1 ack ] [ [dup pred swap] dip pred ack ack ] ] cond.
another using a combinator
DEFINE ack == [ [ [0 =] [pop 1 +] ] [ [swap 0 =] [popd 1 - 1 swap] [] ] [ [dup rollup [1 -] dip] [swap 1 - ack] ] ] condlinrec.
Python
<python>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)))</python>
Example of use<python>>>> import sys >>> 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)) | | | # # | | | /+<<<-\ /-<<+>>\!=/ \=====|==!/========?\>>>=?/<<# ? ? | \<<<+>+>>-/ \>>+<<-/!==========/ # #
V
[ack [ [pop zero?] [popd succ] [zero?] [pop pred 1 ack] [true] [[dup pred swap] dip pred ack ack ] ] when].
using destructuring view
[ack [ [pop zero?] [ [m n : [n succ]] view i] [zero?] [ [m n : [m pred 1 ack]] view i] [true] [ [m n : [m pred m n pred ack ack]] view i] ] when].