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.


 
\ Ackermann function, illustrating use of "memoization".
 
\ Memoization is a technique whereby intermediate computed values are stored
\ away against later need.  It is particularly valuable when calculating those
\ values is time or resource intensive, as with the Ackermann function.
 
\ make the stack much bigger so this can complete!
100000 stack-size
 
\ This is where memoized values are stored:
{} var, dict
 
\ Simple accessor words
: dict! \ "key" val --
  dict @ -rot m:! drop ;
 
: dict@ \ "key" -- val
  dict @ swap m:@ nip ;
 
defer: ack1
 
\ We just jam the string representation of the two numbers together for a key:
: makeKey  \ m n -- m n key
	2dup >s swap >s s:+ ;
 
: ack2 \ m n -- A
	makeKey dup
	dict@ null?
	if \ can't find key in dict
		\ m n key null
		drop \ m n key
		-rot \ key m n
		ack1 \ key A
		tuck \ A key A
		dict! \ A
	else \ found value
		\ m n key value
		>r drop 2drop r>
	then ;
 
: ack \ m n -- A
	over not 
	if
		nip n:1+
	else
		dup not
		if
			drop n:1- 1 ack2
		else
			over swap n:1- ack2
			swap n:1- swap ack2
		then
	then ;
 
' ack is ack1
 
: ackOf \ m n --
        2dup
        "Ack(" . swap . ", " . . ") = " . ack . cr ;
 
 
0 0 ackOf
0 4 ackOf
1 0 ackOf
1 1 ackOf
2 1 ackOf
2 2 ackOf
3 1 ackOf
3 3 ackOf
4 0 ackOf
 
\ this last requires a very large data stack.  So start 8th with a parameter '-k 100000'
4 1 ackOf
 
bye