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.


(defmacro defmemofun (name (. args) . body)
  (let ((hash (gensym "hash-"))
        (argl (gensym "args-"))
        (hent (gensym "hent-"))
        (uniq (copy-str "uniq")))
    ^(let ((,hash (hash :equal-based)))
       (defun ,name (,*args)
         (let* ((,argl (list ,*args))
                (,hent (inhash ,hash ,argl ,uniq)))
           (if (eq (cdr ,hent) ,uniq)
             (set (cdr ,hent) (block ,name (progn ,*body)))
             (cdr ,hent)))))))
 
(defmemofun ack (m n)
  (cond
    ((= m 0) (+ n 1))
    ((= n 0) (ack (- m 1) 1))
    (t (ack (- m 1) (ack m (- n 1))))))
 
(each ((i (range 0 3)))
  (each ((j (range 0 4)))
    (format t "ack(~a, ~a) = ~a\n" i j (ack i j))))