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 Raspberry PI  or android 32 bits */
/*  program ackermann.s   */ 
 
/* REMARK 1 : this program use routines in a include file 
   see task Include a file language arm assembly 
   for the routine affichageMess conversion10 
   see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes                       */
/************************************/
.include "../constantes.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 r3,#0
    mov r4,#0
1:
    mov r0,r3
    mov r1,r4
    bl ackermann
    mov r5,r0
    mov r0,r3
    ldr r1,iAdrsZoneConv        @ else display odd message
    bl conversion10             @ call decimal conversion
    ldr r0,iAdrsMessResult
    ldr r1,iAdrsZoneConv        @ insert value conversion in message
    bl strInsertAtCharInc
    mov r6,r0
    mov r0,r4
    ldr r1,iAdrsZoneConv        @ else display odd message
    bl conversion10             @ call decimal conversion
    mov r0,r6
    ldr r1,iAdrsZoneConv        @ insert value conversion in message
    bl strInsertAtCharInc
    mov r6,r0
    mov r0,r5
    ldr r1,iAdrsZoneConv        @ else display odd message
    bl conversion10             @ call decimal conversion
    mov r0,r6
    ldr r1,iAdrsZoneConv        @ insert value conversion in message
    bl strInsertAtCharInc
    bl affichageMess
    add r4,#1
    cmp r4,#NMAXI
    blt 1b
    mov r4,#0
    add r3,#1
    cmp r3,#MMAXI
    blt 1b
100:                            @ standard end of the program 
    mov r0, #0                  @ return code
    mov r7, #EXIT               @ request to exit program
    svc #0                      @ perform the system call
 
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsMessResult:          .int sMessResult
iAdrsZoneConv:            .int sZoneConv
/***************************************************/
/*     fonction ackermann              */
/***************************************************/
// r0 contains a number m
// r1 contains a number n
// r0 return résult
ackermann:
    push {r1-r2,lr}             @ save  registers 
    cmp r0,#0
    beq 5f
    movlt r0,#-1               @ error
    blt 100f
    cmp r1,#0
    movlt r0,#-1               @ error
    blt 100f
    bgt 1f
    sub r0,r0,#1
    mov r1,#1
    bl ackermann
    b 100f
1:
    mov r2,r0
    sub r1,r1,#1
    bl ackermann
    mov r1,r0
    sub r0,r2,#1
    bl ackermann
    b 100f
5:
    adds r0,r1,#1
    bcc 100f
    ldr r0,iAdrszMessError
    bl affichageMess
    bkpt
100:
    pop {r1-r2,lr}             @ restaur registers
    bx lr                      @ return
iAdrszMessError:        .int szMessError
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
 