The Ackermann function is a classic example of a recursive function, notable especially because it is not a primitive recursive function. It grows very quickly in value, as does the size of its call tree.



The Ackermann function is usually defined as follows:







A
(
m
,
n
)
=


{



n
+
1



if 

m
=
0




A
(
m
−
1
,
1
)



if 

m
>
0

 and 

n
=
0




A
(
m
−
1
,
A
(
m
,
n
−
1
)
)



if 

m
>
0

 and 

n
>
0.








{\displaystyle A(m,n)={\begin{cases}n+1&{\mbox{if }}m=0\\A(m-1,1)&{\mbox{if }}m>0{\mbox{ and }}n=0\\A(m-1,A(m,n-1))&{\mbox{if }}m>0{\mbox{ and }}n>0.\end{cases}}}






Its arguments are never negative and it always terminates.



Task

Write a function which returns the value of 



A
(
m
,
n
)


{\displaystyle A(m,n)}

. Arbitrary precision is preferred (since the function grows so quickly), but not required.



See also

 Conway chained arrow notation for the Ackermann function.


go =>
    foreach(M in 0..3)
        println([m=M,[a(M,N) : N in 0..16]])
    end,
    nl,
    printf("a2(4,1): %d\n", a2(4,1)),
    nl,
    time(check_larger(3,10000)),
    nl,
    time(check_larger(4,2)),
    nl.
 
% Using a2/2 and chop off large output
check_larger(M,N) => 
    printf("a2(%d,%d): ", M,N),
    A = a2(M,N).to_string,
    Len = A.len,
    if Len < 50 then
      println(A)
    else 
      println(A[1..20] ++ ".." ++ A[Len-20..Len])
    end,
    println(digits=Len).
 
% Plain tabled (memoized) version with guards
table
a(0, N) = N+1 => true.
a(M, 0) = a(M-1,1), M > 0 => true.
a(M, N) = a(M-1,a(M, N-1)), M > 0, N > 0 => true.
 
% Faster and pure function version (no guards). 
% (Based on Python example.)
table
a2(0,N) = N + 1.
a2(1,N) = N + 2.
a2(2,N) = 2*N + 3.
a2(3,N) = 8*(2**N - 1) + 5.
a2(M,N) = cond(N == 0,a2(M-1, 1), a2(M-1, a2(M, N-1))).
 