Ackermann function
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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.
Ada
<ada> with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Ackermann is
function Ackermann (M, N : Natural) return Natural is begin if M = 0 then return N + 1; elsif N = 0 then return Ackermann (M - 1, 1); else return Ackermann (M - 1, Ackermann (M, N - 1)); end if; end Ackermann;
begin
for M in 0..3 loop for N in 0..6 loop Put (Natural'Image (Ackermann (M, N))); end loop; New_Line; end loop;
end Test_Ackermann; </ada> The implementation does not care about arbitrary precision numbers because the Ackermann function does not only grow, but also slow quickly, when computed recursively. The example outputs first 4x7 Ackermann's numbers:
1 2 3 4 5 6 7 2 3 4 5 6 7 8 3 5 7 9 11 13 15 5 13 29 61 125 253 509
ALGOL 68
PROC test ackermann = VOID: BEGIN PROC ackermann = (INT m, n)INT: BEGIN IF m = 0 THEN n + 1 ELIF n = 0 THEN ackermann (m - 1, 1) ELSE ackermann (m - 1, ackermann (m, n - 1)) FI END # ackermann #; FOR m FROM 0 TO 3 DO FOR n FROM 0 TO 6 DO print(ackermann (m, n)) OD; new line(stand out) OD END # test ackermann #; test ackermann
Output:
+1 +2 +3 +4 +5 +6 +7 +2 +3 +4 +5 +6 +7 +8 +3 +5 +7 +9 +11 +13 +15 +5 +13 +29 +61 +125 +253 +509
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.
Lucid
ack(m,n) where ack(m,n) = if m eq 0 then n+1 else if n eq 0 then ack(m-1,1) else ack(m-1, ack(m, n-1)) fi fi; end
MAXScript
Use with caution. Will cause a stack overflow for m > 3.
fn ackermann m n = ( if m == 0 then ( return n + 1 ) else if n == 0 then ( ackermann (m-1) 1 ) else ( ackermann (m-1) (ackermann m (n-1)) ) )
OCaml
<ocaml>let rec a m n =
if m=0 then (n+1) else if n=0 then (a (m-1) 1) else (a (m-1) (a m (n-1)))</ocaml>
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>
Ruby
Adapted from Ada's version. def ack(m, n)
if m == 0 n + 1 elsif n == 0 ack(m-1, 1) else ack(m-1, ack(m, n-1)) end
end Example: (0..3).each do |m|
(0..6).each { |n| print ack(m, n), ' ' } puts
end Output:
1 2 3 4 5 6 7 2 3 4 5 6 7 8 3 5 7 9 11 13 15 5 13 29 61 125 253 509
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)) | | | # # | | | /+<<<-\ /-<<+>>\!=/ \=====|==!/========?\>>>=?/<<# ? ? | \<<<+>+>>-/ \>>+<<-/!==========/ # #
One could employ tail recursion elimination by replacing "@/#" with "/" in two places above.
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].