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 for Motorola 68000 under AmigaOs 2+ by Thorham
;
; Set stack space to 60000 for m = 3, n = 5.
;
; The program will print the ackermann values for the range m = 0..3, n = 0..5
;
_LVOOpenLibrary equ -552
_LVOCloseLibrary equ -414
_LVOVPrintf equ -954
 
m equ 3 ; Nr of iterations for the main loop.
n equ 5 ; Do NOT set them higher, or it will take hours to complete on
        ; 68k, not to mention that the stack usage will become astronomical.
        ; Perhaps n can be a little higher... If you do increase the ranges
        ; then don't forget to increase the stack size.
 
execBase=4
 
start
    move.l  execBase,a6
 
    lea     dosName,a1
    moveq   #36,d0
    jsr     _LVOOpenLibrary(a6)
    move.l  d0,dosBase
    beq     exit
 
    move.l  dosBase,a6
    lea     printfArgs,a2
 
    clr.l   d3 ; m
.loopn
    clr.l   d4 ; n
.loopm
    bsr     ackermann
 
    move.l  d3,0(a2)
    move.l  d4,4(a2)
    move.l  d5,8(a2)
    move.l  #outString,d1
    move.l  a2,d2
    jsr     _LVOVPrintf(a6)
 
    addq.l  #1,d4
    cmp.l   #n,d4
    ble     .loopm
 
    addq.l  #1,d3
    cmp.l   #m,d3
    ble     .loopn
 
exit
    move.l  execBase,a6
    move.l  dosBase,a1
    jsr     _LVOCloseLibrary(a6)
    rts
;
; ackermann function
;
; in:
;
; d3 = m
; d4 = n
;
; out:
;
; d5 = ans
;
ackermann
    move.l  d3,-(sp)
    move.l  d4,-(sp)
 
    tst.l   d3
    bne     .l1
    move.l  d4,d5
    addq.l  #1,d5
    bra     .return
.l1
    tst.l   d4
    bne     .l2
    subq.l  #1,d3
    moveq   #1,d4
    bsr     ackermann
    bra     .return
.l2
    subq.l  #1,d4
    bsr     ackermann
    move.l  d5,d4
    subq.l  #1,d3
    bsr     ackermann
 
.return
    move.l  (sp)+,d4
    move.l  (sp)+,d3
    rts
;
; variables
;
dosBase
    dc.l    0
 
printfArgs
    dcb.l   3
;
; strings
;
dosName
    dc.b    "dos.library",0
 
outString
    dc.b    "ackermann (%ld,%ld) is: %ld",10,0