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.


 
section .text
 
global _main
_main:
    mov eax, 3 ;m
    mov ebx, 4 ;n
    call ack ;returns number in ebx
    ret
 
ack:
    cmp eax, 0
    je M0 ;if M == 0
    cmp ebx, 0
    je N0 ;if N == 0
    dec ebx ;else N-1
    push eax ;save M
    call ack1 ;ack(m,n) -> returned in ebx so no further instructions needed
    pop eax ;restore M
    dec eax ;M - 1
    call ack1 ;return ack(m-1,ack(m,n-1))
    ret
    M0:
        inc ebx ;return n + 1
        ret
    N0:
        dec eax
        inc ebx ;ebx always 0: inc -> ebx = 1
        call ack1 ;return ack(M-1,1)
        ret
 