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.


 
/* ARM assembly AARCH64 Raspberry PI 3B or android 64 bits */
/*  program ackermann64.s   */ 
 
/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
.equ MMAXI,   4
.equ NMAXI,   10
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
sMessResult:        .asciz "Result for @  @  : @ \n"
szMessError:        .asciz "Overflow !!.\n"
szCarriageReturn:   .asciz "\n"
 
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:        .skip 24
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                           // entry of program 
    mov x3,#0
    mov x4,#0
1:
    mov x0,x3
    mov x1,x4
    bl ackermann
    mov x5,x0
    mov x0,x3
    ldr x1,qAdrsZoneConv        // else display odd message
    bl conversion10             // call decimal conversion
    ldr x0,qAdrsMessResult
    ldr x1,qAdrsZoneConv        // insert value conversion in message
    bl strInsertAtCharInc
    mov x6,x0
    mov x0,x4
    ldr x1,qAdrsZoneConv        // else display odd message
    bl conversion10             // call decimal conversion
    mov x0,x6
    ldr x1,qAdrsZoneConv        // insert value conversion in message
    bl strInsertAtCharInc
    mov x6,x0
    mov x0,x5
    ldr x1,qAdrsZoneConv        // else display odd message
    bl conversion10             // call decimal conversion
    mov x0,x6
    ldr x1,qAdrsZoneConv        // insert value conversion in message
    bl strInsertAtCharInc
    bl affichageMess
    add x4,x4,#1
    cmp x4,#NMAXI
    blt 1b
    mov x4,#0
    add x3,x3,#1
    cmp x3,#MMAXI
    blt 1b
100:                            // standard end of the program 
    mov x0, #0                  // return code
    mov x8, #EXIT               // request to exit program
    svc #0                      // perform the system call
 
qAdrszCarriageReturn:     .quad szCarriageReturn
qAdrsMessResult:          .quad sMessResult
qAdrsZoneConv:            .quad sZoneConv
/***************************************************/
/*     fonction ackermann              */
/***************************************************/
// x0 contains a number m
// x1 contains a number n
// x0 return résult
ackermann:
    stp x1,lr,[sp,-16]!         // save  registres
    stp x2,x3,[sp,-16]!         // save  registres
    cmp x0,0
    beq 5f
    mov x3,-1
    csel x0,x3,x0,lt               // error
    blt 100f
    cmp x1,#0
    csel x0,x3,x0,lt               // error
    blt 100f
    bgt 1f
    sub x0,x0,#1
    mov x1,#1
    bl ackermann
    b 100f
1:
    mov x2,x0
    sub x1,x1,#1
    bl ackermann
    mov x1,x0
    sub x0,x2,#1
    bl ackermann
    b 100f
5:
    adds x0,x1,#1
    bcc 100f
    ldr x0,qAdrszMessError
    bl affichageMess
    mov x0,-1
100:
 
    ldp x2,x3,[sp],16         // restaur des  2 registres
    ldp x1,lr,[sp],16         // restaur des  2 registres
    ret
qAdrszMessError:        .quad szMessError
 
/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
 