# Ackermann function: Difference between revisions

Ackermann function
You are encouraged to solve this task according to the task description, using any language you may know.

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:

${\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.

Write a function which returns the value of ${\displaystyle A(m, n)}$. Arbitrary precision is preferred (since the function grows so quickly), but not required.

## 11l

Translation of: Python
F ack2(m, n) -> Int
R I m == 0 {(n + 1)
} E I m == 1 {(n + 2)
} E I m == 2 {(2 * n + 3)
} E I m == 3 {(8 * (2 ^ n - 1) + 5)
} E I n == 0 {ack2(m - 1, 1)
} E ack2(m - 1, ack2(m, n - 1))

print(ack2(0, 0))
print(ack2(3, 4))
print(ack2(4, 1))
Output:
1
125
65533

## 360 Assembly

Translation of: AWK

The OS/360 linkage is a bit tricky with the S/360 basic instruction set. To simplify, the program is recursive not reentrant.

*        Ackermann function        07/09/2015
&LAB     XDECO &REG,&TARGET
.*-----------------------------------------------------------------*
.*       THIS MACRO DISPLAYS THE REGISTER CONTENTS AS A TRUE       *
.*       DECIMAL VALUE. XDECO IS NOT PART OF STANDARD S360 MACROS! *
*------------------------------------------------------------------*
AIF   (T'&REG EQ 'O').NOREG
AIF   (T'&TARGET EQ 'O').NODEST
&LAB     B     I&SYSNDX               BRANCH AROUND WORK AREA
W&SYSNDX DS    XL8                    CONVERSION WORK AREA
I&SYSNDX CVD   &REG,W&SYSNDX          CONVERT TO DECIMAL
MVC   &TARGET,=XL12'402120202020202020202020'
ED    &TARGET,W&SYSNDX+2     MAKE FIELD PRINTABLE
BC    2,*+12                 BYPASS NEGATIVE
MVI   &TARGET+12,C'-'        INSERT NEGATIVE SIGN
B     *+8                    BYPASS POSITIVE
MVI   &TARGET+12,C'+'        INSERT POSITIVE SIGN
MEXIT
.NOREG   MNOTE 8,'INPUT REGISTER OMITTED'
MEXIT
.NODEST  MNOTE 8,'TARGET FIELD OMITTED'
MEXIT
MEND
ACKERMAN CSECT
USING  ACKERMAN,R12       r12 : base register
LR     R12,R15            establish base register
ST     R14,SAVER14A       save r14
LA     R4,0               m=0
LOOPM    CH     R4,=H'3'           do m=0 to 3
BH     ELOOPM
LA     R5,0               n=0
LOOPN    CH     R5,=H'8'           do n=0 to 8
BH     ELOOPN
LR     R1,R4              m
LR     R2,R5              n
BAL    R14,ACKER          r1=acker(m,n)
XDECO  R1,PG+19
XDECO  R4,XD
MVC    PG+10(2),XD+10
XDECO  R5,XD
MVC    PG+13(2),XD+10
XPRNT  PG,44              print buffer
LA     R5,1(R5)           n=n+1
B      LOOPN
ELOOPN   LA     R4,1(R4)           m=m+1
B      LOOPM
ELOOPM   L      R14,SAVER14A       restore r14
SAVER14A DS     F                  static save r14
PG       DC     CL44'Ackermann(xx,xx) = xxxxxxxxxxxx'
XD       DS     CL12
ACKER    CNOP   0,4                function r1=acker(r1,r2)
LR     R3,R1              save argument r1 in r3
LR     R9,R10             save stackptr (r10) in r9 temp
LA     R1,STACKLEN        amount of storage required
GETMAIN RU,LV=(R1)        allocate storage for stack
ST     R14,SAVER14B       save previous r14
ST     R9,SAVER10B        save previous r10
LR     R1,R3              restore saved argument r1
START    ST     R1,M               stack m
ST     R2,N               stack n
IF1      C      R1,=F'0'           if m<>0
BNE    IF2                then goto if2
LR     R11,R2             n
LA     R11,1(R11)         return n+1
B      EXIT
IF2      C      R2,=F'0'           else if m<>0
BNE    IF3                then goto if3
BCTR   R1,0               m=m-1
LA     R2,1               n=1
BAL    R14,ACKER          r1=acker(m)
LR     R11,R1             return acker(m-1,1)
B      EXIT
IF3      BCTR   R2,0               n=n-1
BAL    R14,ACKER          r1=acker(m,n-1)
LR     R2,R1              acker(m,n-1)
L      R1,M               m
BCTR   R1,0               m=m-1
BAL    R14,ACKER          r1=acker(m-1,acker(m,n-1))
LR     R11,R1             return acker(m-1,1)
EXIT     L      R14,SAVER14B       restore r14
L      R9,SAVER10B        restore r10 temp
LA     R0,STACKLEN        amount of storage to free
FREEMAIN A=(R10),LV=(R0)  free allocated storage
LR     R1,R11             value returned
LR     R10,R9             restore r10
LTORG
DROP   R12                base no longer needed
STACK    DSECT                     dynamic area
SAVER14B DS     F                  saved r14
SAVER10B DS     F                  saved r10
M        DS     F                  m
N        DS     F                  n
STACKLEN EQU    *-STACK
YREGS
END    ACKERMAN
Output:
Ackermann( 0, 0) =            1
Ackermann( 0, 1) =            2
Ackermann( 0, 2) =            3
Ackermann( 0, 3) =            4
Ackermann( 0, 4) =            5
Ackermann( 0, 5) =            6
Ackermann( 0, 6) =            7
Ackermann( 0, 7) =            8
Ackermann( 0, 8) =            9
Ackermann( 1, 0) =            2
Ackermann( 1, 1) =            3
Ackermann( 1, 2) =            4
Ackermann( 1, 3) =            5
Ackermann( 1, 4) =            6
Ackermann( 1, 5) =            7
Ackermann( 1, 6) =            8
Ackermann( 1, 7) =            9
Ackermann( 1, 8) =           10
Ackermann( 2, 0) =            3
Ackermann( 2, 1) =            5
Ackermann( 2, 2) =            7
Ackermann( 2, 3) =            9
Ackermann( 2, 4) =           11
Ackermann( 2, 5) =           13
Ackermann( 2, 6) =           15
Ackermann( 2, 7) =           17
Ackermann( 2, 8) =           19
Ackermann( 3, 0) =            5
Ackermann( 3, 1) =           13
Ackermann( 3, 2) =           29
Ackermann( 3, 3) =           61
Ackermann( 3, 4) =          125
Ackermann( 3, 5) =          253
Ackermann( 3, 6) =          509
Ackermann( 3, 7) =         1021
Ackermann( 3, 8) =         2045

## 68000 Assembly

This implementation is based on the code shown in the computerphile episode in the youtube link at the top of this page (time index 5:00).

;
; 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)

cmp.l   #n,d4
ble     .loopm

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
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

## 8080 Assembly

This function does 16-bit math. The test code prints a table of ack(m,n) for m ∊ [0,4) and n ∊ [0,9), on a real 8080 this takes a little over two minutes.

org	100h
jmp	demo
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;	ACK(M,N); DE=M, HL=N, return value in HL.
ack:	mov	a,d	; M=0?
ora	e
jnz	ackm
inx	h	; If so, N+1.
ret
ackm:	mov	a,h	; N=0?
ora	l
jnz	ackmn
lxi	h,1	; If so, N=1,
dcx	d	; N-=1,
jmp	ack	; A(M,N) - tail recursion
ackmn:	push	d	; M>0 and N>0: store M on the stack
dcx	h	; N-=1
call	ack	; N = ACK(M,N-1)
pop	d	; Restore previous M
dcx	d	; M-=1
jmp	ack	; A(M,N) - tail recursion
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;	Print table of ack(m,n)
MMAX:	equ	4	; Size of table to print. Note that math is done in
NMAX:	equ	9	; 16 bits.
demo:	lhld	6	; Put stack pointer at top of available memory
sphl
lxi	b,0	; let B,C hold 8-bit M and N.
acknum:	xra	a	; Set high bit of M and N to zero
mov	d,a	; DE = B (M)
mov	e,b
mov	h,a	; HL = C (N)
mov	l,c
call	ack	; HL = ack(DE,HL)
call	prhl	; Print the number
inr	c	; N += 1
mvi	a,NMAX	; Time for next line?
cmp	c
jnz	acknum	; If not, print next number
push	b	; Otherwise, save BC
mvi	c,9	; Print newline
lxi	d,nl
call	5
pop	b	; Restore BC
mvi	c,0	; Set N to 0
inr	b	; M += 1
mvi	a,MMAX	; Time to stop?
cmp	b
jnz	acknum	; If not, print next number
rst	0
;;;	Print HL as ASCII number.
prhl:	push	h	; Save all registers
push	d
push	b
lxi	b,pnum	; Store pointer to num string on stack
push	b
lxi	b,-10	; Divisor
prdgt:	lxi	d,-1
prdgtl:	inx	d	; Divide by 10 through trial subtraction
jc	prdgtl
mvi	a,'0'+10
add	l	; L = remainder - 10
pop	h	; Get pointer from stack
dcx	h	; Store digit
mov	m,a
push	h	; Put pointer back on stack
xchg		; Put quotient in HL
mov	a,h	; Check if zero
ora	l
jnz	prdgt	; If not, next digit
pop	d	; Get pointer and put in DE
mvi	c,9	; CP/M print string
call	5
pop	b	; Restore registers
pop	d
pop	h
ret
db	'*****'	; Placeholder for number
pnum:	db	9,'$' nl: db 13,10,'$'
Output:
1       2       3       4       5       6       7       8       9
2       3       4       5       6       7       8       9       10
3       5       7       9       11      13      15      17      19
5       13      29      61      125     253     509     1021    2045

## 8086 Assembly

This code does 16-bit math just like the 8080 version.

cpu	8086
bits	16
org	100h
section	.text
jmp	demo
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;	ACK(M,N); DX=M, AX=N, return value in AX.
ack:	and	dx,dx	; N=0?
jnz	.m
inc	ax	; If so, return N+1
ret
.m:	and	ax,ax	; M=0?
jnz	.mn
mov	ax,1	; If so, N=1,
dec	dx	; M -= 1
jmp	ack	; ACK(M-1,1) - tail recursion
.mn:	push	dx	; Keep M on the stack
dec	ax	; N-=1
call	ack	; N = ACK(M,N-1)
pop	dx	; Restore M
dec	dx	; M -= 1
jmp	ack	; ACK(M-1,ACK(M,N-1)) - tail recursion
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;	Print table of ack(m,n)
MMAX:	equ	4	; Size of table to print. Noe that math is done
NMAX:	equ	9	; in 16 bits.
demo:	xor	si,si	; Let SI hold M,
xor	di,di	; and DI hold N.
acknum:	mov	dx,si	; Calculate ack(M,N)
mov	ax,di
call	ack
call	prax	; Print number
inc	di	; N += 1
cmp	di,NMAX	; Row done?
jb	acknum	; If not, print next number on row
xor	di,di	; Otherwise, N=0,
inc	si	; M += 1
mov	dx,nl	; Print newline
call	prstr
cmp	si,MMAX	; Done?
jb	acknum	; If not, start next row
ret		; Otherwise, stop.
;;;	Print AX as ASCII number.
prax:	mov	bx,pnum	; Pointer to number string
mov	cx,10	; Divisor
.dgt:	xor	dx,dx	; Divide AX by ten
div	cx
dec	bx	; Move pointer backwards
mov	[bx],dl	; Save digit in string
and	ax,ax	; Are we done yet?
jnz	.dgt	; If not, next digit
mov	dx,bx	; Tell DOS to print the string
prstr:	mov	ah,9
int	21h
ret
section	.data
db	'*****'	; Placeholder for ASCII number
pnum:	db	9,'$' nl: db 13,10,'$'
Output:
1       2       3       4       5       6       7       8       9
2       3       4       5       6       7       8       9       10
3       5       7       9       11      13      15      17      19
5       13      29      61      125     253     509     1021    2045

## 8th

\ 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
The output:
Ack(0, 0) = 1
Ack(0, 4) = 5
Ack(1, 0) = 2
Ack(1, 1) = 3
Ack(2, 1) = 5
Ack(2, 2) = 7
Ack(3, 1) = 13
Ack(3, 3) = 61
Ack(4, 0) = 13
Ack(4, 1) = 65533

## AArch64 Assembly

Works with: as version Raspberry Pi 3B version Buster 64 bits
or android 64 bits with application Termux
/* 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 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
cmp x4,#NMAXI
blt 1b
mov x4,#0
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

/***************************************************/
/*     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:
bcc 100f
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

/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
Output:
Result for 0  0  : 1
Result for 0  1  : 2
Result for 0  2  : 3
Result for 0  3  : 4
Result for 0  4  : 5
Result for 0  5  : 6
Result for 0  6  : 7
Result for 0  7  : 8
Result for 0  8  : 9
Result for 0  9  : 10
Result for 1  0  : 2
Result for 1  1  : 3
Result for 1  2  : 4
Result for 1  3  : 5
Result for 1  4  : 6
Result for 1  5  : 7
Result for 1  6  : 8
Result for 1  7  : 9
Result for 1  8  : 10
Result for 1  9  : 11
Result for 2  0  : 3
Result for 2  1  : 5
Result for 2  2  : 7
Result for 2  3  : 9
Result for 2  4  : 11
Result for 2  5  : 13
Result for 2  6  : 15
Result for 2  7  : 17
Result for 2  8  : 19
Result for 2  9  : 21
Result for 3  0  : 5
Result for 3  1  : 13
Result for 3  2  : 29
Result for 3  3  : 61
Result for 3  4  : 125
Result for 3  5  : 253
Result for 3  6  : 509
Result for 3  7  : 1021
Result for 3  8  : 2045
Result for 3  9  : 4093

## ABAP

REPORT  zhuberv_ackermann.

CLASS zcl_ackermann DEFINITION.
PUBLIC SECTION.
CLASS-METHODS ackermann IMPORTING m TYPE i
n TYPE i
RETURNING value(v) TYPE i.
ENDCLASS.            "zcl_ackermann DEFINITION

CLASS zcl_ackermann IMPLEMENTATION.

METHOD: ackermann.

DATA: lv_new_m TYPE i,
lv_new_n TYPE i.

IF m = 0.
v = n + 1.
ELSEIF m > 0 AND n = 0.
lv_new_m = m - 1.
lv_new_n = 1.
v = ackermann( m = lv_new_m n = lv_new_n ).
ELSEIF m > 0 AND n > 0.
lv_new_m = m - 1.

lv_new_n = n - 1.
lv_new_n = ackermann( m = m n = lv_new_n ).

v = ackermann( m = lv_new_m n = lv_new_n ).
ENDIF.

ENDMETHOD.                    "ackermann

ENDCLASS.                    "zcl_ackermann IMPLEMENTATION

PARAMETERS: pa_m TYPE i,
pa_n TYPE i.

DATA: lv_result TYPE i.

START-OF-SELECTION.
lv_result = zcl_ackermann=>ackermann( m = pa_m n = pa_n ).
WRITE: / lv_result.

## Action!

Action! language does not support recursion. Therefore an iterative approach with a stack has been proposed.

DEFINE MAXSIZE="1000"
CARD ARRAY stack(MAXSIZE)
CARD stacksize=[0]

BYTE FUNC IsEmpty()
IF stacksize=0 THEN
RETURN (1)
FI
RETURN (0)

PROC Push(BYTE v)
IF stacksize=maxsize THEN
PrintE("Error: stack is full!")
Break()
FI
stack(stacksize)=v
stacksize==+1
RETURN

BYTE FUNC Pop()
IF IsEmpty() THEN
PrintE("Error: stack is empty!")
Break()
FI
stacksize==-1
RETURN (stack(stacksize))

CARD FUNC Ackermann(CARD m,n)
Push(m)
WHILE IsEmpty()=0
DO
m=Pop()
IF m=0 THEN
n==+1
ELSEIF n=0 THEN
n=1
Push(m-1)
ELSE
n==-1
Push(m-1)
Push(m)
FI
OD
RETURN (n)

PROC Main()
CARD m,n,res

FOR m=0 TO 3
DO
FOR n=0 TO 4
DO
res=Ackermann(m,n)
PrintF("Ack(%U,%U)=%U%E",m,n,res)
OD
OD
RETURN
Output:
Ack(0,0)=1
Ack(0,1)=2
Ack(0,2)=3
Ack(0,3)=4
Ack(0,4)=5
Ack(1,0)=2
Ack(1,1)=3
Ack(1,2)=4
Ack(1,3)=5
Ack(1,4)=6
Ack(2,0)=3
Ack(2,1)=5
Ack(2,2)=7
Ack(2,3)=9
Ack(2,4)=11
Ack(3,0)=5
Ack(3,1)=13
Ack(3,2)=29
Ack(3,3)=61
Ack(3,4)=125

## ActionScript

public function ackermann(m:uint, n:uint):uint
{
if (m == 0)
{
return n + 1;
}
if (n == 0)
{
return ackermann(m - 1, 1);
}

return ackermann(m - 1, ackermann(m, n - 1));
}

procedure Test_Ackermann is
function Ackermann (M, N : Natural) return Natural is
begin
if M = 0 then
return N + 1;
elsif N = 0 then
return Ackermann (M - 1, 1);
else
return Ackermann (M - 1, Ackermann (M, N - 1));
end if;
end Ackermann;
begin
for M in 0..3 loop
for N in 0..6 loop
Put (Natural'Image (Ackermann (M, N)));
end loop;
New_Line;
end loop;
end Test_Ackermann;

The implementation does not care about arbitrary precision numbers because the Ackermann function does not only grow, but also slow quickly, when computed recursively.

Output:
the first 4x7 Ackermann's numbers
1 2 3 4 5 6 7
2 3 4 5 6 7 8
3 5 7 9 11 13 15
5 13 29 61 125 253 509

## Agda

Works with: Agda version 2.5.2
open import Data.Nat
open import Data.Nat.Show
open import IO

module Ackermann where

ack :  ->  ->
ack zero n = n + 1
ack (suc m) zero = ack m 1
ack (suc m) (suc n) = ack m (ack (suc m) n)

main = run (putStrLn (show (ack 3 9)))

Note the unicode ℕ characters, they can be input in emacs agda mode using "\bN". Running in bash:

agda --compile Ackermann.agda
./Ackermann
Output:
4093

## ALGOL 60

Works with: A60
begin
integer procedure ackermann(m,n);value m,n;integer m,n;
ackermann:=if m=0 then n+1
else if n=0 then ackermann(m-1,1)
else ackermann(m-1,ackermann(m,n-1));
integer m,n;
for m:=0 step 1 until 3 do begin
for n:=0 step 1 until 6 do
outinteger(1,ackermann(m,n));
outstring(1,"\n")
end
end
Output:
1  2  3  4  5  6  7
2  3  4  5  6  7  8
3  5  7  9  11  13  15
5  13  29  61  125  253  509

## ALGOL 68

Works with: ALGOL 68 version Standard - no extensions to language used
Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386
PROC test ackermann = VOID:
BEGIN
PROC ackermann = (INT m, n)INT:
BEGIN
IF m = 0 THEN
n + 1
ELIF n = 0 THEN
ackermann (m - 1, 1)
ELSE
ackermann (m - 1, ackermann (m, n - 1))
FI
END # ackermann #;

FOR m FROM 0 TO 3 DO
FOR n FROM 0 TO 6 DO
print(ackermann (m, n))
OD;
new line(stand out)
OD
END # test ackermann #;
test ackermann
Output:
+1         +2         +3         +4         +5         +6         +7
+2         +3         +4         +5         +6         +7         +8
+3         +5         +7         +9        +11        +13        +15
+5        +13        +29        +61       +125       +253       +509

## ALGOL W

Translation of: ALGOL 60
begin
integer procedure ackermann( integer value m,n ) ;
if m=0 then n+1
else if n=0 then ackermann(m-1,1)
else ackermann(m-1,ackermann(m,n-1));
for m := 0 until 3 do begin
write( ackermann( m, 0 ) );
for n := 1 until 6 do writeon( ackermann( m, n ) );
end for_m
end.
Output:
1               2               3               4               5               6               7
2               3               4               5               6               7               8
3               5               7               9              11              13              15
5              13              29              61             125             253             509

## APL

Works with: Dyalog APL
ackermann{
0=1⍵:1+2
0=2⍵:∇(¯1+1)1
(¯1+1),(1),¯1+2
}

## AppleScript

on ackermann(m, n)
if m is equal to 0 then return n + 1
if n is equal to 0 then return ackermann(m - 1, 1)
return ackermann(m - 1, ackermann(m, n - 1))
end ackermann

## Argile

Works with: Argile version 1.0.0
use std

for each (val nat n) from 0 to 6
for each (val nat m) from 0 to 3
print "A("m","n") = "(A m n)

.:A <nat m, nat n>:. -> nat
return (n+1)				if m == 0
return (A (m - 1) 1)			if n == 0
A (m - 1) (A m (n - 1))

## ARM Assembly

Works with: as version Raspberry Pi
or android 32 bits with application Termux
/* 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 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
cmp r4,#NMAXI
blt 1b
mov r4,#0
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

/***************************************************/
/*     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:
bcc 100f
bl affichageMess
bkpt
100:
pop {r1-r2,lr}             @ restaur registers
bx lr                      @ return
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
Output:
Result for 0            0            : 1
Result for 0            1            : 2
Result for 0            2            : 3
Result for 0            3            : 4
Result for 0            4            : 5
Result for 0            5            : 6
Result for 0            6            : 7
Result for 0            7            : 8
Result for 0            8            : 9
Result for 0            9            : 10
Result for 1            0            : 2
Result for 1            1            : 3
Result for 1            2            : 4
Result for 1            3            : 5
Result for 1            4            : 6
Result for 1            5            : 7
Result for 1            6            : 8
Result for 1            7            : 9
Result for 1            8            : 10
Result for 1            9            : 11
Result for 2            0            : 3
Result for 2            1            : 5
Result for 2            2            : 7
Result for 2            3            : 9
Result for 2            4            : 11
Result for 2            5            : 13
Result for 2            6            : 15
Result for 2            7            : 17
Result for 2            8            : 19
Result for 2            9            : 21
Result for 3            0            : 5
Result for 3            1            : 13
Result for 3            2            : 29
Result for 3            3            : 61
Result for 3            4            : 125
Result for 3            5            : 253
Result for 3            6            : 509
Result for 3            7            : 1021
Result for 3            8            : 2045
Result for 3            9            : 4093

## Arturo

ackermann: function [m,n][
(m=0)? -> n+1 [
(n=0)? -> ackermann m-1 1
-> ackermann m-1 ackermann m n-1
]
]

loop 0..3 'a [
loop 0..4 'b [
print ["ackermann" a b "=>" ackermann a b]
]
]
Output:
ackermann 0 0 => 1
ackermann 0 1 => 2
ackermann 0 2 => 3
ackermann 0 3 => 4
ackermann 0 4 => 5
ackermann 1 0 => 2
ackermann 1 1 => 3
ackermann 1 2 => 4
ackermann 1 3 => 5
ackermann 1 4 => 6
ackermann 2 0 => 3
ackermann 2 1 => 5
ackermann 2 2 => 7
ackermann 2 3 => 9
ackermann 2 4 => 11
ackermann 3 0 => 5
ackermann 3 1 => 13
ackermann 3 2 => 29
ackermann 3 3 => 61
ackermann 3 4 => 125

## ATS

fun ackermann
{m,n:nat} .<m,n>.
(m: int m, n: int n): Nat =
case+ (m, n) of
| (0, _) => n+1
| (_, 0) =>> ackermann (m-1, 1)
| (_, _) =>> ackermann (m-1, ackermann (m, n-1))
// end of [ackermann]

## AutoHotkey

A(m, n) {
If (m > 0) && (n = 0)
Return A(m-1,1)
Else If (m > 0) && (n > 0)
Return A(m-1,A(m, n-1))
Else If (m=0)
Return n+1
}

; Example:
MsgBox, % "A(1,2) = " A(1,2)

## AutoIt

### Classical version

Func Ackermann($m,$n)
If ($m = 0) Then Return$n+1
Else
If ($n = 0) Then Return Ackermann($m-1, 1)
Else
return Ackermann($m-1, Ackermann($m, $n-1)) EndIf EndIf EndFunc ### Classical + cache implementation This version works way faster than the classical one: Ackermann(3, 5) runs in 12,7 ms, while the classical version takes 402,2 ms. Global$ackermann[2047][2047] ; Set the size to whatever you want
Func Ackermann($m,$n)
If ($ackermann[$m][$n] <> 0) Then Return$ackermann[$m][$n]
Else
If ($m = 0) Then$return = $n + 1 Else If ($n = 0) Then
$return = Ackermann($m - 1, 1)
Else
$return = Ackermann($m - 1, Ackermann($m,$n - 1))
EndIf
EndIf
$ackermann[$m][$n] =$return
\^v_$1\1- u^>1-0fp:1-\0fg101- The program reads two integers (first m, then n) from command line, idles around funge space, then outputs the result of the Ackerman function. Since the latter is calculated truly recursively, the execution time becomes unwieldy for most m>3. ## BQN A ← { A 0‿n: n+1; A m‿0: A (m-1)‿1; A m‿n: A (m-1)‿(A m‿(n-1)) } Example usage: A 0‿3 4 A 1‿4 6 A 2‿4 11 A 3‿4 125 ## Bracmat Three solutions are presented here. The first one is a purely recursive version, only using the formulas at the top of the page. The value of A(4,1) cannot be computed due to stack overflow. It can compute A(3,9) (4093), but probably not A(3,10) ( Ack = m n . !arg:(?m,?n) & ( !m:0&!n+1 | !n:0&Ack$(!m+-1,1)
| Ack$(!m+-1,Ack$(!m,!n+-1))
)
);

The second version is a purely non-recursive solution that easily can compute A(4,1). The program uses a stack for Ackermann function calls that are to be evaluated, but that cannot be computed given the currently known function values - the "known unknowns". The currently known values are stored in a hash table. The Hash table also contains incomplete Ackermann function calls, namely those for which the second argument is not known yet - "the unknown unknowns". These function calls are associated with "known unknowns" that are going to provide the value of the second argument. As soon as such an associated known unknown becomes known, the unknown unknown becomes a known unknown and is pushed onto the stack.

Although all known values are stored in the hash table, the converse is not true: an element in the hash table is either a "known known" or an "unknown unknown" associated with an "known unknown".

( A
=     m n value key eq chain
, find insert future stack va val
.   ( chain
=   key future skey
.   !arg:(?key.?future)
& str$!key:?skey & (cache..insert)$(!skey..!future)
&
)
& (find=.(cache..find)$(str$!arg))
& ( insert
=   key value future v futureeq futurem skey
.   !arg:(?key.?value)
& str$!key:?skey & ( (cache..find)$!skey:(?key.?v.?future)
& (cache..remove)$!skey & (cache..insert)$(!skey.!value.)
& (   !future:(?futurem.?futureeq)
& (!futurem,!value.!futureeq)
|
)
| (cache..insert)$(!skey.!value.)& ) ) & !arg:(?m,?n) & !n+1:?value & :?eq:?stack & whl ' ( (!m,!n):?key & ( find$!key:(?.#%?value.?future)
& insert$(!eq.!value) !future | !m:0 & !n+1:?value & ( !eq:&insert$(!key.!value)
|   insert$(!key.!value) !stack:?stack & insert$(!eq.!value)
)
|   !n:0
&   (!m+-1,1.!key)
(!eq:|(!key.!eq))
|   find$(!m,!n+-1):(?.?val.?) & ( !val:#% & ( find$(!m+-1,!val):(?.?va.?)
& !va:#%
& insert$(!key.!va) | (!m+-1,!val.!eq) (!m,!n.!eq) ) | ) | chain$(!m,!n+-1.!m+-1.!key)
&   (!m,!n+-1.)
(!eq:|(!key.!eq))
)
!stack
: (?m,?n.?eq) ?stack
)
& !value
)
& new$hash:?cache Some results: A$(0,0):1
A$(3,13):65533 A$(3,14):131069
A$(4,1):65533 The last solution is a recursive solution that employs some extra formulas, inspired by the Common Lisp solution further down. ( AckFormula = m n . !arg:(?m,?n) & ( !m:0&!n+1 | !m:1&!n+2 | !m:2&2*!n+3 | !m:3&2^(!n+3)+-3 | !n:0&AckFormula$(!m+-1,1)
| AckFormula$(!m+-1,AckFormula$(!m,!n+-1))
)
)
Some results:
AckFormula$(4,1):65533 AckFormula$(4,2):2003529930406846464979072351560255750447825475569751419265016973.....22087777506072339445587895905719156733

The last computation costs about 0,03 seconds.

## Brat

ackermann = { m, n |
when { m == 0 } { n + 1 }
{ m > 0 && n == 0 } { ackermann(m - 1, 1) }
{ m > 0 && n > 0 } { ackermann(m - 1, ackermann(m, n - 1)) }
}

p ackermann 3, 4  #Prints 125

## C

Straightforward implementation per Ackermann definition:

#include <stdio.h>

int ackermann(int m, int n)
{
if (!m) return n + 1;
if (!n) return ackermann(m - 1, 1);
return ackermann(m - 1, ackermann(m, n - 1));
}

int main()
{
int m, n;
for (m = 0; m <= 4; m++)
for (n = 0; n < 6 - m; n++)
printf("A(%d, %d) = %d\n", m, n, ackermann(m, n));

return 0;
}
Output:
A(0, 0) = 1
A(0, 1) = 2
A(0, 2) = 3
A(0, 3) = 4
A(0, 4) = 5
A(0, 5) = 6
A(1, 0) = 2
A(1, 1) = 3
A(1, 2) = 4
A(1, 3) = 5
A(1, 4) = 6
A(2, 0) = 3
A(2, 1) = 5
A(2, 2) = 7
A(2, 3) = 9
A(3, 0) = 5
A(3, 1) = 13
A(3, 2) = 29
A(4, 0) = 13
A(4, 1) = 65533

Ackermann function makes a lot of recursive calls, so the above program is a bit naive. We need to be slightly less naive, by doing some simple caching:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int m_bits, n_bits;
int *cache;

int ackermann(int m, int n)
{
int idx, res;
if (!m) return n + 1;

if (n >= 1<<n_bits) {
printf("%d, %d\n", m, n);
idx = 0;
} else {
idx = (m << n_bits) + n;
if (cache[idx]) return cache[idx];
}

if (!n) res = ackermann(m - 1, 1);
else    res = ackermann(m - 1, ackermann(m, n - 1));

if (idx) cache[idx] = res;
return res;
}
int main()
{
int m, n;

m_bits = 3;
n_bits = 20;  /* can save n values up to 2**20 - 1, that's 1 meg */
cache = malloc(sizeof(int) * (1 << (m_bits + n_bits)));
memset(cache, 0, sizeof(int) * (1 << (m_bits + n_bits)));

for (m = 0; m <= 4; m++)
for (n = 0; n < 6 - m; n++)
printf("A(%d, %d) = %d\n", m, n, ackermann(m, n));

return 0;
}
Output:
A(0, 0) = 1
A(0, 1) = 2
A(0, 2) = 3
A(0, 3) = 4
A(0, 4) = 5
A(0, 5) = 6
A(1, 0) = 2
A(1, 1) = 3
A(1, 2) = 4
A(1, 3) = 5
A(1, 4) = 6
A(2, 0) = 3
A(2, 1) = 5
A(2, 2) = 7
A(2, 3) = 9
A(3, 0) = 5
A(3, 1) = 13
A(3, 2) = 29
A(4, 0) = 13
A(4, 1) = 65533

Whee. Well, with some extra work, we calculated one more n value, big deal, right? But see, A(4, 2) = A(3, A(4, 1)) = A(3, 65533) = A(2, A(3, 65532)) = ... you can see how fast it blows up. In fact, no amount of caching will help you calculate large m values; on the machine I use A(4, 2) segfaults because the recursions run out of stack space--not a whole lot I can do about it. At least it runs out of stack space quickly, unlike the first solution...

A couple of alternative approaches...

/* Thejaka Maldeniya */

#include <conio.h>

unsigned long long HR(unsigned int n, unsigned long long a, unsigned long long b) {
// (Internal) Recursive Hyperfunction: Perform a Hyperoperation...

unsigned long long r = 1;

while(b--)
r = n - 3 ? HR(n - 1, a, r) : /* Exponentiation */ r * a;

return r;
}

unsigned long long H(unsigned int n, unsigned long long a, unsigned long long b) {
// Hyperfunction (Recursive-Iterative-O(1) Hybrid): Perform a Hyperoperation...

switch(n) {
case 0:
// Increment
return ++b;
case 1:
return a + b;
case 2:
// Multiplication
return a * b;
}

return HR(n, a, b);
}

unsigned long long APH(unsigned int m, unsigned int n) {
// Ackermann-Péter Function (Recursive-Iterative-O(1) Hybrid)
return H(m, 2, n + 3) - 3;
}

unsigned long long * p = 0;

unsigned long long APRR(unsigned int m, unsigned int n) {
if (!m) return ++n;

unsigned long long r = p ? p[m] : APRR(m - 1, 1);

--m;
while(n--)
r = APRR(m, r);

return r;
}

unsigned long long APRA(unsigned int m, unsigned int n) {
return
m ?
n ?
APRR(m, n)
: p ? p[m] : APRA(--m, 1)
: ++n
;
}

unsigned long long APR(unsigned int m, unsigned int n) {
unsigned long long r = 0;

// Allocate
p = (unsigned long long *) malloc(sizeof(unsigned long long) * (m + 1));

// Initialize
for(; r <= m; ++r)
p[r] = r ? APRA(r - 1, 1) : APRA(r, 0);

// Calculate
r = APRA(m, n);

// Free
free(p);

return r;
}

unsigned long long AP(unsigned int m, unsigned int n) {
return APH(m, n);
return APR(m, n);
}

int main(int n, char ** a) {
unsigned int M, N;

if (n != 3) {
printf("Usage: %s <m> <n>\n", *a);
return 1;
}

printf("AckermannPeter(%u, %u) = %llu\n", M = atoi(a[1]), N = atoi(a[2]), AP(M, N));

//printf("\nPress any key...");
//getch();
return 0;
}

A couple of more iterative techniques...

/* Thejaka Maldeniya */

#include <conio.h>

unsigned long long HI(unsigned int n, unsigned long long a, unsigned long long b) {
// Hyperfunction (Iterative): Perform a Hyperoperation...

unsigned long long *I, r = 1;
unsigned int N = n - 3;

if (!N)
// Exponentiation
while(b--)
r *= a;
else if(b) {
n -= 2;

// Allocate
I = (unsigned long long *) malloc(sizeof(unsigned long long) * n--);

// Initialize
I[n] = b;

// Calculate
for(;;) {
if(I[n]) {
--I[n];
if (n)
I[--n] = r, r = 1;
else
r *= a;
} else
for(;;)
if (n == N)
goto a;
else if(I[++n])
break;
}
a:

// Free
free(I);
}

return r;
}

unsigned long long H(unsigned int n, unsigned long long a, unsigned long long b) {
// Hyperfunction (Iterative-O(1) Hybrid): Perform a Hyperoperation...

switch(n) {
case 0:
// Increment
return ++b;
case 1:
return a + b;
case 2:
// Multiplication
return a * b;
}

return HI(n, a, b);
}

unsigned long long APH(unsigned int m, unsigned int n) {
// Ackermann-Péter Function (Recursive-Iterative-O(1) Hybrid)
return H(m, 2, n + 3) - 3;
}

unsigned long long * p = 0;

unsigned long long APIA(unsigned int m, unsigned int n) {
if (!m) return ++n;

// Initialize
unsigned long long *I, r = p ? p[m] : APIA(m - 1, 1);
unsigned int M = m;

if (n) {
// Allocate
I = (unsigned long long *) malloc(sizeof(unsigned long long) * (m + 1));

// Initialize
I[m] = n;

// Calculate
for(;;) {
if(I[m]) {
if (m)
--I[m], I[--m] = r, r = p ? p[m] : APIA(m - 1, 1);
else
r += I[m], I[m] = 0;
} else
for(;;)
if (m == M)
goto a;
else if(I[++m])
break;
}
a:

// Free
free(I);
}

return r;
}

unsigned long long API(unsigned int m, unsigned int n) {
unsigned long long r = 0;

// Allocate
p = (unsigned long long *) malloc(sizeof(unsigned long long) * (m + 1));

// Initialize
for(; r <= m; ++r)
p[r] = r ? APIA(r - 1, 1) : APIA(r, 0);

// Calculate
r = APIA(m, n);

// Free
free(p);

return r;
}

unsigned long long AP(unsigned int m, unsigned int n) {
return APH(m, n);
return API(m, n);
}

int main(int n, char ** a) {
unsigned int M, N;

if (n != 3) {
printf("Usage: %s <m> <n>\n", *a);
return 1;
}

printf("AckermannPeter(%u, %u) = %llu\n", M = atoi(a[1]), N = atoi(a[2]), AP(M, N));

//printf("\nPress any key...");
//getch();
return 0;
}

A few further tweaks/optimizations may be possible.

## C#

### Basic Version

using System;
class Program
{
public static long Ackermann(long m, long n)
{
if(m > 0)
{
if (n > 0)
return Ackermann(m - 1, Ackermann(m, n - 1));
else if (n == 0)
return Ackermann(m - 1, 1);
}
else if(m == 0)
{
if(n >= 0)
return n + 1;
}

throw new System.ArgumentOutOfRangeException();
}

static void Main()
{
for (long m = 0; m <= 3; ++m)
{
for (long n = 0; n <= 4; ++n)
{
Console.WriteLine("Ackermann({0}, {1}) = {2}", m, n, Ackermann(m, n));
}
}
}
}
Output:
Ackermann(0, 0) = 1
Ackermann(0, 1) = 2
Ackermann(0, 2) = 3
Ackermann(0, 3) = 4
Ackermann(0, 4) = 5
Ackermann(1, 0) = 2
Ackermann(1, 1) = 3
Ackermann(1, 2) = 4
Ackermann(1, 3) = 5
Ackermann(1, 4) = 6
Ackermann(2, 0) = 3
Ackermann(2, 1) = 5
Ackermann(2, 2) = 7
Ackermann(2, 3) = 9
Ackermann(2, 4) = 11
Ackermann(3, 0) = 5
Ackermann(3, 1) = 13
Ackermann(3, 2) = 29
Ackermann(3, 3) = 61
Ackermann(3, 4) = 125

### Efficient Version

using System;
using System.Numerics;
using System.IO;
using System.Diagnostics;

namespace Ackermann_Function
{
class Program
{
static void Main(string[] args)
{
int _m = 0;
int _n = 0;
Console.Write("m = ");
try
{
}
catch (Exception)
{
}
Console.Write("n = ");
try
{
}
catch (Exception)
{
}
//for (long m = 0; m <= 10; ++m)
//{
//    for (long n = 0; n <= 10; ++n)
//    {
//        DateTime now = DateTime.Now;
//        Console.WriteLine("Ackermann({0}, {1}) = {2}", m, n, Ackermann(m, n));
//        Console.WriteLine("Time taken:{0}", DateTime.Now - now);
//    }
//}

DateTime now = DateTime.Now;
Console.WriteLine("Ackermann({0}, {1}) = {2}", _m, _n, Ackermann(_m, _n));
Console.WriteLine("Time taken:{0}", DateTime.Now - now);
File.WriteAllText("number.txt", Ackermann(_m, _n).ToString());
Process.Start("number.txt");
}
public class OverflowlessStack<T>
{
{
private const int ArraySize = 2048;
T[] _array;
int _size;
{
_array = new T[ArraySize];
}
public bool IsEmpty { get { return _size == 0; } }
{
if (_size == ArraySize - 1)
{
n.Next = this;
n.Push(item);
return n;
}
_array[_size++] = item;
return this;
}
public T Pop()
{
return _array[--_size];
}
}

public T Pop()
{
return ret;
}
public void Push(T item)
{
}
public bool IsEmpty
{
}
}
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
var stack = new OverflowlessStack<BigInteger>();
stack.Push(m);
while (!stack.IsEmpty)
{
m = stack.Pop();
skipStack:
if (m == 0)
n = n + 1;
else if (m == 1)
n = n + 2;
else if (m == 2)
n = n * 2 + 3;
else if (n == 0)
{
--m;
n = 1;
goto skipStack;
}
else
{
stack.Push(m - 1);
--n;
goto skipStack;
}
}
return n;
}
}
}

Possibly the most efficient implementation of Ackermann in C#. It successfully runs Ack(4,2) when executed in Visual Studio. Don't forget to add a reference to System.Numerics.

## C++

### Basic version

#include <iostream>

unsigned int ackermann(unsigned int m, unsigned int n) {
if (m == 0) {
return n + 1;
}
if (n == 0) {
return ackermann(m - 1, 1);
}
return ackermann(m - 1, ackermann(m, n - 1));
}

int main() {
for (unsigned int m = 0; m < 4; ++m) {
for (unsigned int n = 0; n < 10; ++n) {
std::cout << "A(" << m << ", " << n << ") = " << ackermann(m, n) << "\n";
}
}
}

### Efficient version

Translation of: D

C++11 with boost's big integer type. Compile with:

g++ -std=c++11 -I /path/to/boost ackermann.cpp.
#include <iostream>
#include <sstream>
#include <string>
#include <boost/multiprecision/cpp_int.hpp>

using big_int = boost::multiprecision::cpp_int;

big_int ipow(big_int base, big_int exp) {
big_int result(1);
while (exp) {
if (exp & 1) {
result *= base;
}
exp >>= 1;
base *= base;
}
return result;
}

big_int ackermann(unsigned m, unsigned n) {
static big_int (*ack)(unsigned, big_int) =
[](unsigned m, big_int n)->big_int {
switch (m) {
case 0:
return n + 1;
case 1:
return n + 2;
case 2:
return 3 + 2 * n;
case 3:
return 5 + 8 * (ipow(big_int(2), n) - 1);
default:
return n == 0 ? ack(m - 1, big_int(1)) : ack(m - 1, ack(m, n - 1));
}
};
return ack(m, big_int(n));
}

int main() {
for (unsigned m = 0; m < 4; ++m) {
for (unsigned n = 0; n < 10; ++n) {
std::cout << "A(" << m << ", " << n << ") = " << ackermann(m, n) << "\n";
}
}

std::cout << "A(4, 1) = " << ackermann(4, 1) << "\n";

std::stringstream ss;
ss << ackermann(4, 2);
auto text = ss.str();
std::cout << "A(4, 2) = (" << text.length() << " digits)\n"
<< text.substr(0, 80) << "\n...\n"
<< text.substr(text.length() - 80) << "\n";
}
<pre>
A(0, 0) = 1
A(0, 1) = 2
A(0, 2) = 3
A(0, 3) = 4
A(0, 4) = 5
A(0, 5) = 6
A(0, 6) = 7
A(0, 7) = 8
A(0, 8) = 9
A(0, 9) = 10
A(1, 0) = 2
A(1, 1) = 3
A(1, 2) = 4
A(1, 3) = 5
A(1, 4) = 6
A(1, 5) = 7
A(1, 6) = 8
A(1, 7) = 9
A(1, 8) = 10
A(1, 9) = 11
A(2, 0) = 3
A(2, 1) = 5
A(2, 2) = 7
A(2, 3) = 9
A(2, 4) = 11
A(2, 5) = 13
A(2, 6) = 15
A(2, 7) = 17
A(2, 8) = 19
A(2, 9) = 21
A(3, 0) = 5
A(3, 1) = 13
A(3, 2) = 29
A(3, 3) = 61
A(3, 4) = 125
A(3, 5) = 253
A(3, 6) = 509
A(3, 7) = 1021
A(3, 8) = 2045
A(3, 9) = 4093
A(4, 1) = 65533
A(4, 2) = (19729 digits)
2003529930406846464979072351560255750447825475569751419265016973710894059556311
...
4717124577965048175856395072895337539755822087777506072339445587895905719156733

## Chapel

proc A(m:int, n:int):int {
if m == 0 then
return n + 1;
else if n == 0 then
return A(m - 1, 1);
else
return A(m - 1, A(m, n - 1));
}

## Clay

ackermann(m, n) {
if(m == 0)
return n + 1;
if(n == 0)
return ackermann(m - 1, 1);

return ackermann(m - 1, ackermann(m, n - 1));
}

## CLIPS

Functional solution

(deffunction ackerman
(?m ?n)
(if (= 0 ?m)
then (+ ?n 1)
else (if (= 0 ?n)
then (ackerman (- ?m 1) 1)
else (ackerman (- ?m 1) (ackerman ?m (- ?n 1)))
)
)
)
Example usage:
CLIPS> (ackerman 0 4)
5
CLIPS> (ackerman 1 4)
6
CLIPS> (ackerman 2 4)
11
CLIPS> (ackerman 3 4)
125

Fact-based solution

(deffacts solve-items
(solve 0 4)
(solve 1 4)
(solve 2 4)
(solve 3 4)
)

(defrule acker-m-0
?compute <- (compute 0 ?n)
=>
(retract ?compute)
(assert (ackerman 0 ?n (+ ?n 1)))
)

(defrule acker-n-0-pre
(compute ?m&:(> ?m 0) 0)
(not (ackerman =(- ?m 1) 1 ?))
=>
(assert (compute (- ?m 1) 1))
)

(defrule acker-n-0
?compute <- (compute ?m&:(> ?m 0) 0)
(ackerman =(- ?m 1) 1 ?val)
=>
(retract ?compute)
(assert (ackerman ?m 0 ?val))
)

(defrule acker-m-n-pre-1
(compute ?m&:(> ?m 0) ?n&:(> ?n 0))
(not (ackerman ?m =(- ?n 1) ?))
=>
(assert (compute ?m (- ?n 1)))
)

(defrule acker-m-n-pre-2
(compute ?m&:(> ?m 0) ?n&:(> ?n 0))
(ackerman ?m =(- ?n 1) ?newn)
(not (ackerman =(- ?m 1) ?newn ?))
=>
(assert (compute (- ?m 1) ?newn))
)

(defrule acker-m-n
?compute <- (compute ?m&:(> ?m 0) ?n&:(> ?n 0))
(ackerman ?m =(- ?n 1) ?newn)
(ackerman =(- ?m 1) ?newn ?val)
=>
(retract ?compute)
(assert (ackerman ?m ?n ?val))
)

(defrule acker-solve
(solve ?m ?n)
(not (compute ?m ?n))
(not (ackerman ?m ?n ?))
=>
(assert (compute ?m ?n))
)

(defrule acker-solved
?solve <- (solve ?m ?n)
(ackerman ?m ?n ?result)
=>
(retract ?solve)
(printout t "A(" ?m "," ?n ") = " ?result crlf)
)

When invoked, each required A(m,n) needed to solve the requested (solve ?m ?n) facts gets generated as its own fact. Below shows the invocation of the above, as well as an excerpt of the final facts list. Regardless of how many input (solve ?m ?n) requests are made, each possible A(m,n) is only solved once.

CLIPS> (reset)
CLIPS> (facts)
f-0     (initial-fact)
f-1     (solve 0 4)
f-2     (solve 1 4)
f-3     (solve 2 4)
f-4     (solve 3 4)
For a total of 5 facts.
CLIPS> (run)
A(3,4) = 125
A(2,4) = 11
A(1,4) = 6
A(0,4) = 5
CLIPS> (facts)
f-0     (initial-fact)
f-15    (ackerman 0 1 2)
f-16    (ackerman 1 0 2)
f-18    (ackerman 0 2 3)
...
f-632   (ackerman 1 123 125)
f-633   (ackerman 2 61 125)
f-634   (ackerman 3 4 125)
For a total of 316 facts.
CLIPS>

## Clojure

(defn ackermann [m n]
(cond (zero? m) (inc n)
(zero? n) (ackermann (dec m) 1)
:else (ackermann (dec m) (ackermann m (dec n)))))

## CLU

% Ackermann function
ack = proc (m, n: int) returns (int)
if     m=0 then return(n+1)
elseif n=0 then return(ack(m-1, 1))
else            return(ack(m-1, ack(m, n-1)))
end
end ack

% Print a table of ack( 0..3, 0..8 )
start_up = proc ()
po: stream := stream$primary_output() for m: int in int$from_to(0, 3) do
for n: int in int$from_to(0, 8) do stream$putright(po, int$unparse(ack(m,n)), 8) end stream$putl(po, "")
end
end start_up
Output:
1       2       3       4       5       6       7       8       9
2       3       4       5       6       7       8       9      10
3       5       7       9      11      13      15      17      19
5      13      29      61     125     253     509    1021    2045

## COBOL

IDENTIFICATION DIVISION.
PROGRAM-ID. Ackermann.

DATA DIVISION.
01  M          USAGE UNSIGNED-LONG.
01  N          USAGE UNSIGNED-LONG.

01  Return-Val USAGE UNSIGNED-LONG.

PROCEDURE DIVISION USING M N Return-Val.
EVALUATE M ALSO N
WHEN 0 ALSO ANY
ADD 1 TO N GIVING Return-Val

WHEN NOT 0 ALSO 0
SUBTRACT 1 FROM M
CALL "Ackermann" USING BY CONTENT M BY CONTENT 1
BY REFERENCE Return-Val

WHEN NOT 0 ALSO NOT 0
SUBTRACT 1 FROM N
CALL "Ackermann" USING BY CONTENT M BY CONTENT N
BY REFERENCE Return-Val

SUBTRACT 1 FROM M
CALL "Ackermann" USING BY CONTENT M
BY CONTENT Return-Val BY REFERENCE Return-Val
END-EVALUATE

GOBACK
.

## CoffeeScript

ackermann = (m, n) ->
if m is 0 then n + 1
else if m > 0 and n is 0 then ackermann m - 1, 1
else ackermann m - 1, ackermann m, n - 1

## Comal

0010 //
0020 // Ackermann function
0030 //
0040 FUNC a#(m#,n#)
0050   IF m#=0 THEN RETURN n#+1
0060   IF n#=0 THEN RETURN a#(m#-1,1)
0070   RETURN a#(m#-1,a#(m#,n#-1))
0080 ENDFUNC a#
0090 //
0100 // Print table of Ackermann values
0110 //
0120 ZONE 5
0130 FOR m#:=0 TO 3 DO
0140   FOR n#:=0 TO 4 DO PRINT a#(m#,n#),
0150   PRINT
0160 ENDFOR m#
0170 END
Output:
1    2    3    4    5
2    3    4    5    6
3    5    7    9    11
5    13   29   61   125

## Common Lisp

(defun ackermann (m n)
(cond ((zerop m) (1+ n))
((zerop n) (ackermann (1- m) 1))
(t         (ackermann (1- m) (ackermann m (1- n))))))

More elaborately:

(defun ackermann (m n)
(case m ((0) (1+ n))
((1) (+ 2 n))
((2) (+ n n 3))
((3) (- (expt 2 (+ 3 n)) 3))
(otherwise (ackermann (1- m) (if (zerop n) 1 (ackermann m (1- n)))))))

(loop for m from 0 to 4 do
(loop for n from (- 5 m) to (- 6 m) do
(format t "A(~d, ~d) = ~d~%" m n (ackermann m n))))
Output:
A(0, 5) = 6

A(0, 6) = 7 A(1, 4) = 6 A(1, 5) = 7 A(2, 3) = 9 A(2, 4) = 11 A(3, 2) = 29 A(3, 3) = 61 A(4, 1) = 65533

A(4, 2) = 2003529930 <... skipping a few digits ...> 56733

## Component Pascal

BlackBox Component Builder

MODULE NpctAckerman;

IMPORT  StdLog;

VAR
m,n: INTEGER;

PROCEDURE Ackerman (x,y: INTEGER):INTEGER;

BEGIN
IF    x = 0  THEN  RETURN  y + 1
ELSIF y = 0  THEN  RETURN  Ackerman (x - 1 , 1)
ELSE
RETURN  Ackerman (x - 1 , Ackerman (x , y - 1))
END
END Ackerman;

PROCEDURE Do*;
BEGIN
FOR  m := 0  TO  3  DO
FOR  n := 0  TO  6  DO
StdLog.Int (Ackerman (m, n));StdLog.Char (' ')
END;
StdLog.Ln
END;
StdLog.Ln
END Do;

END NpctAckerman.

Execute: ^Q NpctAckerman.Do

<pre>
1  2  3  4  5  6  7
2  3  4  5  6  7  8
3  5  7  9  11  13  15
5  13  29  61  125  253  509

## Coq

Require Import Arith.
Fixpoint A m := fix A_m n :=
match m with
| 0 => n + 1
| S pm =>
match n with
| 0 => A pm 1
| S pn => A pm (A_m pn)
end
end.
Require Import Utf8.

Section FOLD.
Context {A: Type} (f: A  A) (a: A).
Fixpoint fold (n: nat) : A :=
match n with
| O => a
| S n' => f (fold n')
end.
End FOLD.

Definition ackermann : nat  nat  nat :=
fold  g, fold g (g (S O))) S.

## Crystal

Translation of: Ruby
def ack(m, n)
if m == 0
n + 1
elsif n == 0
ack(m-1, 1)
else
ack(m-1, ack(m, n-1))
end
end

#Example:
(0..3).each do |m|
puts (0..6).map { |n| ack(m, n) }.join(' ')
end
Output:
1 2 3 4 5 6 7
2 3 4 5 6 7 8
3 5 7 9 11 13 15
5 13 29 61 125 253 509

## D

### Basic version

ulong ackermann(in ulong m, in ulong n) pure nothrow @nogc {
if (m == 0)
return n + 1;
if (n == 0)
return ackermann(m - 1, 1);
return ackermann(m - 1, ackermann(m, n - 1));
}

void main() {
assert(ackermann(2, 4) == 11);
}

### More Efficient Version

Translation of: Mathematica
import std.stdio, std.bigint, std.conv;

BigInt ipow(BigInt base, BigInt exp) pure nothrow {
auto result = 1.BigInt;
while (exp) {
if (exp & 1)
result *= base;
exp >>= 1;
base *= base;
}

return result;
}

BigInt ackermann(in uint m, in uint n) pure nothrow
out(result) {
assert(result >= 0);
} body {
static BigInt ack(in uint m, in BigInt n) pure nothrow {
switch (m) {
case 0: return n + 1;
case 1: return n + 2;
case 2: return 3 + 2 * n;
//case 3: return 5 + 8 * (2 ^^ n - 1);
case 3: return 5 + 8 * (ipow(2.BigInt, n) - 1);
default: return (n == 0) ?
ack(m - 1, 1.BigInt) :
ack(m - 1, ack(m, n - 1));
}
}

return ack(m, n.BigInt);
}

void main() {
foreach (immutable m; 1 .. 4)
foreach (immutable n; 1 .. 9)
writefln("ackermann(%d, %d): %s", m, n, ackermann(m, n));
writefln("ackermann(4, 1): %s", ackermann(4, 1));

immutable a = ackermann(4, 2).text;
writefln("ackermann(4, 2)) (%d digits):\n%s...\n%s",
a.length, a[0 .. 94], a[$- 96 ..$]);
}
Output:
ackermann(1, 1): 3
ackermann(1, 2): 4
ackermann(1, 3): 5
ackermann(1, 4): 6
ackermann(1, 5): 7
ackermann(1, 6): 8
ackermann(1, 7): 9
ackermann(1, 8): 10
ackermann(2, 1): 5
ackermann(2, 2): 7
ackermann(2, 3): 9
ackermann(2, 4): 11
ackermann(2, 5): 13
ackermann(2, 6): 15
ackermann(2, 7): 17
ackermann(2, 8): 19
ackermann(3, 1): 13
ackermann(3, 2): 29
ackermann(3, 3): 61
ackermann(3, 4): 125
ackermann(3, 5): 253
ackermann(3, 6): 509
ackermann(3, 7): 1021
ackermann(3, 8): 2045
ackermann(4, 1): 65533
ackermann(4, 2)) (19729 digits):
2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880...
699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156733

## Dart

no caching, the implementation takes ages even for A(4,1)

int A(int m, int n) => m==0 ? n+1 : n==0 ? A(m-1,1) : A(m-1,A(m,n-1));

main() {
print(A(0,0));
print(A(1,0));
print(A(0,1));
print(A(2,2));
print(A(2,3));
print(A(3,3));
print(A(3,4));
print(A(3,5));
print(A(4,0));
}

## Dc

This needs a modern Dc with r (swap) and # (comment). It easily can be adapted to an older Dc, but it will impact readability a lot.

[               # todo: n 0 -- n+1 and break 2 levels
+ 1 +         # n+1
q
] s1

[               # todo: m 0 -- A(m-1,1) and break 2 levels
+ 1 -         # m-1
1             # m-1 1
lA x          # A(m-1,1)
q
] s2

[               # todo: m n -- A(m,n)
r d 0=1       # n m(!=0)
r d 0=2       # m(!=0) n(!=0)
Sn            # m(!=0)
d 1 - r       # m-1 m
Ln 1 -        # m-1 m n-1
lA x          # m-1 A(m,n-1)
lA x          # A(m-1,A(m,n-1))
] sA

3 9 lA x f
Output:
4093

## Delphi

function Ackermann(m,n:Int64):Int64;
begin
if m = 0 then
Result := n + 1
else if n = 0 then
Result := Ackermann(m-1, 1)
else
Result := Ackermann(m-1, Ackermann(m, n - 1));
end;

## Draco

/* Ackermann function */
proc ack(word m, n) word:
if   m=0 then n+1
elif n=0 then ack(m-1, 1)
else          ack(m-1, ack(m, n-1))
fi
corp;

/* Write a table of Ackermann values */
proc nonrec main() void:
byte m, n;
for m from 0 upto 3 do
for n from 0 upto 8 do
write(ack(m,n) : 5)
od;
writeln()
od
corp
Output:
1    2    3    4    5    6    7    8    9
2    3    4    5    6    7    8    9   10
3    5    7    9   11   13   15   17   19
5   13   29   61  125  253  509 1021 2045

## DWScript

function Ackermann(m, n : Integer) : Integer;
begin
if m = 0 then
Result := n+1
else if n = 0 then
Result := Ackermann(m-1, 1)
else Result := Ackermann(m-1, Ackermann(m, n-1));
end;

## Dylan

define method ack(m == 0, n :: <integer>)
n + 1
end;
define method ack(m :: <integer>, n :: <integer>)
ack(m - 1, if (n == 0) 1 else ack(m, n - 1) end)
end;

## E

def A(m, n) {
return if (m <=> 0)          { n+1              } \
else if (m > 0 && n <=> 0) { A(m-1, 1)        } \
else                       { A(m-1, A(m,n-1)) }
}

## EasyLang

func ackerm m n . r .
if m = 0
r = n + 1
elif n = 0
call ackerm m - 1 1 r
else
call ackerm m n - 1 h
call ackerm m - 1 h r
.
.
call ackerm 3 6 r
print r

## Egel

def ackermann =
[ 0 N -> N + 1
| M 0 -> ackermann (M - 1) 1
| M N -> ackermann (M - 1) (ackermann M (N - 1)) ]

## Eiffel

class
ACKERMAN_EXAMPLE

feature -- Basic Operations

ackerman (m, n: NATURAL): NATURAL
-- Recursively compute the n-th term of a series.
require
non_negative_m: m >= 0
non_negative_n: n >= 0
do
if m = 0 then
Result := n + 1
elseif m > 0 and n = 0 then
Result := ackerman (m - 1, 1)
elseif m > 0 and n > 0 then
Result := ackerman (m - 1, ackerman (m, n - 1))
else
check invalid_arg_state: False end
end
end

end

## Ela

ack 0 n = n+1
ack m 0 = ack (m - 1) 1
ack m n = ack (m - 1) <| ack m <| n - 1

## Elena

ELENA 4.x :

import extensions;

ackermann(m,n)
{
if(n < 0 || m < 0)
{
InvalidArgumentException.raise()
};

m =>
0 { ^n + 1 }
: {
n =>
0 { ^ackermann(m - 1,1) }
: { ^ackermann(m - 1,ackermann(m,n-1)) }
}
}

public program()
{
for(int i:=0, i <= 3, i += 1)
{
for(int j := 0, j <= 5, j += 1)
{
console.printLine("A(",i,",",j,")=",ackermann(i,j))
}
};

}
Output:
A(0,0)=1
A(0,1)=2
A(0,2)=3
A(0,3)=4
A(0,4)=5
A(0,5)=6
A(1,0)=2
A(1,1)=3
A(1,2)=4
A(1,3)=5
A(1,4)=6
A(1,5)=7
A(2,0)=3
A(2,1)=5
A(2,2)=7
A(2,3)=9
A(2,4)=11
A(2,5)=13
A(3,0)=5
A(3,1)=13
A(3,2)=29
A(3,3)=61
A(3,4)=125
A(3,5)=253

## Elixir

defmodule Ackermann do
def ack(0, n), do: n + 1
def ack(m, 0), do: ack(m - 1, 1)
def ack(m, n), do: ack(m - 1, ack(m, n - 1))
end

Enum.each(0..3, fn m ->
IO.puts Enum.map_join(0..6, " ", fn n -> Ackermann.ack(m, n) end)
end)
Output:
1 2 3 4 5 6 7
2 3 4 5 6 7 8
3 5 7 9 11 13 15
5 13 29 61 125 253 509

## Emacs Lisp

(defun ackermann (m n)
(cond ((zerop m) (1+ n))
((zerop n) (ackermann (1- m) 1))
(t         (ackermann (1- m)
(ackermann m (1- n))))))

## Erlang

-module(ackermann).
-export([ackermann/2]).

ackermann(0, N) ->
N+1;
ackermann(M, 0) ->
ackermann(M-1, 1);
ackermann(M, N) when M > 0 andalso N > 0 ->
ackermann(M-1, ackermann(M, N-1)).

## ERRE

Iterative version, using a stack. First version used various GOTOs statement, now removed and substituted with the new ERRE control statements.

PROGRAM ACKERMAN

!
! computes Ackermann function
! (second version for rosettacode.org)
!

!$INTEGER DIM STACK[10000] !$INCLUDE="PC.LIB"

PROCEDURE ACK(M,N->N)
LOOP
CURSOR_SAVE(->CURX%,CURY%)
LOCATE(8,1)
PRINT("Livello Stack:";S;"  ")
LOCATE(CURY%,CURX%)
IF M<>0 THEN
IF N<>0 THEN
STACK[S]=M
S+=1
N-=1
ELSE
M-=1
N+=1
END IF
CONTINUE LOOP
ELSE
N+=1
S-=1
END IF
IF S<>0 THEN
M=STACK[S]
M-=1
CONTINUE LOOP
ELSE
EXIT PROCEDURE
END IF
END LOOP
END PROCEDURE

BEGIN
PRINT(CHR$(12);) FOR X=0 TO 3 DO FOR Y=0 TO 9 DO S=1 ACK(X,Y->ANS) PRINT(ANS;) END FOR PRINT END FOR END PROGRAM Prints a list of Ackermann function values: from A(0,0) to A(3,9). Uses a stack to avoid overflow. Formating options to make this pretty are available, but for this example only basic output is used. 1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 11 3 5 7 9 11 13 15 17 19 21 5 13 29 61 125 253 509 1021 2045 4093 Stack Level: 1 ## Euler Math Toolbox >M=zeros(1000,1000); >function map A(m,n) ...$  global M;
$if m==0 then return n+1; endif;$  if n==0 then return A(m-1,1); endif;
$if m<=cols(M) and n<=cols(M) then$    M[m,n]=A(m-1,A(m,n-1));
$return M[m,n];$  else return A(m-1,A(m,n-1));
$endif;$endfunction
>shortestformat; A((0:3)',0:5)
1         2         3         4         5         6
2         3         4         5         6         7
3         5         7         9        11        13
5        13        29        61       125       253

## Euphoria

This is based on the VBScript example.

function ack(atom m, atom n)
if m = 0 then
return n + 1
elsif m > 0 and n = 0 then
return ack(m - 1, 1)
else
return ack(m - 1, ack(m, n - 1))
end if
end function

for i = 0 to 3 do
for j = 0 to 6 do
printf( 1, "%5d", ack( i, j ) )
end for
puts( 1, "\n" )
end for

## Ezhil

நிரல்பாகம் அகெர்மன்(முதலெண், இரண்டாமெண்)

@((முதலெண் < 0) || (இரண்டாமெண் < 0)) ஆனால்

பின்கொடு -1

முடி

@(முதலெண் == 0) ஆனால்

பின்கொடு இரண்டாமெண்+1

முடி

@((முதலெண் > 0) && (இரண்டாமெண் == 00)) ஆனால்

பின்கொடு அகெர்மன்(முதலெண் - 1, 1)

முடி

பின்கொடு அகெர்மன்(முதலெண் - 1, அகெர்மன்(முதலெண், இரண்டாமெண் - 1))

முடி

= int(உள்ளீடு("ஓர் எண்ணைத் தாருங்கள், அது பூஜ்ஜியமாகவோ, அதைவிடப் பெரியதாக இருக்கலாம்: "))
= int(உள்ளீடு("அதேபோல் இன்னோர் எண்ணைத் தாருங்கள், இதுவும் பூஜ்ஜியமாகவோ, அதைவிடப் பெரியதாகவோ இருக்கலாம்: "))

விடை = அகெர்மன்(, )

@(விடை < 0) ஆனால்

பதிப்பி "தவறான எண்களைத் தந்துள்ளீர்கள்!"

இல்லை

பதிப்பி "நீங்கள் தந்த எண்களுக்கான அகர்மென் மதிப்பு: ", விடை

முடி

## F#

The following program implements the Ackermann function in F# but is not tail-recursive and so runs out of stack space quite fast.

let rec ackermann m n =
match m, n with
| 0, n -> n + 1
| m, 0 -> ackermann (m - 1) 1
| m, n -> ackermann (m - 1) ackermann m (n - 1)

do
printfn "%A" (ackermann (int fsi.CommandLineArgs.[1]) (int fsi.CommandLineArgs.[2]))

Transforming this into continuation passing style avoids limited stack space by permitting tail-recursion.

let ackermann M N =
let rec acker (m, n, k) =
match m,n with
| 0, n -> k(n + 1)
| m, 0 -> acker ((m - 1), 1, k)
| m, n -> acker (m, (n - 1), (fun x -> acker ((m - 1), x, k)))
acker (M, N, (fun x -> x))

## Factor

USING: kernel math locals combinators ;
IN: ackermann

:: ackermann ( m n -- u )
{
{ [ m 0 = ] [ n 1 + ] }
{ [ n 0 = ] [ m 1 - 1 ackermann ] }
[ m 1 - m n 1 - ackermann ackermann ]
} cond ;

## Falcon

function ackermann( m, n )
if m == 0:  return( n + 1 )
if n == 0:  return( ackermann( m - 1, 1 ) )
return( ackermann( m - 1, ackermann( m, n - 1 ) ) )
end

for M in [ 0:4 ]
for N in [ 0:7 ]
>> ackermann( M, N ), " "
end
>
end

The above will output the below. Formating options to make this pretty are available, but for this example only basic output is used.

1 2 3 4 5 6 7
2 3 4 5 6 7 8
3 5 7 9 11 13 15
5 13 29 61 125 253 509

## FALSE

[$$[% \$$[%
1-\$@@a;! { i j -> A(i-1, A(i, j-1)) } 1]?0=[ %1 { i 0 -> A(i-1, 1) } ]? \1-a;! 1]?0=[ %1+ { 0 j -> j+1 } ]?]a: { j i } 3 3 a;! . { 61 } ## Fantom class Main { // assuming m,n are positive static Int ackermann (Int m, Int n) { if (m == 0) return n + 1 else if (n == 0) return ackermann (m - 1, 1) else return ackermann (m - 1, ackermann (m, n - 1)) } public static Void main () { (0..3).each |m| { (0..6).each |n| { echo ("Ackerman($m, $n) =${ackermann(m, n)}")
}
}
}
}
Output:
Ackerman(0, 0) = 1
Ackerman(0, 1) = 2
Ackerman(0, 2) = 3
Ackerman(0, 3) = 4
Ackerman(0, 4) = 5
Ackerman(0, 5) = 6
Ackerman(0, 6) = 7
Ackerman(1, 0) = 2
Ackerman(1, 1) = 3
Ackerman(1, 2) = 4
Ackerman(1, 3) = 5
Ackerman(1, 4) = 6
Ackerman(1, 5) = 7
Ackerman(1, 6) = 8
Ackerman(2, 0) = 3
Ackerman(2, 1) = 5
Ackerman(2, 2) = 7
Ackerman(2, 3) = 9
Ackerman(2, 4) = 11
Ackerman(2, 5) = 13
Ackerman(2, 6) = 15
Ackerman(3, 0) = 5
Ackerman(3, 1) = 13
Ackerman(3, 2) = 29
Ackerman(3, 3) = 61
Ackerman(3, 4) = 125
Ackerman(3, 5) = 253
Ackerman(3, 6) = 509

## FBSL

Mixed-language solution using pure FBSL, Dynamic Assembler, and Dynamic C layers of FBSL v3.5 concurrently. The following is a single script; the breaks are caused by switching between RC's different syntax highlighting schemes:

#APPTYPE CONSOLE

TestAckermann()

PAUSE

SUB TestAckermann()
FOR DIM m = 0 TO 3
FOR DIM n = 0 TO 10
PRINT AckermannF(m, n), " ";
NEXT
PRINT
NEXT
END SUB

FUNCTION AckermannF(m AS INTEGER, n AS INTEGER) AS INTEGER
IF NOT m THEN RETURN n + 1
IF NOT n THEN RETURN AckermannA(m - 1, 1)
RETURN AckermannC(m - 1, AckermannF(m, n - 1))
END FUNCTION

DYNC AckermannC(m AS INTEGER, n AS INTEGER) AS INTEGER
int Ackermann(int m, int n)
{
if (!m) return n + 1;
if (!n) return Ackermann(m - 1, 1);
return Ackermann(m - 1, Ackermann(m, n - 1));
}

int main(int m, int n)
{
return Ackermann(m, n);
}
END DYNC

DYNASM AckermannA(m AS INTEGER, n AS INTEGER) AS INTEGER
ENTER 0, 0
INVOKE Ackermann, m, n
LEAVE
RET

@Ackermann
ENTER 0, 0

.IF DWORD PTR [m] .THEN
JMP @F
.ENDIF
MOV EAX, n
INC EAX
JMP xit

@@
.IF DWORD PTR [n] .THEN
JMP @F
.ENDIF
MOV EAX, m
DEC EAX
INVOKE Ackermann, EAX, 1
JMP xit

@@
MOV EAX, n
DEC EAX
INVOKE Ackermann, m, EAX
MOV ECX, m
DEC ECX
INVOKE Ackermann, ECX, EAX

@xit
LEAVE
RET 8
END DYNASM
Output:
1 2 3 4 5 6 7 8 9 10 11
2 3 4 5 6 7 8 9 10 11 12
3 5 7 9 11 13 15 17 19 21 23
5 13 29 61 125 253 509 1021 2045 4093 8189

Press any key to continue...

## Fermat

Func A(m,n) = if m = 0 then n+1 else if n = 0 then A(m-1,1) else A(m-1,A(m,n-1)) fi fi.;
A(3,8)
Output:
2045

## Forth

: acker ( m n -- u )
over 0= IF  nip 1+ EXIT  THEN
swap 1- swap ( m-1 n -- )
dup  0= IF  1+  recurse EXIT  THEN
1- over 1+ swap recurse recurse ;
Example of use:
FORTH> 0 0 acker . 1  ok
FORTH> 3 4 acker . 125  ok

An optimized version:

: ackermann                            ( m n -- u )
over                                 ( case statement)
0 over = if drop nip 1+     else
1 over = if drop nip 2 +    else
2 over = if drop nip 2* 3 + else
3 over = if drop swap 5 + swap lshift 3 - else
drop swap 1- swap dup
if
1- over 1+ swap recurse recurse exit
else
1+ recurse exit                  \ allow tail recursion
then
then then then then
;

## Fortran

Works with: Fortran version 90 and later
PROGRAM EXAMPLE
IMPLICIT NONE

INTEGER :: i, j

DO i = 0, 3
DO j = 0, 6
END DO
WRITE(*,*)
END DO

CONTAINS

RECURSIVE FUNCTION Ackermann(m, n) RESULT(ack)
INTEGER :: ack, m, n

IF (m == 0) THEN
ack = n + 1
ELSE IF (n == 0) THEN
ack = Ackermann(m - 1, 1)
ELSE
ack = Ackermann(m - 1, Ackermann(m, n - 1))
END IF
END FUNCTION Ackermann

END PROGRAM EXAMPLE

## Free Pascal

See #Delphi or #Pascal.

## FreeBASIC

' version 28-10-2016
' compile with: fbc -s console
' to do A(4, 2) the stack size needs to be increased
' compile with: fbc -s console -t 2000

Function ackerman (m As Long, n As Long) As Long

If m = 0 Then ackerman = n +1

If m > 0 Then
If n = 0 Then
ackerman = ackerman(m -1, 1)
Else
If n > 0 Then
ackerman = ackerman(m -1, ackerman(m, n -1))
End If
End If
End If
End Function

' ------=< MAIN >=------

Dim As Long m, n
Print

For m = 0 To 4
Print Using "###"; m;
For n = 0 To 10
' A(4, 1) or higher will run out of stack memory (default 1M)
' change n = 1 to n = 2 to calculate A(4, 2), increase stack!
If m = 4 And n = 1 Then Exit For
Print Using "######"; ackerman(m, n);
Next
Print
Next

' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
Output:
0     1     2     3     4     5     6     7     8     9    10    11
1     2     3     4     5     6     7     8     9    10    11    12
2     3     5     7     9    11    13    15    17    19    21    23
3     5    13    29    61   125   253   509  1021  2045  4093  8189
4    13

## FunL

def
ackermann( 0, n ) = n + 1
ackermann( m, 0 ) = ackermann( m - 1, 1 )
ackermann( m, n ) = ackermann( m - 1, ackermann(m, n - 1) )

for m <- 0..3, n <- 0..4
printf( 'Ackermann( %d, %d ) = %d\n', m, n, ackermann(m, n) )
Output:
Ackermann( 0, 0 ) = 1
Ackermann( 0, 1 ) = 2
Ackermann( 0, 2 ) = 3
Ackermann( 0, 3 ) = 4
Ackermann( 0, 4 ) = 5
Ackermann( 1, 0 ) = 2
Ackermann( 1, 1 ) = 3
Ackermann( 1, 2 ) = 4
Ackermann( 1, 3 ) = 5
Ackermann( 1, 4 ) = 6
Ackermann( 2, 0 ) = 3
Ackermann( 2, 1 ) = 5
Ackermann( 2, 2 ) = 7
Ackermann( 2, 3 ) = 9
Ackermann( 2, 4 ) = 11
Ackermann( 3, 0 ) = 5
Ackermann( 3, 1 ) = 13
Ackermann( 3, 2 ) = 29
Ackermann( 3, 3 ) = 61
Ackermann( 3, 4 ) = 125

## Futhark

fun ackermann(m: int, n: int): int =
if m == 0 then n + 1
else if n == 0 then ackermann(m-1, 1)
else ackermann(m - 1, ackermann(m, n-1))

## FutureBasic

include "NSLog.incl"

local fn Ackerman( m as NSInteger, n as NSInteger ) as NSInteger
NSInteger result

select
case m == 0 : result = ( n + 1 )
case n == 0 : result = fn Ackerman( ( m - 1 ), 1 )
case else   : result = fn Ackerman( ( m - 1 ), fn Ackerman( m, ( n - 1 ) ) )
end select
end fn = result

NSInteger          m, n
CFMutableStringRef mutStr

mutStr = fn StringWithCapacity( 0 )

for m = 0 to 3
for n = 0 to 9
StringAppendString( mutStr, fn StringWithFormat( @"fn Ackerman( %ld, %ld ) = %ld\n", m, n, fn Ackerman( m, n ) ) )
next
next

NSLog( @"%@", mutStr )

HandleEvents

Output:

fn Ackerman( 0, 0 ) = 1
fn Ackerman( 0, 1 ) = 2
fn Ackerman( 0, 2 ) = 3
fn Ackerman( 0, 3 ) = 4
fn Ackerman( 0, 4 ) = 5
fn Ackerman( 0, 5 ) = 6
fn Ackerman( 0, 6 ) = 7
fn Ackerman( 0, 7 ) = 8
fn Ackerman( 0, 8 ) = 9
fn Ackerman( 0, 9 ) = 10
fn Ackerman( 1, 0 ) = 2
fn Ackerman( 1, 1 ) = 3
fn Ackerman( 1, 2 ) = 4
fn Ackerman( 1, 3 ) = 5
fn Ackerman( 1, 4 ) = 6
fn Ackerman( 1, 5 ) = 7
fn Ackerman( 1, 6 ) = 8
fn Ackerman( 1, 7 ) = 9
fn Ackerman( 1, 8 ) = 10
fn Ackerman( 1, 9 ) = 11
fn Ackerman( 2, 0 ) = 3
fn Ackerman( 2, 1 ) = 5
fn Ackerman( 2, 2 ) = 7
fn Ackerman( 2, 3 ) = 9
fn Ackerman( 2, 4 ) = 11
fn Ackerman( 2, 5 ) = 13
fn Ackerman( 2, 6 ) = 15
fn Ackerman( 2, 7 ) = 17
fn Ackerman( 2, 8 ) = 19
fn Ackerman( 2, 9 ) = 21
fn Ackerman( 3, 0 ) = 5
fn Ackerman( 3, 1 ) = 13
fn Ackerman( 3, 2 ) = 29
fn Ackerman( 3, 3 ) = 61
fn Ackerman( 3, 4 ) = 125
fn Ackerman( 3, 5 ) = 253
fn Ackerman( 3, 6 ) = 509
fn Ackerman( 3, 7 ) = 1021
fn Ackerman( 3, 8 ) = 2045
fn Ackerman( 3, 9 ) = 4093

## Fōrmulæ

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.

Programs in Fōrmulæ are created/edited online in its website, However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.

## Gambas

Public Function Ackermann(m As Float, n As Float) As Float
If m = 0 Then
Return n + 1
End If
If n = 0 Then
Return Ackermann(m - 1, 1)
End If
Return Ackermann(m - 1, Ackermann(m, n - 1))
End

Public Sub Main()
Dim m, n As Float
For m = 0 To 3
For n = 0 To 4
Print "Ackermann("; m; ", "; n; ") = "; Ackermann(m, n)
Next
Next
End

## GAP

ack := function(m, n)
if m = 0 then
return n + 1;
elif (m > 0) and (n = 0) then
return ack(m - 1, 1);
elif (m > 0) and (n > 0) then
return ack(m - 1, ack(m, n - 1));
else
return fail;
fi;
end;

## Genyris

def A (m n)
cond
(equal? m 0)
+ n 1
(equal? n 0)
A (- m 1) 1
else
A (- m 1)
A m (- n 1)

## GML

Define a script resource named ackermann and paste this code inside:

///ackermann(m,n)
var m, n;
m = argument0;
n = argument1;
if(m=0)
{
return (n+1)
}
else if(n == 0)
{
return (ackermann(m-1,1,1))
}
else
{
return (ackermann(m-1,ackermann(m,n-1,2),1))
}

## gnuplot

A (m, n) = m == 0 ? n + 1 : n == 0 ? A (m - 1, 1) : A (m - 1, A (m, n - 1))
print A (0, 4)
print A (1, 4)
print A (2, 4)
print A (3, 4)
Output:
5
6
11
stack overflow

## Go

### Classic version

func Ackermann(m, n uint) uint {
switch 0 {
case m:
return n + 1
case n:
return Ackermann(m - 1, 1)
}
return Ackermann(m - 1, Ackermann(m, n - 1))
}

### Expanded version

func Ackermann2(m, n uint) uint {
switch {
case m == 0:
return n + 1
case m == 1:
return n + 2
case m == 2:
return 2*n + 3
case m == 3:
return 8 << n - 3
case n == 0:
return Ackermann2(m - 1, 1)
}
return Ackermann2(m - 1, Ackermann2(m, n - 1))
}

### Expanded version with arbitrary precision

package main

import (
"fmt"
"math/big"
"math/bits" // Added in Go 1.9
)

var one = big.NewInt(1)
var two = big.NewInt(2)
var three = big.NewInt(3)
var eight = big.NewInt(8)

func Ackermann2(m, n *big.Int) *big.Int {
if m.Cmp(three) <= 0 {
switch m.Int64() {
case 0:
case 1:
case 2:
r := new(big.Int).Lsh(n, 1)
case 3:
if nb := n.BitLen(); nb > bits.UintSize {
// n is too large to represent as a
// uint for use in the Lsh method.
panic(TooBigError(nb))

// If we tried to continue anyway, doing
// 8*2^n-3 as bellow, we'd use hundreds
// of megabytes and lots of CPU time
// without the Exp call even returning.
r := new(big.Int).Exp(two, n, nil)
r.Mul(eight, r)
return r.Sub(r, three)
}
r := new(big.Int).Lsh(eight, uint(n.Int64()))
return r.Sub(r, three)
}
}
if n.BitLen() == 0 {
return Ackermann2(new(big.Int).Sub(m, one), one)
}
return Ackermann2(new(big.Int).Sub(m, one),
Ackermann2(m, new(big.Int).Sub(n, one)))
}

type TooBigError int

func (e TooBigError) Error() string {
return fmt.Sprintf("A(m,n) had n of %d bits; too large", int(e))
}

func main() {
show(0, 0)
show(1, 2)
show(2, 4)
show(3, 100)
show(3, 1e6)
show(4, 1)
show(4, 2)
show(4, 3)
}

func show(m, n int64) {
defer func() {
// Ackermann2 could/should have returned an error
// instead of a panic. But here's how to recover
// from the panic, and report "expected" errors.
if e := recover(); e != nil {
if err, ok := e.(TooBigError); ok {
fmt.Println("Error:", err)
} else {
panic(e)
}
}
}()

fmt.Printf("A(%d, %d) = ", m, n)
a := Ackermann2(big.NewInt(m), big.NewInt(n))
if a.BitLen() <= 256 {
fmt.Println(a)
} else {
s := a.String()
fmt.Printf("%d digits starting/ending with: %s...%s\n",
len(s), s[:20], s[len(s)-20:],
)
}
}
Output:
A(0, 0) = 1
A(1, 2) = 4
A(2, 4) = 11
A(3, 100) = 10141204801825835211973625643005
A(3, 1000000) = 301031 digits starting/ending with: 79205249834367186005...39107225301976875005
A(4, 1) = 65533
A(4, 2) = 19729 digits starting/ending with: 20035299304068464649...45587895905719156733
A(4, 3) = Error: A(m,n) had n of 65536 bits; too large

## Golfscript

{
:_n; :_m;
_m 0= {_n 1+}
{_n 0= {_m 1- 1 ack}
{_m 1- _m _n 1- ack ack}
if}
if
}:ack;

## Groovy

def ack ( m, n ) {
assert m >= 0 && n >= 0 : 'both arguments must be non-negative'
m == 0 ? n + 1 : n == 0 ? ack(m-1, 1) : ack(m-1, ack(m, n-1))
}

Test program:

def ackMatrix = (0..3).collect { m -> (0..8).collect { n -> ack(m, n) } }
ackMatrix.each { it.each { elt -> printf "%7d", elt }; println() }
Output:
1      2      3      4      5      6      7      8      9
2      3      4      5      6      7      8      9     10
3      5      7      9     11     13     15     17     19
5     13     29     61    125    253    509   1021   2045

Note: In the default groovyConsole configuration for WinXP, "ack(4,1)" caused a stack overflow error!

## Hare

use fmt;

fn ackermann(m: u64, n: u64) u64 = {
if (m == 0) {
return n + 1;
};
if (n == 0) {
return ackermann(m - 1, 1);
};
return ackermann(m - 1, ackermann(m, n - 1));
};

export fn main() void = {
for (let m = 0u64; m < 4; m += 1) {
for (let n = 0u64; n < 10; n += 1) {
fmt::printfln("A({}, {}) = {}", m, n, ackermann(m, n))!;
};
fmt::println()!;
};
};

ack :: Int -> Int -> Int
ack 0 n = succ n
ack m 0 = ack (pred m) 1
ack m n = ack (pred m) (ack m (pred n))

main :: IO ()
main = mapM_ print $uncurry ack <$> [(0, 0), (3, 4)]
Output:
1
125

import Data.List (mapAccumL)

-- everything here are [Int] or [[Int]], which would overflow
-- * had it not overrun the stack first *
ackermann = iterate ack [1..] where
ack a = s where
s = snd $mapAccumL f (tail a) (1 : zipWith (-) s (1:s)) f a b = (aa, head aa) where aa = drop b a main = mapM_ print$ map (\n -> take (6 - n) $ackermann !! n) [0..5] ## Haxe class RosettaDemo { static public function main() { Sys.print(ackermann(3, 4)); } static function ackermann(m : Int, n : Int) { if (m == 0) { return n + 1; } else if (n == 0) { return ackermann(m-1, 1); } return ackermann(m-1, ackermann(m, n-1)); } } ## Hoon |= [m=@ud n=@ud] ?: =(m 0) +(n) ?: =(n 0)$(n 1, m (dec m))
$(m (dec m), n$(n (dec n)))

## Icon and Unicon

Taken from the public domain Icon Programming Library's acker in memrfncs, written by Ralph E. Griswold.

procedure acker(i, j)
static memory

initial {
memory := table()
every memory[0 to 100] := table()
}

if i = 0 then return j + 1

if j = 0 then /memory[i][j] := acker(i - 1, 1)
else /memory[i][j] := acker(i - 1, acker(i, j - 1))

return memory[i][j]

end

procedure main()
every m := 0 to 3 do {
every n := 0 to 8 do {
writes(acker(m, n) || " ")
}
write()
}
end
Output:
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 10
3 5 7 9 11 13 15 17 19
5 13 29 61 125 253 509 1021 2045

## Idris

A : Nat -> Nat -> Nat
A Z n = S n
A (S m) Z = A m (S Z)
A (S m) (S n) = A m (A (S m) n)

## Ioke

Translation of: Clojure
ackermann = method(m,n,
cond(
m zero?, n succ,
n zero?, ackermann(m pred, 1),
ackermann(m pred, ackermann(m, n pred)))
)

## J

As posted at the J wiki

ack=: c1c1c2c3 @. (#.@,&*) M.
c1=: >:@]                        NB. if 0=x, 1+y
c2=: <:@[ ack 1:                 NB. if 0=y, (x-1) ack 1
c3=: <:@[ ack [ ack <:@]         NB. else,   (x-1) ack x ack y-1
Example use:
0 ack 3
4
1 ack 3
5
2 ack 3
9
3 ack 3
61

J's stack was too small for me to compute 4 ack 1.

### Alternative Primitive Recursive Version

This version works by first generating verbs (functions) and then applying them to compute the rows of the related Buck function; then the Ackermann function is obtained in terms of the Buck function. It uses extended precision to be able to compute 4 Ack 2.

The Ackermann function derived in this fashion is primitive recursive. This is possible because in J (as in some other languages) functions, or representations of them, are first-class values.

Ack=. 3 -~ [ ({&(2 4$'>: 2x&+') ::(,&'&1'&'2x&*'@:(-&2))"0@:[ 128!:2 ]) 3 + ] Example use: 0 1 2 3 Ack 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 3 5 7 9 11 13 15 17 5 13 29 61 125 253 509 1021 3 4 Ack 0 1 2 5 13 ... 13 65533 2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933348101038234342907263181822949382118812668869506364761547029165041871916351587966347219442930927982084309104855990570159318959639524863372367203002916... 4 # @: ": @: Ack 2 NB. Number of digits of 4 Ack 2 19729 5 Ack 0 65533 A structured derivation of Ack follows: o=. @: NB. Composition of verbs (functions) x=. o[ NB. Composing the left noun (argument) (rows2up=. ,&'&1'&'2x&*') o i. 4 2x&* 2x&*&1 2x&*&1&1 2x&*&1&1&1 NB. 2's multiplication, exponentiation, tetration, pentation, etc. 0 1 2 (BuckTruncated=. (rows2up x apply ]) f.) 0 1 2 3 4 5 0 2 4 6 8 ... 1 2 4 8 16 ... 1 2 4 16 65536 2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933348101038234342907263181822949382118812668869506364761547029165041871916351587966347219442930927982084309104855990570159318959639524863372367203... NB. Buck truncated function (missing the first two rows) BuckTruncated NB. Buck truncated function-level code ,&'&1'&'2x&*'@:[ 128!:2 ] (rows01=. {&('>:',:'2x&+')) 0 1 NB. The missing first two rows >: 2x&+ Buck=. (rows01 :: (rows2up o (-&2)))"0 x apply ] (Ack=. (3 -~ [ Buck 3 + ])f.) NB. Ackermann function-level code 3 -~ [ ({&(2 4$'>:  2x&+') ::(,&'&1'&'2x&*'@:(-&2))"0@:[ 128!:2 ]) 3 + ]

## Java

import java.math.BigInteger;

public static BigInteger ack(BigInteger m, BigInteger n) {
return m.equals(BigInteger.ZERO)
: ack(m.subtract(BigInteger.ONE),
n.equals(BigInteger.ZERO) ? BigInteger.ONE : ack(m, n.subtract(BigInteger.ONE)));
}
Works with: Java version 8+
@FunctionalInterface
public interface FunctionalField<FIELD extends Enum<?>> {
public Object untypedField(FIELD field);

@SuppressWarnings("unchecked")
public default <VALUE> VALUE field(FIELD field) {
return (VALUE) untypedField(field);
}
}
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
import java.util.stream.Stream;

public interface TailRecursive {
public static <INPUT, INTERMEDIARY, OUTPUT> Function<INPUT, OUTPUT> new_(Function<INPUT, INTERMEDIARY> toIntermediary, UnaryOperator<INTERMEDIARY> unaryOperator, Predicate<INTERMEDIARY> predicate, Function<INTERMEDIARY, OUTPUT> toOutput) {
return input ->
$.new_( Stream.iterate( toIntermediary.apply(input), unaryOperator ), predicate, toOutput ) ; } public static <INPUT1, INPUT2, INTERMEDIARY, OUTPUT> BiFunction<INPUT1, INPUT2, OUTPUT> new_(BiFunction<INPUT1, INPUT2, INTERMEDIARY> toIntermediary, UnaryOperator<INTERMEDIARY> unaryOperator, Predicate<INTERMEDIARY> predicate, Function<INTERMEDIARY, OUTPUT> toOutput) { return (input1, input2) ->$.new_(
Stream.iterate(
toIntermediary.apply(input1, input2),
unaryOperator
),
predicate,
toOutput
)
;
}

end ;

Example:

range(0;5) as $i | range(0; if$i > 3 then 1 else 6 end) as $j | "A(\($i),\($j)) = \( [$i,$j] | ack )" Output: # jq -n -r -f ackermann.jq A(0,0) = 1 A(0,1) = 2 A(0,2) = 3 A(0,3) = 4 A(0,4) = 5 A(0,5) = 6 A(1,0) = 2 A(1,1) = 3 A(1,2) = 4 A(1,3) = 5 A(1,4) = 6 A(1,5) = 7 A(2,0) = 3 A(2,1) = 5 A(2,2) = 7 A(2,3) = 9 A(2,4) = 11 A(2,5) = 13 A(3,0) = 5 A(3,1) = 13 A(3,2) = 29 A(3,3) = 61 A(3,4) = 125 A(3,5) = 253 A(4,0) = 13 ### With Memoization and Optimization # input: [m,n, cache] # output [value, updatedCache] def ack: # input: [value,cache]; output: [value, updatedCache] def cache(key): .[1] += { (key): .[0] }; def pow2: reduce range(0; .) as$i (1; .*2);

.[0] as $m | .[1] as$n | .[2] as $cache | if$m == 0 then [$n + 1,$cache]
elif $m == 1 then [$n + 2, $cache] elif$m == 2 then [2 * $n + 3,$cache]
elif $m == 3 then [8 * ($n|pow2) - 3, $cache] else (.[0:2]|tostring) as$key
| $cache[$key] as $value | if$value then [$value,$cache]
elif $n == 0 then ([$m-1, 1, $cache] | ack) | cache($key)
else
([$m,$n-1, $cache ] | ack) | [$m-1, .[0], .[1]] | ack
ack(1,3) ==> 5
ack(2,3) ==> 9
ack(3,3) ==> 61
ack(1,5) ==> 7
ack(2,5) ==> 13
ack(3,5) ==> 253

## Julia

function ack(m,n)
if m == 0
return n + 1
elseif n == 0
return ack(m-1,1)
else
return ack(m-1,ack(m,n-1))
end
end

One-liner:

ack2(m::Integer, n::Integer) = m == 0 ? n + 1 : n == 0 ? ack2(m - 1, 1) : ack2(m - 1, ack2(m, n - 1))

Using memoization, source:

using Memoize
@memoize ack3(m::Integer, n::Integer) = m == 0 ? n + 1 : n == 0 ? ack3(m - 1, 1) : ack3(m - 1, ack3(m, n - 1))

Benchmarking:

julia> @time ack2(4,1)
elapsed time: 71.98668457 seconds (96 bytes allocated)
65533

julia> @time ack3(4,1)
elapsed time: 0.49337724 seconds (30405308 bytes allocated)
65533

## K

See the K wiki

ack:{:[0=x;y+1;0=y;_f[x-1;1];_f[x-1;_f[x;y-1]]]}
ack[2;2]

## Kdf9 Usercode

V6; W0;
YS26000;
RESTART; J999; J999;
PROGRAM;                   (main program);
V1 = B1212121212121212; (radix 10 for FRB);
V2 = B2020202020202020; (high bits for decimal digits);
V3 = B0741062107230637; ("A[3,"  in Flexowriter code);
V4 = B0727062200250007; ("7] = " in Flexowriter code);
V5 = B7777777777777777;

ZERO; NOT; =M1;      (Q1 := 0/0/-1);
SETAYS0; =M2; I2=2;  (Q2 := 0/2/AYS0: M2 is the stack pointer);
SET 3; =RC7;         (Q7 := 3/1/0: C7 = m);
SET 7; =RC8;         (Q8 := 7/1/0: C8 = n);
JSP1;                   (call Ackermann function);
V1; REV; FRB;        (convert result to base 10);
V2; OR;              (convert decimal digits to characters);
V5; REV;
SHLD+24; =V5; ERASE; (eliminate leading zeros);
SETAV5; =RM9;
SETAV3; =I9;
POAQ9;               (write result to Flexowriter);

999;  ZERO; OUT;           (terminate run);

P1; (To compute A[m, n]);

99;
J1C7NZ;           (to 1 if m ± 0);
I8; =+C8;      (n := n + 1);
C8;            (result to NEST);
EXIT 1;           (return);
*1;
J2C8NZ;           (to 2 if n ± 0);
I8; =C8;       (n := 1);
DC7;           (m := m - 1);
J99;              (tail recursion for A[m-1, 1]);
*2;
C7; =M0M2QN;   (push m);
DC8;           (n := n - 1);
JSP1;             (full recursion for A[m, n-1]);
=C8;           (n := A[m, n-1]);
M1M2; =C7;     (m := top of stack);
DC7;           (m := m - 1);
M-I2;          (pop stack);
J99;              (tail recursion for A[m-1, A[m, n-1]]);

FINISH;

## Klingphix

:ack
%n !n %m !m

$m 0 == ( [$n 1 +]
[$n 0 == ( [$m 1 - 1 ack]
[$m 1 -$m $n 1 - ack ack] ) if ] ) if ; 3 6 ack print nl msec print " " input ## Klong ack::{:[0=x;y+1:|0=y;.f(x-1;1);.f(x-1;.f(x;y-1))]} ack(2;2) ## Kotlin tailrec fun A(m: Long, n: Long): Long { require(m >= 0L) { "m must not be negative" } require(n >= 0L) { "n must not be negative" } if (m == 0L) { return n + 1L } if (n == 0L) { return A(m - 1L, 1L) } return A(m - 1L, A(m, n - 1L)) } inline fun<T> tryOrNull(block: () -> T): T? = try { block() } catch (e: Throwable) { null } const val N = 10L const val M = 4L fun main() { (0..M) .map { it to 0..N } .map { (m, Ns) -> (m to Ns) to Ns.map { n -> tryOrNull { A(m, n) } } } .map { (input, output) -> "A(${input.first}, ${input.second})" to output.map { it?.toString() ?: "?" } } .map { (input, output) -> "$input = $output" } .forEach(::println) } Output: A(0, 0..10) = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] A(1, 0..10) = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] A(2, 0..10) = [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23] A(3, 0..10) = [5, 13, 29, 61, 125, 253, 509, 1021, 2045, 4093, 8189] A(4, 0..10) = [13, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?] ## Lambdatalk {def ack {lambda {:m :n} {if {= :m 0} then {+ :n 1} else {if {= :n 0} then {ack {- :m 1} 1} else {ack {- :m 1} {ack :m {- :n 1}}}}}}} -> ack {S.map {ack 0} {S.serie 0 300000}} // 2090ms {S.map {ack 1} {S.serie 0 500}} // 2038ms {S.map {ack 2} {S.serie 0 70}} // 2100ms {S.map {ack 3} {S.serie 0 6}} // 1800ms {ack 2 700} // 8900ms -> 1403 {ack 3 7} // 6000ms -> 1021 {ack 4 1} // too much -> ??? ## Lasso #!/usr/bin/lasso9 define ackermann(m::integer, n::integer) => { if(#m == 0) => { return ++#n else(#n == 0) return ackermann(--#m, 1) else return ackermann(#m-1, ackermann(#m, --#n)) } } with x in generateSeries(1,3), y in generateSeries(0,8,2) do stdoutnl(#x+', '#y+': ' + ackermann(#x, #y)) Output: 1, 0: 2 1, 2: 4 1, 4: 6 1, 6: 8 1, 8: 10 2, 0: 3 2, 2: 7 2, 4: 11 2, 6: 15 2, 8: 19 3, 0: 5 3, 2: 29 3, 4: 125 3, 6: 509 3, 8: 2045 ## LFE (defun ackermann ((0 n) (+ n 1)) ((m 0) (ackermann (- m 1) 1)) ((m n) (ackermann (- m 1) (ackermann m (- n 1))))) ## Liberty BASIC Print Ackermann(1, 2) Function Ackermann(m, n) Select Case Case (m < 0) Or (n < 0) Exit Function Case (m = 0) Ackermann = (n + 1) Case (m > 0) And (n = 0) Ackermann = Ackermann((m - 1), 1) Case (m > 0) And (n > 0) Ackermann = Ackermann((m - 1), Ackermann(m, (n - 1))) End Select End Function ## LiveCode function ackermann m,n switch Case m = 0 return n + 1 Case (m > 0 And n = 0) return ackermann((m - 1), 1) Case (m > 0 And n > 0) return ackermann((m - 1), ackermann(m, (n - 1))) end switch end ackermann ## Logo to ack :i :j if :i = 0 [output :j+1] if :j = 0 [output ack :i-1 1] output ack :i-1 ack :i :j-1 end ## Logtalk ack(0, N, V) :- !, V is N + 1. ack(M, 0, V) :- !, M2 is M - 1, ack(M2, 1, V). ack(M, N, V) :- M2 is M - 1, N2 is N - 1, ack(M, N2, V2), ack(M2, V2, V). ## LOLCODE Translation of: C HAI 1.3 HOW IZ I ackermann YR m AN YR n NOT m, O RLY? YA RLY, FOUND YR SUM OF n AN 1 OIC NOT n, O RLY? YA RLY, FOUND YR I IZ ackermann YR DIFF OF m AN 1 AN YR 1 MKAY OIC FOUND YR I IZ ackermann YR DIFF OF m AN 1 AN YR... I IZ ackermann YR m AN YR DIFF OF n AN 1 MKAY MKAY IF U SAY SO IM IN YR outer UPPIN YR m TIL BOTH SAEM m AN 5 IM IN YR inner UPPIN YR n TIL BOTH SAEM n AN DIFF OF 6 AN m VISIBLE "A(" m ", " n ") = " I IZ ackermann YR m AN YR n MKAY IM OUTTA YR inner IM OUTTA YR outer KTHXBYE ## Lua function ack(M,N) if M == 0 then return N + 1 end if N == 0 then return ack(M-1,1) end return ack(M-1,ack(M, N-1)) end ### Stackless iterative solution with multiple precision, fast #!/usr/bin/env luajit local gmp = require 'gmp' ('libgmp') local mpz, z_mul, z_add, z_add_ui, z_set_d = gmp.types.z, gmp.z_mul, gmp.z_add, gmp.z_add_ui, gmp.z_set_d local z_cmp, z_cmp_ui, z_init_d, z_set= gmp.z_cmp, gmp.z_cmp_ui, gmp.z_init_set_d, gmp.z_set local printf = gmp.printf local function ack(i,n) local nxt=setmetatable({}, {__index=function(t,k) local z=mpz() z_init_d(z, 0) t[k]=z return z end}) local goal=setmetatable({}, {__index=function(t,k) local o=mpz() z_init_d(o, 1) t[k]=o return o end}) goal[i]=mpz() z_init_d(goal[i], -1) local v=mpz() z_init_d(v, 0) local ic local END=n+1 local ntmp,gtmp repeat ic=0 ntmp,gtmp=nxt[ic], goal[ic] z_add_ui(v, ntmp, 1) while z_cmp(ntmp, gtmp) == 0 do z_set(gtmp,v) z_add_ui(ntmp, ntmp, 1) nxt[ic], goal[ic]=ntmp, gtmp ic=ic+1 ntmp,gtmp=nxt[ic], goal[ic] end z_add_ui(ntmp, ntmp, 1) nxt[ic]=ntmp until z_cmp_ui(nxt[i], END) == 0 return v end if #arg<1 then print("Ackermann: "..arg[0].." <num1> [num2]") else printf("%Zd\n", ack(tonumber(arg[1]), arg[2] and tonumber(arg[2]) or 0)) end Output: > time ./ackermann_iter.lua 4 1 65533 ./ackermann_iter.lua 4 1 0,01s user 0,01s system 95% cpu 0,015 total // AMD FX-8350@4 GHz > time ./ackermann.lua 3 10 ⏎ 8189 ./ackermann.lua 3 10 0,22s user 0,00s system 98% cpu 0,222 total // recursive solution > time ./ackermann_iter.lua 3 10 8189 ./ackermann_iter.lua 3 10 0,00s user 0,00s system 92% cpu 0,009 total ## Lucid ack(m,n) where ack(m,n) = if m eq 0 then n+1 else if n eq 0 then ack(m-1,1) else ack(m-1, ack(m, n-1)) fi fi; end ## Luck function ackermann(m: int, n: int): int = ( if m==0 then n+1 else if n==0 then ackermann(m-1,1) else ackermann(m-1,ackermann(m,n-1)) ) ## M2000 Interpreter Module Checkit { Def ackermann(m,n) =If(m=0-> n+1, If(n=0-> ackermann(m-1,1), ackermann(m-1,ackermann(m,n-1)))) For m = 0 to 3 {For n = 0 to 4 {Print m;" ";n;" ";ackermann(m,n)}} } Checkit Module Checkit { Module Inner (ack) { For m = 0 to 3 {For n = 0 to 4 {Print m;" ";n;" ";ack(m,n)}} } Inner lambda (m,n) ->If(m=0-> n+1, If(n=0-> lambda(m-1,1),lambda(m-1,lambda(m,n-1)))) } Checkit ## M4 define(ack',ifelse($1,0,incr($2)',ifelse($2,0,ack(decr($1),1)',ack(decr($1),ack($1,decr($2)))')')')dnl
ack(3,3)
Output:
61

While MAD supports function calls, it does not handle recursion automatically. There is support for a stack, but the programmer has to set it up himself (by defining an array to reserve memory, then making it the stack using the SET LIST) command. Values have to be pushed and popped from it by hand (using SAVE and RESTORE), and for a function to be reentrant, even the return address has to be kept.

On top of this, all variables are global throughout the program (there is no scope), and argument passing is done by reference, meaning that even once the stack is set up, arguments cannot be passed in the normal way. To define a function that takes arguments, one would have to declare a helper function that then passes the arguments to the recursive function via the stack or the global variables. The following program demonstrates this.

NORMAL MODE IS INTEGER
DIMENSION LIST(3000)
SET LIST TO LIST

INTERNAL FUNCTION(DUMMY)
ENTRY TO ACKH.
LOOP        WHENEVER M.E.0
FUNCTION RETURN N+1
OR WHENEVER N.E.0
M=M-1
N=1
TRANSFER TO LOOP
OTHERWISE
SAVE RETURN
SAVE DATA M
N=N-1
N=ACKH.(0)
RESTORE DATA M
RESTORE RETURN
M=M-1
TRANSFER TO LOOP
END OF CONDITIONAL
ERROR RETURN
END OF FUNCTION

INTERNAL FUNCTION(MM,NN)
ENTRY TO ACK.
M=MM
N=NN
FUNCTION RETURN ACKH.(0)
END OF FUNCTION

THROUGH SHOW, FOR I=0, 1, I.G.3
THROUGH SHOW, FOR J=0, 1, J.G.8
SHOW        PRINT FORMAT ACKF,I,J,ACK.(I,J)

VECTOR VALUES ACKF = $4HACK(,I1,1H,,I1,4H) = ,I4*$
END OF PROGRAM
Output:
ACK(0,0) =    1
ACK(0,1) =    2
ACK(0,2) =    3
ACK(0,3) =    4
ACK(0,4) =    5
ACK(0,5) =    6
ACK(0,6) =    7
ACK(0,7) =    8
ACK(0,8) =    9
ACK(1,0) =    2
ACK(1,1) =    3
ACK(1,2) =    4
ACK(1,3) =    5
ACK(1,4) =    6
ACK(1,5) =    7
ACK(1,6) =    8
ACK(1,7) =    9
ACK(1,8) =   10
ACK(2,0) =    3
ACK(2,1) =    5
ACK(2,2) =    7
ACK(2,3) =    9
ACK(2,4) =   11
ACK(2,5) =   13
ACK(2,6) =   15
ACK(2,7) =   17
ACK(2,8) =   19
ACK(3,0) =    5
ACK(3,1) =   13
ACK(3,2) =   29
ACK(3,3) =   61
ACK(3,4) =  125
ACK(3,5) =  253
ACK(3,6) =  509
ACK(3,7) = 1021
ACK(3,8) = 2045

## Maple

Strictly by the definition given above, we can code this as follows.

Ackermann := proc( m :: nonnegint, n :: nonnegint )
option remember; # optional automatic memoization
if m = 0 then
n + 1
elif n = 0 then
thisproc( m - 1, 1 )
else
thisproc( m - 1, thisproc( m, n - 1 ) )
end if
end proc:
In Maple, the keyword
thisproc
refers to the currently executing procedure (closure) and is used when writing recursive procedures. (You could also use the name of the procedure, Ackermann in this case, but then a concurrently executing task or thread could re-assign that name while the recursive procedure is executing, resulting in an incorrect result.)

To make this faster, you can use known expansions for small values of ${\displaystyle m}$. (See Wikipedia:Ackermann function)

Ackermann := proc( m :: nonnegint, n :: nonnegint )
option remember; # optional automatic memoization
if m = 0 then
n + 1
elif m = 1 then
n + 2
elif m = 2 then
2 * n + 3
elif m = 3 then
8 * 2^n - 3
elif n = 0 then
thisproc( m - 1, 1 )
else
thisproc( m - 1, thisproc( m, n - 1 ) )
end if
end proc:

This makes it possible to compute Ackermann( 4, 1 ) and Ackermann( 4, 2 ) essentially instantly, though Ackermann( 4, 3 ) is still out of reach.

To compute Ackermann( 1, i ) for i from 1 to 10 use

> map2( Ackermann, 1, [seq]( 1 .. 10 ) );
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

To get the first 10 values for m = 2 use

> map2( Ackermann, 2, [seq]( 1 .. 10 ) );
[5, 7, 9, 11, 13, 15, 17, 19, 21, 23]

For Ackermann( 4, 2 ) we get a very long number with

> length( Ackermann( 4, 2 ) );
19729

digits.

Mathcad is a non-text-based programming environment. The equation below is an approximation of the way that it is entered (and) displayed on a Mathcad worksheet. The worksheet is available at https://community.ptc.com/t5/PTC-Mathcad/Rosetta-Code-Ackermann-Function/m-p/750117#M197410

This particular version of Ackermann's function was created in Mathcad Prime Express 7.0, a free version of Mathcad Prime 7.0 with restrictions (such as no programming or symbolics). All Prime Express numbers are complex. There is a recursion depth limit of about 4,500.

A(m,n):=if(m=0,n+1,if(n=0,A(m-1,1),A(m-1,A(m,n-1))))

The worksheet also contains an explictly-calculated version of Ackermann's function that calls the tetration function na.

na(a,n):=if(n=0,1,ana(a,n-1))

aerror(m,n):=error(format("cannot compute a({0},{1})",m,n))

a(m,n):=if(m=0,n+1,if(m=1,n+2,if(m=2,2n+3,if(m=3,2^(n+3)-3,aerror(m,n)))))

a(m,n):=if(m=4,na(2,n+3)-3,a(m,n)

## Mathematica / Wolfram Language

Two possible implementations would be:

$RecursionLimit=Infinity Ackermann1[m_,n_]:= If[m==0,n+1, If[ n==0,Ackermann1[m-1,1], Ackermann1[m-1,Ackermann1[m,n-1]] ] ] Ackermann2[0,n_]:=n+1; Ackermann2[m_,0]:=Ackermann1[m-1,1]; Ackermann2[m_,n_]:=Ackermann1[m-1,Ackermann1[m,n-1]] Note that the second implementation is quite a bit faster, as doing 'if' comparisons is slower than the built-in pattern matching algorithms. Examples: Flatten[#,1]&@Table[{"Ackermann2["<>ToString[i]<>","<>ToString[j]<>"] =",Ackermann2[i,j]},{i,3},{j,8}]//Grid gives back: Ackermann2[1,1] = 3 Ackermann2[1,2] = 4 Ackermann2[1,3] = 5 Ackermann2[1,4] = 6 Ackermann2[1,5] = 7 Ackermann2[1,6] = 8 Ackermann2[1,7] = 9 Ackermann2[1,8] = 10 Ackermann2[2,1] = 5 Ackermann2[2,2] = 7 Ackermann2[2,3] = 9 Ackermann2[2,4] = 11 Ackermann2[2,5] = 13 Ackermann2[2,6] = 15 Ackermann2[2,7] = 17 Ackermann2[2,8] = 19 Ackermann2[3,1] = 13 Ackermann2[3,2] = 29 Ackermann2[3,3] = 61 Ackermann2[3,4] = 125 Ackermann2[3,5] = 253 Ackermann2[3,6] = 509 Ackermann2[3,7] = 1021 Ackermann2[3,8] = 2045 If we would like to calculate Ackermann[4,1] or Ackermann[4,2] we have to optimize a little bit: Clear[Ackermann3]$RecursionLimit=Infinity;
Ackermann3[0,n_]:=n+1;
Ackermann3[1,n_]:=n+2;
Ackermann3[2,n_]:=3+2n;
Ackermann3[3,n_]:=5+8 (2^n-1);
Ackermann3[m_,0]:=Ackermann3[m-1,1];
Ackermann3[m_,n_]:=Ackermann3[m-1,Ackermann3[m,n-1]]

Now computing Ackermann[4,1] and Ackermann[4,2] can be done quickly (<0.01 sec): Examples 2:

Ackermann3[4, 1]
Ackermann3[4, 2]

gives back:

65533
2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880........699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156733

Ackermann[4,2] has 19729 digits, several thousands of digits omitted in the result above for obvious reasons. Ackermann[5,0] can be computed also quite fast, and is equal to 65533. Summarizing Ackermann[0,n_], Ackermann[1,n_], Ackermann[2,n_], and Ackermann[3,n_] can all be calculated for n>>1000. Ackermann[4,0], Ackermann[4,1], Ackermann[4,2] and Ackermann[5,0] are only possible now. Maybe in the future we can calculate higher Ackermann numbers efficiently and fast. Although showing the results will always be a problem.

## MATLAB

function A = ackermannFunction(m,n)
if m == 0
A = n+1;
elseif (m > 0) && (n == 0)
A = ackermannFunction(m-1,1);
else
A = ackermannFunction( m-1,ackermannFunction(m,n-1) );
end
end

## Maxima

ackermann(m, n) := if integerp(m) and integerp(n) then ackermann[m, n] else 'ackermann(m, n)$ackermann[m, n] := if m = 0 then n + 1 elseif m = 1 then 2 + (n + 3) - 3 elseif m = 2 then 2 * (n + 3) - 3 elseif m = 3 then 2^(n + 3) - 3 elseif n = 0 then ackermann[m - 1, 1] else ackermann[m - 1, ackermann[m, n - 1]]$

tetration(a, n) := if integerp(n) then block([b: a], for i from 2 thru n do b: a^b, b) else 'tetration(a, n)$/* this should evaluate to zero */ ackermann(4, n) - (tetration(2, n + 3) - 3); subst(n = 2, %); ev(%, nouns); ## MAXScript Use with caution. Will cause a stack overflow for m > 3. fn ackermann m n = ( if m == 0 then ( return n + 1 ) else if n == 0 then ( ackermann (m-1) 1 ) else ( ackermann (m-1) (ackermann m (n-1)) ) ) ## Mercury This is the Ackermann function with some (obvious) elements elided. The ack/3 predicate is implemented in terms of the ack/2 function. The ack/2 function is implemented in terms of the ack/3 predicate. This makes the code both more concise and easier to follow than would otherwise be the case. The integer type is used instead of int because the problem statement stipulates the use of bignum integers if possible. :- func ack(integer, integer) = integer. ack(M, N) = R :- ack(M, N, R). :- pred ack(integer::in, integer::in, integer::out) is det. ack(M, N, R) :- ( ( M < integer(0) ; N < integer(0) ) -> throw(bounds_error) ; M = integer(0) -> R = N + integer(1) ; N = integer(0) -> ack(M - integer(1), integer(1), R) ; ack(M - integer(1), ack(M, N - integer(1)), R) ). ## min Works with: min version 0.19.3 ( :n :m ( ((m 0 ==) (n 1 +)) ((n 0 ==) (m 1 - 1 ackermann)) ((true) (m 1 - m n 1 - ackermann ackermann)) ) case ) :ackermann ## MiniScript ackermann = function(m, n) if m == 0 then return n+1 if n == 0 then return ackermann(m - 1, 1) return ackermann(m - 1, ackermann(m, n - 1)) end function for m in range(0, 3) for n in range(0, 4) print "(" + m + ", " + n + "): " + ackermann(m, n) end for end for ## МК-61/52 П1 <-> П0 ПП 06 С/П ИП0 x=0 13 ИП1 1 + В/О ИП1 x=0 24 ИП0 1 П1 - П0 ПП 06 В/О ИП0 П2 ИП1 1 - П1 ПП 06 П1 ИП2 1 - П0 ПП 06 В/О ## ML/I ML/I loves recursion, but runs out of its default amount of storage with larger numbers than those tested here! ### Program MCSKIP "WITH" NL "" Ackermann function "" Will overflow when it reaches implementation-defined signed integer limit MCSKIP MT,<> MCINS %. MCDEF ACK WITHS ( , ) AS <MCSET T1=%A1. MCSET T2=%A2. MCGO L1 UNLESS T1 EN 0 %%T2.+1.MCGO L0 %L1.MCGO L2 UNLESS T2 EN 0 ACK(%%T1.-1.,1)MCGO L0 %L2.ACK(%%T1.-1.,ACK(%T1.,%%T2.-1.))> "" Macro ACK now defined, so try it out a(0,0) => ACK(0,0) a(0,1) => ACK(0,1) a(0,2) => ACK(0,2) a(0,3) => ACK(0,3) a(0,4) => ACK(0,4) a(0,5) => ACK(0,5) a(1,0) => ACK(1,0) a(1,1) => ACK(1,1) a(1,2) => ACK(1,2) a(1,3) => ACK(1,3) a(1,4) => ACK(1,4) a(2,0) => ACK(2,0) a(2,1) => ACK(2,1) a(2,2) => ACK(2,2) a(2,3) => ACK(2,3) a(3,0) => ACK(3,0) a(3,1) => ACK(3,1) a(3,2) => ACK(3,2) a(4,0) => ACK(4,0) Output: a(0,0) => 1 a(0,1) => 2 a(0,2) => 3 a(0,3) => 4 a(0,4) => 5 a(0,5) => 6 a(1,0) => 2 a(1,1) => 3 a(1,2) => 4 a(1,3) => 5 a(1,4) => 6 a(2,0) => 3 a(2,1) => 5 a(2,2) => 7 a(2,3) => 9 a(3,0) => 5 a(3,1) => 13 a(3,2) => 29 a(4,0) => 13 ## mLite fun ackermann( 0, n ) = n + 1 | ( m, 0 ) = ackermann( m - 1, 1 ) | ( m, n ) = ackermann( m - 1, ackermann(m, n - 1) ) Test code providing tuples from (0,0) to (3,8) fun jota x = map (fn x = x-1)  iota x fun test_tuples (x, y) = append_map (fn a = map (fn b = (b, a))  jota x)  jota y map ackermann (test_tuples(4,9)) Result [1, 2, 3, 5, 2, 3, 5, 13, 3, 4, 7, 29, 4, 5, 9, 61, 5, 6, 11, 125, 6, 7, 13, 253, 7, 8, 15, 509, 8, 9, 17, 1021, 9, 10, 19, 2045] ## Modula-2 MODULE ackerman; IMPORT ASCII, NumConv, InOut; VAR m, n : LONGCARD; string : ARRAY [0..19] OF CHAR; OK : BOOLEAN; PROCEDURE Ackerman (x, y : LONGCARD) : LONGCARD; BEGIN IF x = 0 THEN RETURN y + 1 ELSIF y = 0 THEN RETURN Ackerman (x - 1 , 1) ELSE RETURN Ackerman (x - 1 , Ackerman (x , y - 1)) END END Ackerman; BEGIN FOR m := 0 TO 3 DO FOR n := 0 TO 6 DO NumConv.Num2Str (Ackerman (m, n), 10, string, OK); IF OK THEN InOut.WriteString (string) ELSE InOut.WriteString ("* Error in number * ") END; InOut.Write (ASCII.HT) END; InOut.WriteLn END; InOut.WriteLn END ackerman. Output: jan@Beryllium:~/modula/rosetta$ ackerman

1 2 3 4 5 6 7 2 3 4 5 6 7 8 3 5 7 9 11 13 15

5 13 29 61 125 253 509

## Modula-3

The type CARDINAL is defined in Modula-3 as [0..LAST(INTEGER)], in other words, it can hold all positive integers.

MODULE Ack EXPORTS Main;

FROM IO IMPORT Put;
FROM Fmt IMPORT Int;

PROCEDURE Ackermann(m, n: CARDINAL): CARDINAL =
BEGIN
IF m = 0 THEN
RETURN n + 1;
ELSIF n = 0 THEN
RETURN Ackermann(m - 1, 1);
ELSE
RETURN Ackermann(m - 1, Ackermann(m, n - 1));
END;
END Ackermann;

BEGIN
FOR m := 0 TO 3 DO
FOR n := 0 TO 6 DO
Put(Int(Ackermann(m, n)) & " ");
END;
Put("\n");
END;
END Ack.
Output:
1 2 3 4 5 6 7
2 3 4 5 6 7 8
3 5 7 9 11 13 15
5 13 29 61 125 253 509

## MUMPS

Ackermann(m,n)	;
If m=0 Quit n+1
If m>0,n=0 Quit $$Ackermann(m-1,1) If m>0,n>0 Quit$$Ackermann(m-1,$$Ackermann(m,n-1)) Set Ecode=",U13-Invalid parameter for Ackermann: m="_m_", n="_n_"," Write$$Ackermann(1,8) ; 10
Write $$Ackermann(2,8) ; 19 Write$$Ackermann(3,5) ; 253

## Neko

/**
Ackermann recursion, in Neko
Tectonics:
nekoc ackermann.neko
neko ackermann 4 0
*/
ack = function(x,y) {
if (x == 0) return y+1;
if (y == 0) return ack(x-1,1);
return ack(x-1, ack(x,y-1));
};

var arg1 = $int($loader.args[0]);
var arg2 = $int($loader.args[1]);

/* If not given, or negative, default to Ackermann(3,4) */
if (arg1 == null || arg1 < 0) arg1 = 3;
if (arg2 == null || arg2 < 0) arg2 = 4;

try
$print("Ackermann(", arg1, ",", arg2, "): ", ack(arg1,arg2), "\n") catch problem$print("Ackermann(", arg1, ",", arg2, "): ", problem, "\n")
Output:
prompt$nekoc ackermann.neko prompt$ neko ackermann.n 3 4
Ackermann(3,4): 125

prompt$time neko ackermann.n 4 1 Ackermann(4,1): Stack Overflow real 0m31.475s user 0m31.460s sys 0m0.012s prompt$ time neko ackermann 3 10
Ackermann(3,10): 8189

real    0m1.865s
user    0m1.862s
sys     0m0.004s

## Nemerle

In Nemerle, we can state the Ackermann function as a lambda. By using pattern-matching, our definition strongly resembles the mathematical notation.

using System;
using Nemerle.IO;

def ackermann(m, n) {
def A = ackermann;
match(m, n) {
| (0, n) => n + 1
| (m, 0) when m > 0 => A(m - 1, 1)
| (m, n) when m > 0 && n > 0 => A(m - 1, A(m, n - 1))
| _ => throw Exception("invalid inputs");
}
}

for(mutable m = 0; m < 4; m++) {
for(mutable n = 0; n < 5; n++) {

## Nit

Source: the official Nit’s repository.

#
# A simple straightforward recursive implementation.
module ackermann_function

fun ack(m, n: Int): Int
do
if m == 0 then return n + 1
if n == 0 then return ack(m-1,1)
return ack(m-1, ack(m, n-1))
end

for m in [0..3] do
for n in [0..6] do
print ack(m,n)
end
print ""
end

Output:

1
2
3
4
5
6
7

2
3
4
5
6
7
8

3
5
7
9
11
13
15

5
13
29
61
125
253
509

## Oberon-2

MODULE ackerman;

IMPORT  Out;

VAR     m, n    : INTEGER;

PROCEDURE Ackerman (x, y   : INTEGER) : INTEGER;

BEGIN
IF    x = 0  THEN  RETURN  y + 1
ELSIF y = 0  THEN  RETURN  Ackerman (x - 1 , 1)
ELSE
RETURN  Ackerman (x - 1 , Ackerman (x , y - 1))
END
END Ackerman;

BEGIN
FOR  m := 0  TO  3  DO
FOR  n := 0  TO  6  DO
Out.Int (Ackerman (m, n), 10);
Out.Char (9X)
END;
Out.Ln
END;
Out.Ln
END ackerman.

## Objeck

Translation of: C# – C sharp
class Ackermann {
function : Main(args : String[]) ~ Nil {
for(m := 0; m <= 3; ++m;) {
for(n := 0; n <= 4; ++n;) {
a := Ackermann(m, n);
if(a > 0) {
"Ackermann({$m}, {$n}) = {$a}"->PrintLine(); }; }; }; } function : Ackermann(m : Int, n : Int) ~ Int { if(m > 0) { if (n > 0) { return Ackermann(m - 1, Ackermann(m, n - 1)); } else if (n = 0) { return Ackermann(m - 1, 1); }; } else if(m = 0) { if(n >= 0) { return n + 1; }; }; return -1; } } Ackermann(0, 0) = 1 Ackermann(0, 1) = 2 Ackermann(0, 2) = 3 Ackermann(0, 3) = 4 Ackermann(0, 4) = 5 Ackermann(1, 0) = 2 Ackermann(1, 1) = 3 Ackermann(1, 2) = 4 Ackermann(1, 3) = 5 Ackermann(1, 4) = 6 Ackermann(2, 0) = 3 Ackermann(2, 1) = 5 Ackermann(2, 2) = 7 Ackermann(2, 3) = 9 Ackermann(2, 4) = 11 Ackermann(3, 0) = 5 Ackermann(3, 1) = 13 Ackermann(3, 2) = 29 Ackermann(3, 3) = 61 Ackermann(3, 4) = 125 ## OCaml let rec a m n = if m=0 then (n+1) else if n=0 then (a (m-1) 1) else (a (m-1) (a m (n-1))) or: let rec a = function | 0, n -> (n+1) | m, 0 -> a(m-1, 1) | m, n -> a(m-1, a(m, n-1)) with memoization using an hash-table: let h = Hashtbl.create 4001 let a m n = try Hashtbl.find h (m, n) with Not_found -> let res = a (m, n) in Hashtbl.add h (m, n) res; (res) taking advantage of the memoization we start calling small values of m and n in order to reduce the recursion call stack: let a m n = for _m = 0 to m do for _n = 0 to n do ignore(a _m _n); done; done; (a m n) ### Arbitrary precision With arbitrary-precision integers (Big_int module): open Big_int let one = unit_big_int let zero = zero_big_int let succ = succ_big_int let pred = pred_big_int let eq = eq_big_int let rec a m n = if eq m zero then (succ n) else if eq n zero then (a (pred m) one) else (a (pred m) (a m (pred n))) compile with: ocamlopt -o acker nums.cmxa acker.ml ### Tail-Recursive Here is a tail-recursive version: let rec find_option h v = try Some(Hashtbl.find h v) with Not_found -> None let rec a bounds caller todo m n = match m, n with | 0, n -> let r = (n+1) in ( match todo with | [] -> r | (m,n)::todo -> List.iter (fun k -> if not(Hashtbl.mem bounds k) then Hashtbl.add bounds k r) caller; a bounds [] todo m n ) | m, 0 -> a bounds caller todo (m-1) 1 | m, n -> match find_option bounds (m, n-1) with | Some a_rec -> let caller = (m,n)::caller in a bounds caller todo (m-1) a_rec | None -> let todo = (m,n)::todo and caller = [(m, n-1)] in a bounds caller todo m (n-1) let a = a (Hashtbl.create 42 (* arbitrary *) ) [] [] ;; This one uses the arbitrary precision, the tail-recursion, and the optimisation explain on the Wikipedia page about (m,n) = (3,_). open Big_int let one = unit_big_int let zero = zero_big_int let succ = succ_big_int let pred = pred_big_int let add = add_big_int let sub = sub_big_int let eq = eq_big_int let three = succ(succ one) let power = power_int_positive_big_int let eq2 (a1,a2) (b1,b2) = (eq a1 b1) && (eq a2 b2) module H = Hashtbl.Make (struct type t = Big_int.big_int * Big_int.big_int let equal = eq2 let hash (x,y) = Hashtbl.hash (Big_int.string_of_big_int x ^ "," ^ Big_int.string_of_big_int y) (* probably not a very good hash function *) end) let rec find_option h v = try Some (H.find h v) with Not_found -> None let rec a bounds caller todo m n = let may_tail r = let k = (m,n) in match todo with | [] -> r | (m,n)::todo -> List.iter (fun k -> if not (H.mem bounds k) then H.add bounds k r) (k::caller); a bounds [] todo m n in match m, n with | m, n when eq m zero -> let r = (succ n) in may_tail r | m, n when eq n zero -> let caller = (m,n)::caller in a bounds caller todo (pred m) one | m, n when eq m three -> let r = sub (power 2 (add n three)) three in may_tail r | m, n -> match find_option bounds (m, pred n) with | Some a_rec -> let caller = (m,n)::caller in a bounds caller todo (pred m) a_rec | None -> let todo = (m,n)::todo in let caller = [(m, pred n)] in a bounds caller todo m (pred n) let a = a (H.create 42 (* arbitrary *)) [] [] ;; let () = let m, n = try big_int_of_string Sys.argv.(1), big_int_of_string Sys.argv.(2) with _ -> Printf.eprintf "usage: %s <int> <int>\n" Sys.argv.(0); exit 1 in let r = a m n in Printf.printf "(a %s %s) = %s\n" (string_of_big_int m) (string_of_big_int n) (string_of_big_int r); ;; ## Octave function r = ackerman(m, n) if ( m == 0 ) r = n + 1; elseif ( n == 0 ) r = ackerman(m-1, 1); else r = ackerman(m-1, ackerman(m, n-1)); endif endfunction for i = 0:3 disp(ackerman(i, 4)); endfor ## Oforth : A( m n -- p ) m ifZero: [ n 1+ return ] m 1- n ifZero: [ 1 ] else: [ A( m, n 1- ) ] A ; ## Ol ; simple version (define (A m n) (cond ((= m 0) (+ n 1)) ((= n 0) (A (- m 1) 1)) (else (A (- m 1) (A m (- n 1)))))) (print "simple version (A 3 6): " (A 3 6)) ; smart (lazy) version (define (ints-from n) (cons* n (delay (ints-from (+ n 1))))) (define (knuth-up-arrow a n b) (let loop ((n n) (b b)) (cond ((= b 0) 1) ((= n 1) (expt a b)) (else (loop (- n 1) (loop n (- b 1))))))) (define (A+ m n) (define (A-stream) (cons* (ints-from 1) ;; m = 0 (ints-from 2) ;; m = 1 ;; m = 2 (lmap (lambda (n) (+ (* 2 (+ n 1)) 1)) (ints-from 0)) ;; m = 3 (lmap (lambda (n) (- (knuth-up-arrow 2 (- m 2) (+ n 3)) 3)) (ints-from 0)) ;; m = 4... (delay (ldrop (A-stream) 3)))) (llref (llref (A-stream) m) n)) (print "extended version (A 3 6): " (A+ 3 6)) Output: simple version (A 3 6): 509 extended version (A 3 6): 509 ## OOC ack: func (m: Int, n: Int) -> Int { if (m == 0) { n + 1 } else if (n == 0) { ack(m - 1, 1) } else { ack(m - 1, ack(m, n - 1)) } } main: func { for (m in 0..4) { for (n in 0..10) { "ack(#{m}, #{n}) = #{ack(m, n)}" println() } } } ## ooRexx loop m = 0 to 3 loop n = 0 to 6 say "Ackermann("m", "n") =" ackermann(m, n) end end ::routine ackermann use strict arg m, n -- give us some precision room numeric digits 10000 if m = 0 then return n + 1 else if n = 0 then return ackermann(m - 1, 1) else return ackermann(m - 1, ackermann(m, n - 1)) Output: Ackermann(0, 0) = 1 Ackermann(0, 1) = 2 Ackermann(0, 2) = 3 Ackermann(0, 3) = 4 Ackermann(0, 4) = 5 Ackermann(0, 5) = 6 Ackermann(0, 6) = 7 Ackermann(1, 0) = 2 Ackermann(1, 1) = 3 Ackermann(1, 2) = 4 Ackermann(1, 3) = 5 Ackermann(1, 4) = 6 Ackermann(1, 5) = 7 Ackermann(1, 6) = 8 Ackermann(2, 0) = 3 Ackermann(2, 1) = 5 Ackermann(2, 2) = 7 Ackermann(2, 3) = 9 Ackermann(2, 4) = 11 Ackermann(2, 5) = 13 Ackermann(2, 6) = 15 Ackermann(3, 0) = 5 Ackermann(3, 1) = 13 Ackermann(3, 2) = 29 Ackermann(3, 3) = 61 Ackermann(3, 4) = 125 Ackermann(3, 5) = 253 Ackermann(3, 6) = 509 ## Order #include <order/interpreter.h> #define ORDER_PP_DEF_8ack ORDER_PP_FN( \ 8fn(8X, 8Y, \ 8cond((8is_0(8X), 8inc(8Y)) \ (8is_0(8Y), 8ack(8dec(8X), 1)) \ (8else, 8ack(8dec(8X), 8ack(8X, 8dec(8Y))))))) ORDER_PP(8to_lit(8ack(3, 4))) // 125 ## Oz Oz has arbitrary precision integers. declare fun {Ack M N} if M == 0 then N+1 elseif N == 0 then {Ack M-1 1} else {Ack M-1 {Ack M N-1}} end end in {Show {Ack 3 7}} ## PARI/GP Naive implementation. A(m,n)={ if(m, if(n, A(m-1, A(m,n-1)) , A(m-1,1) ) , n+1 ) }; ## Pascal Program Ackerman; function ackermann(m, n: Integer) : Integer; begin if m = 0 then ackermann := n+1 else if n = 0 then ackermann := ackermann(m-1, 1) else ackermann := ackermann(m-1, ackermann(m, n-1)); end; var m, n : Integer; begin for n := 0 to 6 do for m := 0 to 3 do WriteLn('A(', m, ',', n, ') = ', ackermann(m,n)); end. ## Perl We memoize calls to A to make A(2, n) and A(3, n) feasible for larger values of n. { my @memo; sub A { my($m, $n ) = @_;$memo[ $m ][$n ] and return $memo[$m ][ $n ];$m or return $n + 1; return$memo[ $m ][$n ] = (
$n ? A($m - 1, A( $m,$n - 1 ) )
: A( $m - 1, 1 ) ); } } An implementation using the conditional statements 'if', 'elsif' and 'else': sub A { my ($m, $n) = @_; if ($m == 0) { $n + 1 } elsif ($n == 0) { A($m - 1, 1) } else { A($m - 1, A($m,$n - 1)) }
}

An implementation using ternary chaining:

sub A {
my ($m,$n) = @_;
$m == 0 ?$n + 1 :
$n == 0 ? A($m - 1, 1) :
A($m - 1, A($m, $n - 1)) } Adding memoization and extra terms: use Memoize; memoize('ack2'); use bigint try=>"GMP"; sub ack2 { my ($m, $n) = @_;$m == 0 ? $n + 1 :$m == 1 ? $n + 2 :$m == 2 ? 2*$n + 3 :$m == 3 ? 8 * (2**$n - 1) + 5 :$n == 0 ? ack2($m-1, 1) : ack2($m-1, ack2($m,$n-1));
}
print "ack2(3,4) is ", ack2(3,4), "\n";
print "ack2(4,1) is ", ack2(4,1), "\n";
print "ack2(4,2) has ", length(ack2(4,2)), " digits\n";
Output:
ack2(3,4) is 125
ack2(4,1) is 65533
ack2(4,2) has 19729 digits

An optimized version, which uses @_ as a stack, instead of recursion. Very fast.

use strict;
use warnings;
use Math::BigInt;

use constant two => Math::BigInt->new(2);

sub ack {
my $n = pop; while( @_ ) { my$m = pop;
if( $m > 3 ) { push @_, (--$m) x $n; push @_, reverse 3 .. --$m;
$n = 13; } elsif($m == 3 ) {
if( $n < 29 ) {$n = ( 1 << ( $n + 3 ) ) - 3; } else {$n = two ** ( $n + 3 ) - 3; } } elsif($m == 2 ) {
$n = 2 *$n + 3;
} elsif( $m >= 0 ) {$n = $n +$m + 1;
} else {
die "negative m!";
}
}
$n; } print "ack(3,4) is ", ack(3,4), "\n"; print "ack(4,1) is ", ack(4,1), "\n"; print "ack(4,2) has ", length(ack(4,2)), " digits\n"; ## Phix ### native version function ack(integer m, integer n) if m=0 then return n+1 elsif m=1 then return n+2 elsif m=2 then return 2*n+3 elsif m=3 then return power(2,n+3)-3 elsif m>0 and n=0 then return ack(m-1,1) else return ack(m-1,ack(m,n-1)) end if end function constant limit = 23, fmtlens = {1,2,2,2,3,3,3,4,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8} atom t0 = time() printf(1," 0") for j=1 to limit do string fmt = sprintf(" %%%dd",fmtlens[j+1]) printf(1,fmt,j) end for printf(1,"\n") for i=0 to 5 do printf(1,"%d:",i) for j=0 to iff(i>=4?5-i:limit) do string fmt = sprintf(" %%%dd",fmtlens[j+1]) printf(1,fmt,{ack(i,j)}) end for printf(1,"\n") end for Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 0: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2: 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 3: 5 13 29 61 125 253 509 1021 2045 4093 8189 16381 32765 65533 131069 262141 524285 1048573 2097149 4194301 8388605 16777213 33554429 67108861 4: 13 65533 5: 65533 ack(4,2) and above fail with power function overflow. ack(3,100) will get you an answer, but only accurate to 16 or so digits. ### gmp version Translation of: Go Library: Phix/mpfr -- demo\rosetta\Ackermann.exw include mpfr.e procedure ack(integer m, mpz n) if m=0 then mpz_add_ui(n, n, 1) -- return n+1 elsif m=1 then mpz_add_ui(n, n, 2) -- return n+2 elsif m=2 then mpz_mul_si(n, n, 2) mpz_add_ui(n, n, 3) -- return 2*n+3 elsif m=3 then if not mpz_fits_integer(n) then -- As per Go: 2^MAXINT would most certainly run out of memory. -- (think about it: a million digits is fine but pretty daft; -- however a billion digits requires > addressable memory.) integer bn = mpz_sizeinbase(n, 2) throw(sprintf("A(m,n) had n of %d bits; too large",bn)) end if integer ni = mpz_get_integer(n) mpz_set_si(n, 8) mpz_mul_2exp(n, n, ni) -- (n:=8*2^ni) mpz_sub_ui(n, n, 3) -- return power(2,n+3)-3 elsif mpz_cmp_si(n,0)=0 then mpz_set_si(n, 1) ack(m-1,n) -- return ack(m-1,1) else mpz_sub_ui(n, n, 1) ack(m,n) ack(m-1,n) -- return ack(m-1,ack(m,n-1)) end if end procedure constant limit = 23, fmtlens = {1,2,2,2,3,3,3,4,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8}, extras = {{3,100},{3,1e6},{4,2},{4,3}} procedure ackermann_tests() atom t0 = time() atom n = mpz_init() printf(1," 0") for j=1 to limit do string fmt = sprintf(" %%%dd",fmtlens[j+1]) printf(1,fmt,j) end for printf(1,"\n") for i=0 to 5 do printf(1,"%d:",i) for j=0 to iff(i>=4?5-i:limit) do mpz_set_si(n, j) ack(i,n) string fmt = sprintf(" %%%ds",fmtlens[j+1]) printf(1,fmt,{mpz_get_str(n)}) end for printf(1,"\n") end for printf(1,"\n") for i=1 to length(extras) do integer {em, en} = extras[i] mpz_set_si(n, en) string res try ack(em,n) res = mpz_get_str(n) integer lr = length(res) if lr>50 then res[21..-21] = "..." res &= sprintf(" (%d digits)",lr) end if catch e -- ack(4,3), ack(5,1) and ack(6,0) all fail, -- just as they should do res = "***ERROR***: "&e[E_USER] end try printf(1,"ack(%d,%d) %s\n",{em,en,res}) end for n = mpz_free(n) printf(1,"\n") printf(1,"ackermann_tests completed (%s)\n\n",{elapsed(time()-t0)}) end procedure ackermann_tests() Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 0: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2: 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 3: 5 13 29 61 125 253 509 1021 2045 4093 8189 16381 32765 65533 131069 262141 524285 1048573 2097149 4194301 8388605 16777213 33554429 67108861 4: 13 65533 5: 65533 ack(3,100) 10141204801825835211973625643005 ack(3,1000000) 79205249834367186005...39107225301976875005 (301031 digits) ack(4,2) 20035299304068464649...45587895905719156733 (19729 digits) ack(4,3) ***ERROR***: A(m,n) had n of 65536 bits; too large ackermann_tests completed (0.2s) ## Phixmonti def ack var n var m m 0 == if n 1 + else n 0 == if m 1 - 1 ack else m 1 - m n 1 - ack ack endif endif enddef 3 6 ack print nl ## PHP function ackermann($m , $n ) { if ($m==0 )
{
return $n + 1; } elseif ($n==0 )
{
return ackermann( $m-1 , 1 ); } return ackermann($m-1, ackermann( $m ,$n-1 ) );
}

echo ackermann( 3, 4 );
// prints 125

## Picat

go =>
foreach(M in 0..3)
println([m=M,[a(M,N) : N in 0..16]])
end,
nl,
printf("a2(4,1): %d\n", a2(4,1)),
nl,
time(check_larger(3,10000)),
nl,
time(check_larger(4,2)),
nl.

% Using a2/2 and chop off large output
check_larger(M,N) =>
printf("a2(%d,%d): ", M,N),
A = a2(M,N).to_string,
Len = A.len,
if Len < 50 then
println(A)
else
println(A[1..20] ++ ".." ++ A[Len-20..Len])
end,
println(digits=Len).

% Plain tabled (memoized) version with guards
table
a(0, N) = N+1 => true.
a(M, 0) = a(M-1,1), M > 0 => true.
a(M, N) = a(M-1,a(M, N-1)), M > 0, N > 0 => true.

% Faster and pure function version (no guards).
% (Based on Python example.)
table
a2(0,N) = N + 1.
a2(1,N) = N + 2.
a2(2,N) = 2*N + 3.
a2(3,N) = 8*(2**N - 1) + 5.
a2(M,N) = cond(N == 0,a2(M-1, 1), a2(M-1, a2(M, N-1))).
Output:
[m = 0,[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]]
[m = 1,[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]]
[m = 2,[3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35]]
[m = 3,[5,13,29,61,125,253,509,1021,2045,4093,8189,16381,32765,65533,131069,262141,524285]]

a2(4,1): 65533

a2(3,10000): 15960504935046067079..454194438340773675005
digits = 3012
CPU time 0.02 seconds.

a2(4,2): 20035299304068464649..445587895905719156733
digits = 19729
CPU time 0.822 seconds.

## PicoLisp

(de ack (X Y)
(cond
((=0 X) (inc Y))
((=0 Y) (ack (dec X) 1))
(T (ack (dec X) (ack X (dec Y)))) ) )

## Piet

Rendered as wikitable:

 ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww ww

This is a naive implementation that does not use any optimization. Find the explanation at [[1]]. Computing the Ackermann function for (4,1) is possible, but takes quite a while because the stack grows very fast to large dimensions.

Example output:

? 3
? 5
253

## Pike

int main(){
write(ackermann(3,4) + "\n");
}

int ackermann(int m, int n){
if(m == 0){
return n + 1;
} else if(n == 0){
return ackermann(m-1, 1);
} else {
return ackermann(m-1, ackermann(m, n-1));
}
}

## PL/I

Ackerman: procedure (m, n) returns (fixed (30)) recursive;
declare (m, n) fixed (30);
if m = 0 then return (n+1);
else if m > 0 & n = 0 then return (Ackerman(m-1, 1));
else if m > 0 & n > 0 then return (Ackerman(m-1, Ackerman(m, n-1)));
return (0);
end Ackerman;

## PL/SQL

DECLARE

FUNCTION ackermann(pi_m IN NUMBER,
pi_n IN NUMBER) RETURN NUMBER IS
BEGIN
IF pi_m = 0 THEN
RETURN pi_n + 1;
ELSIF pi_n = 0 THEN
RETURN ackermann(pi_m - 1, 1);
ELSE
RETURN ackermann(pi_m - 1, ackermann(pi_m, pi_n - 1));
END IF;
END ackermann;

BEGIN
FOR n IN 0 .. 6 LOOP
FOR m IN 0 .. 3 LOOP
dbms_output.put_line('A(' || m || ',' || n || ') = ' || ackermann(m, n));
END LOOP;
END LOOP;
END;
Output:
A(0,0) = 1
A(1,0) = 2
A(2,0) = 3
A(3,0) = 5
A(0,1) = 2
A(1,1) = 3
A(2,1) = 5
A(3,1) = 13
A(0,2) = 3
A(1,2) = 4
A(2,2) = 7
A(3,2) = 29
A(0,3) = 4
A(1,3) = 5
A(2,3) = 9
A(3,3) = 61
A(0,4) = 5
A(1,4) = 6
A(2,4) = 11
A(3,4) = 125
A(0,5) = 6
A(1,5) = 7
A(2,5) = 13
A(3,5) = 253
A(0,6) = 7
A(1,6) = 8
A(2,6) = 15
A(3,6) = 509

## PostScript

/ackermann{
/n exch def
/m exch def %PostScript takes arguments in the reverse order as specified in the function definition
m 0 eq{
}if
m 0 gt n 0 eq and
{
m 1 sub 1 ackermann
}if
m 0 gt n 0 gt and{
m 1 sub m n 1 sub ackermann ackermann
}if
}def
Library: initlib
/A {
[/.m /.n] let
{
{.m 0 eq} {.n succ} is?
{.m 0 gt .n 0 eq and} {.m pred 1 A} is?
{.m 0 gt .n 0 gt and} {.m pred .m .n pred A A} is?
} cond
end}.

## Potion

ack = (m, n):
if (m == 0): n + 1
. elsif (n == 0): ack(m - 1, 1)
. else: ack(m - 1, ack(m, n - 1)).
.

4 times(m):
7 times(n):
ack(m, n) print
" " print.
"\n" print.

## PowerBASIC

FUNCTION PBMAIN () AS LONG

m = ABS(VAL(INPUTBOX$("Enter a whole number."))) n = ABS(VAL(INPUTBOX$("Enter another whole number.")))

MSGBOX STR$(Ackermann(m, n)) END FUNCTION FUNCTION Ackermann (m AS QUAD, n AS QUAD) AS QUAD IF 0 = m THEN FUNCTION = n + 1 ELSEIF 0 = n THEN FUNCTION = Ackermann(m - 1, 1) ELSE ' m > 0; n > 0 FUNCTION = Ackermann(m - 1, Ackermann(m, n - 1)) END IF END FUNCTION ## PowerShell Translation of: PHP function ackermann ([long]$m, [long] $n) { if ($m -eq 0) {
return $n + 1 } if ($n -eq 0) {
return (ackermann ($m - 1) 1) } return (ackermann ($m - 1) (ackermann $m ($n - 1)))
}

Building an example table (takes a while to compute, though, especially for the last three numbers; also it fails with the last line in Powershell v1 since the maximum recursion depth is only 100 there):

foreach ($m in 0..3) { foreach ($n in 0..6) {
Write-Host -NoNewline ("{0,5}" -f (ackermann $m$n))
}
Write-Host
}
Output:
1    2    3    4    5    6    7
2    3    4    5    6    7    8
3    5    7    9   11   13   15
5   13   29   61  125  253  509

### A More "PowerShelly" Way

function Get-Ackermann ([int64]$m, [int64]$n)
{
if ($m -eq 0) { return$n + 1
}

if ($n -eq 0) { return Get-Ackermann ($m - 1) 1
}

return (Get-Ackermann ($m - 1) (Get-Ackermann$m ($n - 1))) } Save the result to an array (for possible future use?), then display it using the Format-Wide cmdlet:$ackermann = 0..3 | ForEach-Object {$m =$_; 0..6 | ForEach-Object {Get-Ackermann $m$_}}

$ackermann | Format-Wide {"{0,3}" -f$_} -Column 7 -Force
Output:
1                   2                  3                  4                  5                  6                  7
2                   3                  4                  5                  6                  7                  8
3                   5                  7                  9                 11                 13                 15
5                  13                 29                 61                125                253                509

## Processing

int ackermann(int m, int n) {
if (m == 0)
return n + 1;
else if (m > 0 && n == 0)
return ackermann(m - 1, 1);
else
return ackermann( m - 1, ackermann(m, n - 1) );
}

// Call function to produce output:
// the first 4x7 Ackermann numbers
void setup() {
for (int m=0; m<4; m++) {
for (int n=0; n<7; n++) {
print(ackermann(m, n), " ");
}
println();
}
}
Output:
1  2  3  4  5  6  7
2  3  4  5  6  7  8
3  5  7  9  11  13  15
5  13  29  61  125  253  509

### Processing Python mode

Python is not very adequate for deep recursion, so even setting sys.setrecursionlimit(1000000000) if m = 5 it throws 'maximum recursion depth exceeded'

from __future__ import print_function

def setup():
for m in range(4):
for n in range(7):
print("{} ".format(ackermann(m, n)), end = "")
print()
# print('finished')

def ackermann(m, n):
if m == 0:
return n + 1
elif m > 0 and n == 0:
return ackermann(m - 1, 1)
else:
return ackermann(m - 1, ackermann(m, n - 1))

### Processing.R

Processing.R may exceed its stack depth at ~n==6 and returns null.

setup <- function() {
for (m in 0:3) {
for (n in 0:4) {
stdout$print(paste(ackermann(m, n), " ")) } stdout$println("")
}
}

ackermann <- function(m, n) {
if ( m == 0 ) {
return(n+1)
} else if ( n == 0 ) {
ackermann(m-1, 1)
} else {
ackermann(m-1, ackermann(m, n-1))
}
}
Output:
1  2  3  4  5
2  3  4  5  6
3  5  7  9  11
5  13  29  61  125

## Prolog

Works with: SWI Prolog
:- table ack/3. % memoization reduces the execution time of ack(4,1,X) from several
% minutes to about one second on a typical desktop computer.
ack(0, N, Ans) :- Ans is N+1.
ack(M, 0, Ans) :- M>0, X is M-1, ack(X, 1, Ans).
ack(M, N, Ans) :- M>0, N>0, X is M-1, Y is N-1, ack(M, Y, Ans2), ack(X, Ans2, Ans).

"Pure" Prolog Version (Uses Peano arithmetic instead of is/2):

ack(0,N,s(N)).
ack(s(M),0,P):- ack(M,s(0),P).
ack(s(M),s(N),P):- ack(s(M),N,S), ack(M,S,P).

% Peano's first axiom in Prolog is that s(0) AND s(s(N)):- s(N)
% Thanks to this we don't need explicit N > 0 checks.
% Nor explicit arithmetic operations like X is M-1.
% Recursion and unification naturally decrement s(N) to N.
% But: Prolog clauses are relations and cannot be replaced by their result, like functions.
% Because of this we do need an extra argument to hold the output of the function.
% And we also need an additional call to the function in the last clause.

% Example input/output:
% ?- ack(s(0),s(s(0)),P).
% P = s(s(s(s(0)))) ;
% false.

## Pure

A 0 n = n+1;
A m 0 = A (m-1) 1 if m > 0;
A m n = A (m-1) (A m (n-1)) if m > 0 && n > 0;

## Pure Data

#N canvas 741 265 450 436 10;
#X obj 83 111 t b l;
#X obj 115 163 route 0;
#X obj 115 185 + 1;
#X obj 83 380 f;
#X obj 161 186 swap;
#X obj 161 228 route 0;
#X obj 161 250 - 1;
#X obj 161 208 pack;
#X obj 115 314 t f f;
#X msg 161 272 \$1 1; #X obj 115 142 t l; #X obj 207 250 swap; #X obj 273 271 - 1; #X obj 207 272 t f f; #X obj 207 298 - 1; #X obj 207 360 pack; #X obj 239 299 pack; #X obj 83 77 inlet; #X obj 83 402 outlet; #X connect 0 0 3 0; #X connect 0 1 10 0; #X connect 1 0 2 0; #X connect 1 1 4 0; #X connect 2 0 8 0; #X connect 3 0 18 0; #X connect 4 0 7 0; #X connect 4 1 7 1; #X connect 5 0 6 0; #X connect 5 1 11 0; #X connect 6 0 9 0; #X connect 7 0 5 0; #X connect 8 0 3 1; #X connect 8 1 15 1; #X connect 9 0 10 0; #X connect 10 0 1 0; #X connect 11 0 13 0; #X connect 11 1 12 0; #X connect 12 0 16 1; #X connect 13 0 14 0; #X connect 13 1 16 0; #X connect 14 0 15 0; #X connect 15 0 10 0; #X connect 16 0 10 0; #X connect 17 0 0 0; ## PureBasic Procedure.q Ackermann(m, n) If m = 0 ProcedureReturn n + 1 ElseIf n = 0 ProcedureReturn Ackermann(m - 1, 1) Else ProcedureReturn Ackermann(m - 1, Ackermann(m, n - 1)) EndIf EndProcedure Debug Ackermann(3,4) ## Purity data Iter = f => FoldNat <const$f One, $f> data Ackermann = FoldNat <const Succ, Iter> ## Python ### Python: Explicitly recursive Works with: Python version 2.5 def ack1(M, N): return (N + 1) if M == 0 else ( ack1(M-1, 1) if N == 0 else ack1(M-1, ack1(M, N-1))) Another version: from functools import lru_cache @lru_cache(None) def ack2(M, N): if M == 0: return N + 1 elif N == 0: return ack2(M - 1, 1) else: return ack2(M - 1, ack2(M, N - 1)) Example of use: >>> import sys >>> sys.setrecursionlimit(3000) >>> ack1(0,0) 1 >>> ack1(3,4) 125 >>> ack2(0,0) 1 >>> ack2(3,4) 125 From the Mathematica ack3 example: def ack2(M, N): return (N + 1) if M == 0 else ( (N + 2) if M == 1 else ( (2*N + 3) if M == 2 else ( (8*(2**N - 1) + 5) if M == 3 else ( ack2(M-1, 1) if N == 0 else ack2(M-1, ack2(M, N-1)))))) Results confirm those of Mathematica for ack(4,1) and ack(4,2) ### Python: Without recursive function calls The heading is more correct than saying the following is iterative as an explicit stack is used to replace explicit recursive function calls. I don't think this is what Comp. Sci. professors mean by iterative. from collections import deque def ack_ix(m, n): "Paddy3118's iterative with optimisations on m" stack = deque([]) stack.extend([m, n]) while len(stack) > 1: n, m = stack.pop(), stack.pop() if m == 0: stack.append(n + 1) elif m == 1: stack.append(n + 2) elif m == 2: stack.append(2*n + 3) elif m == 3: stack.append(2**(n + 3) - 3) elif n == 0: stack.extend([m-1, 1]) else: stack.extend([m-1, m, n-1]) return stack[0] Output: (From an ipython shell) In [26]: %time a_4_2 = ack_ix(4, 2) Wall time: 0 ns In [27]: # How big is the answer? In [28]: float(a_4_2) Traceback (most recent call last): File "<ipython-input-28-af4ad951eff8>", line 1, in <module> float(a_4_2) OverflowError: int too large to convert to float In [29]: # How many decimal digits in the answer? In [30]: len(str(a_4_2)) Out[30]: 19729 ## Quackery forward is ackermann ( m n --> r ) [ over 0 = iff [ nip 1 + ] done dup 0 = iff [ drop 1 - 1 ackermann ] done over 1 - unrot 1 - ackermann ackermann ] resolves ackermann ( m n --> r ) 3 10 ackermann echo Output: 8189 ## R ackermann <- function(m, n) { if ( m == 0 ) { n+1 } else if ( n == 0 ) { ackermann(m-1, 1) } else { ackermann(m-1, ackermann(m, n-1)) } } for ( i in 0:3 ) { print(ackermann(i, 4)) } ## Racket #lang racket (define (ackermann m n) (cond [(zero? m) (add1 n)] [(zero? n) (ackermann (sub1 m) 1)] [else (ackermann (sub1 m) (ackermann m (sub1 n)))])) ## Raku (formerly Perl 6) Works with: Rakudo version 2018.03 sub A(Int$m, Int $n) { if$m == 0 { $n + 1 } elsif$n == 0 { A($m - 1, 1) } else { A($m - 1, A($m,$n - 1)) }
}

An implementation using multiple dispatch:

multi sub A(0,      Int $n) {$n + 1                   }
multi sub A(Int $m, 0 ) { A($m - 1, 1)             }
multi sub A(Int $m, Int$n) { A($m - 1, A($m, $n - 1)) } Note that in either case, Int is defined to be arbitrary precision in Raku. Here's a caching version of that, written in the sigilless style, with liberal use of Unicode, and the extra optimizing terms to make A(4,2) possible: proto A(Int \𝑚, Int \𝑛) { (state @)[𝑚][𝑛] //= {*} } multi A(0, Int \𝑛) { 𝑛 + 1 } multi A(1, Int \𝑛) { 𝑛 + 2 } multi A(2, Int \𝑛) { 3 + 2 * 𝑛 } multi A(3, Int \𝑛) { 5 + 8 * (2 ** 𝑛 - 1) } multi A(Int \𝑚, 0 ) { A(𝑚 - 1, 1) } multi A(Int \𝑚, Int \𝑛) { A(𝑚 - 1, A(𝑚, 𝑛 - 1)) } # Testing: say A(4,1); say .chars, " digits starting with ", .substr(0,50), "..." given A(4,2); Output: 65533 19729 digits starting with 20035299304068464649790723515602557504478254755697... ## REBOL ackermann: func [m n] [ case [ m = 0 [n + 1] n = 0 [ackermann m - 1 1] true [ackermann m - 1 ackermann m n - 1] ] ] ## ReScript let _m = Sys.argv[2] let _n = Sys.argv[3] let m = int_of_string(_m) let n = int_of_string(_n) let rec a = (m, n) => switch (m, n) { | (0, n) => (n+1) | (m, 0) => a(m-1, 1) | (m, n) => a(m-1, a(m, n-1)) } Js.log("ackermann(" ++ _m ++ ", " ++ _n ++ ") = " ++ string_of_int(a(m, n))) Output:$ bsc acker.res > acker.bs.js
$node acker.bs.js 2 3 ackermann(2, 3) = 9$ node acker.bs.js 3 4
ackermann(3, 4) = 125

## REXX

### no optimization

/*REXX program  calculates and displays  some values for the  Ackermann function.       */
/*╔════════════════════════════════════════════════════════════════════════╗
║  Note:  the Ackermann function  (as implemented here)  utilizes deep   ║
║         recursive and is limited by the largest number that can have   ║
║         "1"  (unity) added to a number  (successfully and accurately). ║
╚════════════════════════════════════════════════════════════════════════╝*/
high=24
do     j=0  to 3;                    say
do k=0  to high % (max(1, j))
call tell_Ack  j, k
end   /*k*/
end       /*j*/
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
tell_Ack:  parse arg mm,nn;   calls=0            /*display an echo message to terminal. */
#=right(nn,length(high))
say 'Ackermann('mm", "#')='right(ackermann(mm, nn), high),
left('', 12)     'calls='right(calls, high)
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
ackermann: procedure expose calls                /*compute value of Ackermann function. */
parse arg m,n;   calls=calls+1
if m==0  then return n+1
if n==0  then return ackermann(m-1, 1)
return ackermann(m-1, ackermann(m, n-1) )
output   when using the internal default input:
Ackermann(0, 0)=                       1              calls=                       1
Ackermann(0, 1)=                       2              calls=                       1
Ackermann(0, 2)=                       3              calls=                       1
Ackermann(0, 3)=                       4              calls=                       1
Ackermann(0, 4)=                       5              calls=                       1
Ackermann(0, 5)=                       6              calls=                       1
Ackermann(0, 6)=                       7              calls=                       1
Ackermann(0, 7)=                       8              calls=                       1
Ackermann(0, 8)=                       9              calls=                       1
Ackermann(0, 9)=                      10              calls=                       1
Ackermann(0,10)=                      11              calls=                       1
Ackermann(0,11)=                      12              calls=                       1
Ackermann(0,12)=                      13              calls=                       1
Ackermann(0,13)=                      14              calls=                       1
Ackermann(0,14)=                      15              calls=                       1
Ackermann(0,15)=                      16              calls=                       1
Ackermann(0,16)=                      17              calls=                       1
Ackermann(0,17)=                      18              calls=                       1
Ackermann(0,18)=                      19              calls=                       1
Ackermann(0,19)=                      20              calls=                       1
Ackermann(0,20)=                      21              calls=                       1
Ackermann(0,21)=                      22              calls=                       1
Ackermann(0,22)=                      23              calls=                       1
Ackermann(0,23)=                      24              calls=                       1
Ackermann(0,24)=                      25              calls=                       1

Ackermann(1, 0)=                       2              calls=                       2
Ackermann(1, 1)=                       3              calls=                       4
Ackermann(1, 2)=                       4              calls=                       6
Ackermann(1, 3)=                       5              calls=                       8
Ackermann(1, 4)=                       6              calls=                      10
Ackermann(1, 5)=                       7              calls=                      12
Ackermann(1, 6)=                       8              calls=                      14
Ackermann(1, 7)=                       9              calls=                      16
Ackermann(1, 8)=                      10              calls=                      18
Ackermann(1, 9)=                      11              calls=                      20
Ackermann(1,10)=                      12              calls=                      22
Ackermann(1,11)=                      13              calls=                      24
Ackermann(1,12)=                      14              calls=                      26
Ackermann(1,13)=                      15              calls=                      28
Ackermann(1,14)=                      16              calls=                      30
Ackermann(1,15)=                      17              calls=                      32
Ackermann(1,16)=                      18              calls=                      34
Ackermann(1,17)=                      19              calls=                      36
Ackermann(1,18)=                      20              calls=                      38
Ackermann(1,19)=                      21              calls=                      40
Ackermann(1,20)=                      22              calls=                      42
Ackermann(1,21)=                      23              calls=                      44
Ackermann(1,22)=                      24              calls=                      46
Ackermann(1,23)=                      25              calls=                      48
Ackermann(1,24)=                      26              calls=                      50

Ackermann(2, 0)=                       3              calls=                       5
Ackermann(2, 1)=                       5              calls=                      14
Ackermann(2, 2)=                       7              calls=                      27
Ackermann(2, 3)=                       9              calls=                      44
Ackermann(2, 4)=                      11              calls=                      65
Ackermann(2, 5)=                      13              calls=                      90
Ackermann(2, 6)=                      15              calls=                     119
Ackermann(2, 7)=                      17              calls=                     152
Ackermann(2, 8)=                      19              calls=                     189
Ackermann(2, 9)=                      21              calls=                     230
Ackermann(2,10)=                      23              calls=                     275
Ackermann(2,11)=                      25              calls=                     324
Ackermann(2,12)=                      27              calls=                     377

Ackermann(3, 0)=                       5              calls=                      15
Ackermann(3, 1)=                      13              calls=                     106
Ackermann(3, 2)=                      29              calls=                     541
Ackermann(3, 3)=                      61              calls=                    2432
Ackermann(3, 4)=                     125              calls=                   10307
Ackermann(3, 5)=                     253              calls=                   42438
Ackermann(3, 6)=                     509              calls=                  172233
Ackermann(3, 7)=                    1021              calls=                  693964
Ackermann(3, 8)=                    2045              calls=                 2785999

### optimized for m ≤ 2

/*REXX program  calculates and displays  some values for the  Ackermann function.       */
high=24
do     j=0  to 3;                    say
do k=0  to high % (max(1, j))
call tell_Ack  j, k
end   /*k*/
end       /*j*/
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
tell_Ack:  parse arg mm,nn;   calls=0            /*display an echo message to terminal. */
#=right(nn,length(high))
say 'Ackermann('mm", "#')='right(ackermann(mm, nn), high),
left('', 12)     'calls='right(calls, high)
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
ackermann: procedure expose calls                /*compute value of Ackermann function. */
parse arg m,n;   calls=calls+1
if m==0  then return n + 1
if n==0  then return ackermann(m-1, 1)
if m==2  then return n + 3 + n
return ackermann(m-1, ackermann(m, n-1) )
output   when using the internal default input:
Ackermann(0, 0)=                       1              calls=         1
Ackermann(0, 1)=                       2              calls=         1
Ackermann(0, 2)=                       3              calls=         1
Ackermann(0, 3)=                       4              calls=         1
Ackermann(0, 4)=                       5              calls=         1
Ackermann(0, 5)=                       6              calls=         1
Ackermann(0, 6)=                       7              calls=         1
Ackermann(0, 7)=                       8              calls=         1
Ackermann(0, 8)=                       9              calls=         1
Ackermann(0, 9)=                      10              calls=         1
Ackermann(0,10)=                      11              calls=         1
Ackermann(0,11)=                      12              calls=         1
Ackermann(0,12)=                      13              calls=         1
Ackermann(0,13)=                      14              calls=         1
Ackermann(0,14)=                      15              calls=         1
Ackermann(0,15)=                      16              calls=         1
Ackermann(0,16)=                      17              calls=         1
Ackermann(0,17)=                      18              calls=         1
Ackermann(0,18)=                      19              calls=         1
Ackermann(0,19)=                      20              calls=         1
Ackermann(0,20)=                      21              calls=         1
Ackermann(0,21)=                      22              calls=         1
Ackermann(0,22)=                      23              calls=         1
Ackermann(0,23)=                      24              calls=         1
Ackermann(0,24)=                      25              calls=         1

Ackermann(1, 0)=                       2              calls=         2
Ackermann(1, 1)=                       3              calls=         4
Ackermann(1, 2)=                       4              calls=         6
Ackermann(1, 3)=                       5              calls=         8
Ackermann(1, 4)=                       6              calls=        10
Ackermann(1, 5)=                       7              calls=        12
Ackermann(1, 6)=                       8              calls=        14
Ackermann(1, 7)=                       9              calls=        16
Ackermann(1, 8)=                      10              calls=        18
Ackermann(1, 9)=                      11              calls=        20
Ackermann(1,10)=                      12              calls=        22
Ackermann(1,11)=                      13              calls=        24
Ackermann(1,12)=                      14              calls=        26
Ackermann(1,13)=                      15              calls=        28
Ackermann(1,14)=                      16              calls=        30
Ackermann(1,15)=                      17              calls=        32
Ackermann(1,16)=                      18              calls=        34
Ackermann(1,17)=                      19              calls=        36
Ackermann(1,18)=                      20              calls=        38
Ackermann(1,19)=                      21              calls=        40
Ackermann(1,20)=                      22              calls=        42
Ackermann(1,21)=                      23              calls=        44
Ackermann(1,22)=                      24              calls=        46
Ackermann(1,23)=                      25              calls=        48
Ackermann(1,24)=                      26              calls=        50

Ackermann(2, 0)=                       3              calls=         5
Ackermann(2, 1)=                       5              calls=         1
Ackermann(2, 2)=                       7              calls=         1
Ackermann(2, 3)=                       9              calls=         1
Ackermann(2, 4)=                      11              calls=         1
Ackermann(2, 5)=                      13              calls=         1
Ackermann(2, 6)=                      15              calls=         1
Ackermann(2, 7)=                      17              calls=         1
Ackermann(2, 8)=                      19              calls=         1
Ackermann(2, 9)=                      21              calls=         1
Ackermann(2,10)=                      23              calls=         1
Ackermann(2,11)=                      25              calls=         1
Ackermann(2,12)=                      27              calls=         1

Ackermann(3, 0)=                       5              calls=         2
Ackermann(3, 1)=                      13              calls=         4
Ackermann(3, 2)=                      29              calls=         6
Ackermann(3, 3)=                      61              calls=         8
Ackermann(3, 4)=                     125              calls=        10
Ackermann(3, 5)=                     253              calls=        12
Ackermann(3, 6)=                     509              calls=        14
Ackermann(3, 7)=                    1021              calls=        16
Ackermann(3, 8)=                    2045              calls=        18

### optimized for m ≤ 4

This REXX version takes advantage that some of the lower numbers for the Ackermann function have direct formulas.

If the   numeric digits 100   were to be increased to   20000,   then the value of   Ackermann(4,2)
(the last line of output)   would be presented with the full   19,729   decimal digits.

/*REXX program  calculates and displays  some values for the  Ackermann function.       */
numeric digits 100                               /*use up to 100 decimal digit integers.*/
/*╔═════════════════════════════════════════════════════════════╗
║ When REXX raises a number to an integer power  (via the  ** ║
║ operator,  the power can be positive, zero, or negative).   ║
║ Ackermann(5,1)   is a bit impractical to calculate.         ║
╚═════════════════════════════════════════════════════════════╝*/
high=24
do     j=0  to 4;                   say
do k=0  to high % (max(1, j))
call tell_Ack  j, k
if j==4 & k==2  then leave          /*there's no sense in going overboard. */
end   /*k*/
end       /*j*/
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
tell_Ack:  parse arg mm,nn;   calls=0            /*display an echo message to terminal. */
#=right(nn,length(high))
say 'Ackermann('mm", "#')='right(ackermann(mm, nn), high),
left('', 12)     'calls='right(calls, high)
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
ackermann: procedure expose calls                /*compute value of Ackermann function. */
parse arg m,n;   calls=calls+1
if m==0  then return n + 1
if m==1  then return n + 2
if m==2  then return n + 3 + n
if m==3  then return 2**(n+3) - 3
if m==4  then do; #=2                 /* [↓]  Ugh!  ···  and still more ughs.*/
do (n+3)-1 /*This is where the heavy lifting is.  */
#=2**#
end
return #-3
end
if n==0  then return ackermann(m-1, 1)
return ackermann(m-1, ackermann(m, n-1) )

Output note:   none of the numbers shown below use recursion to compute.

output   when using the internal default input:
Ackermann(0, 0)=                       1              calls=         1
Ackermann(0, 1)=                       2              calls=         1
Ackermann(0, 2)=                       3              calls=         1
Ackermann(0, 3)=                       4              calls=         1
Ackermann(0, 4)=                       5              calls=         1
Ackermann(0, 5)=                       6              calls=         1
Ackermann(0, 6)=                       7              calls=         1
Ackermann(0, 7)=                       8              calls=         1
Ackermann(0, 8)=                       9              calls=         1
Ackermann(0, 9)=                      10              calls=         1
Ackermann(0,10)=                      11              calls=         1
Ackermann(0,11)=                      12              calls=         1
Ackermann(0,12)=                      13              calls=         1
Ackermann(0,13)=                      14              calls=         1
Ackermann(0,14)=                      15              calls=         1
Ackermann(0,15)=                      16              calls=         1
Ackermann(0,16)=                      17              calls=         1
Ackermann(0,17)=                      18              calls=         1
Ackermann(0,18)=                      19              calls=         1
Ackermann(0,19)=                      20              calls=         1
Ackermann(0,20)=                      21              calls=         1
Ackermann(0,21)=                      22              calls=         1
Ackermann(0,22)=                      23              calls=         1
Ackermann(0,23)=                      24              calls=         1
Ackermann(0,24)=                      25              calls=         1

Ackermann(1, 0)=                       2              calls=         1
Ackermann(1, 1)=                       3              calls=         1
Ackermann(1, 2)=                       4              calls=         1
Ackermann(1, 3)=                       5              calls=         1
Ackermann(1, 4)=                       6              calls=         1
Ackermann(1, 5)=                       7              calls=         1
Ackermann(1, 6)=                       8              calls=         1
Ackermann(1, 7)=                       9              calls=         1
Ackermann(1, 8)=                      10              calls=         1
Ackermann(1, 9)=                      11              calls=         1
Ackermann(1,10)=                      12              calls=         1
Ackermann(1,11)=                      13              calls=         1
Ackermann(1,12)=                      14              calls=         1
Ackermann(1,13)=                      15              calls=         1
Ackermann(1,14)=                      16              calls=         1
Ackermann(1,15)=                      17              calls=         1
Ackermann(1,16)=                      18              calls=         1
Ackermann(1,17)=                      19              calls=         1
Ackermann(1,18)=                      20              calls=         1
Ackermann(1,19)=                      21              calls=         1
Ackermann(1,20)=                      22              calls=         1
Ackermann(1,21)=                      23              calls=         1
Ackermann(1,22)=                      24              calls=         1
Ackermann(1,23)=                      25              calls=         1
Ackermann(1,24)=                      26              calls=         1

Ackermann(2, 0)=                       3              calls=         1
Ackermann(2, 1)=                       5              calls=         1
Ackermann(2, 2)=                       7              calls=         1
Ackermann(2, 3)=                       9              calls=         1
Ackermann(2, 4)=                      11              calls=         1
Ackermann(2, 5)=                      13              calls=         1
Ackermann(2, 6)=                      15              calls=         1
Ackermann(2, 7)=                      17              calls=         1
Ackermann(2, 8)=                      19              calls=         1
Ackermann(2, 9)=                      21              calls=         1
Ackermann(2,10)=                      23              calls=         1
Ackermann(2,11)=                      25              calls=         1
Ackermann(2,12)=                      27              calls=         1

Ackermann(3, 0)=                       5              calls=         1
Ackermann(3, 1)=                      13              calls=         1
Ackermann(3, 2)=                      29              calls=         1
Ackermann(3, 3)=                      61              calls=         1
Ackermann(3, 4)=                     125              calls=         1
Ackermann(3, 5)=                     253              calls=         1
Ackermann(3, 6)=                     509              calls=         1
Ackermann(3, 7)=                    1021              calls=         1
Ackermann(3, 8)=                    2045              calls=         1

Ackermann(4, 0)=                      13              calls=         1
Ackermann(4, 1)=                   65533              calls=         1
Ackermann(4, 2)=89506130880933368E+19728              calls=         1

## Ring

Translation of: C#
for m = 0 to 3
for n = 0 to 4
see "Ackermann(" + m + ", " + n + ") = " + Ackermann(m, n) + nl
next
next

func Ackermann m, n
if m > 0
if n > 0
return Ackermann(m - 1, Ackermann(m, n - 1))
but n = 0
return Ackermann(m - 1, 1)
ok
but m = 0
if n >= 0
return n + 1
ok
ok
Raise("Incorrect Numerical input !!!")
Output:
Ackermann(0, 0) = 1
Ackermann(0, 1) = 2
Ackermann(0, 2) = 3
Ackermann(0, 3) = 4
Ackermann(0, 4) = 5
Ackermann(1, 0) = 2
Ackermann(1, 1) = 3
Ackermann(1, 2) = 4
Ackermann(1, 3) = 5
Ackermann(1, 4) = 6
Ackermann(2, 0) = 3
Ackermann(2, 1) = 5
Ackermann(2, 2) = 7
Ackermann(2, 3) = 9
Ackermann(2, 4) = 11
Ackermann(3, 0) = 5
Ackermann(3, 1) = 13
Ackermann(3, 2) = 29
Ackermann(3, 3) = 61
Ackermann(3, 4) = 125

## Risc-V

the basic recursive function, because memorization and other improvements would blow the clarity.

ackermann: 	#x: a1, y: a2, return: a0
beqz a1, npe #case m = 0
beqz a2, mme #case m > 0 & n = 0
addi sp, sp, -8 #case m > 0 & n > 0
sw ra, 4(sp)
sw a1, 0(sp)
jal ackermann
lw a1, 0(sp)
mv a2, a0
jal ackermann
lw t0, 4(sp)
jr t0, 0
npe:
jr ra, 0
mme:
sw ra, 0(sp)
li a2, 1
jal ackermann
lw t0, 0(sp)
jr t0, 0

## Ruby

def ack(m, n)
if m == 0
n + 1
elsif n == 0
ack(m-1, 1)
else
ack(m-1, ack(m, n-1))
end
end

Example:

(0..3).each do |m|
puts (0..6).map { |n| ack(m, n) }.join(' ')
end
Output:
1 2 3 4 5 6 7
2 3 4 5 6 7 8
3 5 7 9 11 13 15
5 13 29 61 125 253 509

## Run BASIC

print ackermann(1, 2)

function ackermann(m, n)
if (m = 0)             then ackermann = (n + 1)
if (m > 0) and (n = 0) then ackermann = ackermann((m - 1), 1)
if (m > 0) and (n > 0) then ackermann = ackermann((m - 1), ackermann(m, (n - 1)))
end function

## Rust

fn ack(m: isize, n: isize) -> isize {
if m == 0 {
n + 1
} else if n == 0 {
ack(m - 1, 1)
} else {
ack(m - 1, ack(m, n - 1))
}
}

fn main() {
let a = ack(3, 4);
println!("{}", a); // 125
}

Or:

fn ack(m: u64, n: u64) -> u64 {
match (m, n) {
(0, n) => n + 1,
(m, 0) => ack(m - 1, 1),
(m, n) => ack(m - 1, ack(m, n - 1)),
}
}

## Sather

class MAIN is

ackermann(m, n:INT):INT
pre m >= 0 and n >= 0
is
if m = 0 then return n + 1; end;
if n = 0 then return ackermann(m-1, 1); end;
return ackermann(m-1, ackermann(m, n-1));
end;

main is
n, m :INT;
loop n := 0.upto!(6);
loop m := 0.upto!(3);
#OUT + "A(" + m + ", " + n + ") = " + ackermann(m, n) + "\n";
end;
end;
end;
end;

Instead of INT, the class INTI could be used, even though we need to use a workaround since in the GNU Sather v1.2.3 compiler the INTI literals are not implemented yet.

class MAIN is

ackermann(m, n:INTI):INTI is
zero ::= 0.inti; -- to avoid type conversion each time
one  ::= 1.inti;
if m = zero then return n + one; end;
if n = zero then return ackermann(m-one, one); end;
return ackermann(m-one, ackermann(m, n-one));
end;

main is
n, m :INT;
loop n := 0.upto!(6);
loop m := 0.upto!(3);
#OUT + "A(" + m + ", " + n + ") = " + ackermann(m.inti, n.inti) + "\n";
end;
end;
end;
end;

## Scala

def ack(m: BigInt, n: BigInt): BigInt = {
if (m==0) n+1
else if (n==0) ack(m-1, 1)
else ack(m-1, ack(m, n-1))
}
Example:
scala> for ( m <- 0 to 3; n <- 0 to 6 ) yield ack(m,n)
res0: Seq.Projection[BigInt] = RangeG(1, 2, 3, 4, 5, 6, 7, 2, 3, 4, 5, 6, 7, 8, 3, 5, 7, 9, 11, 13, 15, 5, 13, 29, 61, 125, 253, 509)

Memoized version using a mutable hash map:

val ackMap = new mutable.HashMap[(BigInt,BigInt),BigInt]
def ackMemo(m: BigInt, n: BigInt): BigInt = {
ackMap.getOrElseUpdate((m,n), ack(m,n))
}

## Scheme

(define (A m n)
(cond
((= m 0) (+ n 1))
((= n 0) (A (- m 1) 1))
(else (A (- m 1) (A m (- n 1))))))

An improved solution that uses a lazy data structure, streams, and defines Knuth up-arrows to calculate iterative exponentiation:

(define (A m n)
(letrec ((A-stream
(cons-stream
(ints-from 1) ;; m = 0
(cons-stream
(ints-from 2) ;; m = 1
(cons-stream
;; m = 2
(stream-map (lambda (n)
(1+ (* 2 (1+ n))))
(ints-from 0))
(cons-stream
;; m = 3
(stream-map (lambda (n)
(- (knuth-up-arrow 2 (- m 2) (+ n 3)) 3))
(ints-from 0))
;; m = 4...
(stream-tail A-stream 3)))))))
(stream-ref (stream-ref A-stream m) n)))

(define (ints-from n)
(letrec ((ints-rec (cons-stream n (stream-map 1+ ints-rec))))
ints-rec))

(define (knuth-up-arrow a n b)
(let loop ((n n) (b b))
(cond ((= b 0) 1)
((= n 1) (expt a b))
(else    (loop (-1+ n) (loop n (-1+ b)))))))

## Scilab

clear
function acker=ackermann(m,n)
global calls
calls=calls+1
if m==0 then     acker=n+1
else
if n==0 then acker=ackermann(m-1,1)
else acker=ackermann(m-1,ackermann(m,n-1))
end
end
endfunction
function printacker(m,n)
global calls
calls=0
printf('ackermann(%d,%d)=',m,n)
printf('%d  calls=%d\n',ackermann(m,n),calls)
endfunction
maxi=3; maxj=6
for i=0:maxi
for j=0:maxj
printacker(i,j)
end
end
Output:
ackermann(0,0)=1  calls=1
ackermann(0,1)=2  calls=1
ackermann(0,2)=3  calls=1
ackermann(0,3)=4  calls=1
ackermann(0,4)=5  calls=1
ackermann(0,5)=6  calls=1
ackermann(0,6)=7  calls=1
ackermann(1,0)=2  calls=2
ackermann(1,1)=3  calls=4
ackermann(1,2)=4  calls=6
ackermann(1,3)=5  calls=8
ackermann(1,4)=6  calls=10
ackermann(1,5)=7  calls=12
ackermann(1,6)=8  calls=14
ackermann(2,0)=3  calls=5
ackermann(2,1)=5  calls=14
ackermann(2,2)=7  calls=27
ackermann(2,3)=9  calls=44
ackermann(2,4)=11  calls=65
ackermann(2,5)=13  calls=90
ackermann(2,6)=15  calls=119
ackermann(3,0)=5  calls=15
ackermann(3,1)=13  calls=106
ackermann(3,2)=29  calls=541
ackermann(3,3)=61  calls=2432
ackermann(3,4)=125  calls=10307
ackermann(3,5)=253  calls=42438
ackermann(3,6)=509  calls=172233

## Seed7

const func integer: ackermann (in integer: m, in integer: n) is func
result
var integer: result is 0;
begin
if m = 0 then
result := succ(n);
elsif n = 0 then
result := ackermann(pred(m), 1);
else
result := ackermann(pred(m), ackermann(m, pred(n)));
end if;
end func;

Original source: [2]

## SETL

program ackermann;

(for m in [0..3])
print(+/ [rpad('' + ack(m, n), 4): n in [0..6]]);
end;

proc ack(m, n);
return {[0,n+1]}(m) ? ack(m-1, {[0,1]}(n) ? ack(m, n-1));
end proc;

end program;

## Shen

(define ack
0 N -> (+ N 1)
M 0 -> (ack (- M 1) 1)
M N -> (ack (- M 1)
(ack M (- N 1))))

## Sidef

func A(m, n) {
m == 0 ? (n + 1)
: (n == 0 ? (A(m - 1, 1))
: (A(m - 1, A(m, n - 1))));
}

Alternatively, using multiple dispatch:

func A((0), n) { n + 1 }
func A(m, (0)) { A(m - 1, 1) }
func A(m,  n)  { A(m-1, A(m, n-1)) }

Calling the function:

say A(3, 2);     # prints: 29

## Simula

as modified by R. Péter and R. Robinson:

BEGIN
INTEGER procedure
Ackermann(g, p); SHORT INTEGER g, p;
Ackermann:= IF g = 0 THEN p+1
ELSE Ackermann(g-1, IF p = 0 THEN 1
ELSE Ackermann(g, p-1));

INTEGER g, p;
FOR p := 0 STEP 3 UNTIL 13 DO BEGIN
g := 4 - p/3;
outtext("Ackermann("); outint(g, 0);
outchar(','); outint(p, 2); outtext(") = ");
outint(Ackermann(g, p), 0); outimage
END
END
Output:
Ackermann(4, 0) = 13
Ackermann(3, 3) = 61
Ackermann(2, 6) = 15
Ackermann(1, 9) = 11
Ackermann(0,12) = 13

## Slate

m@(Integer traits) ackermann: n@(Integer traits)
[
m isZero
ifTrue: [n + 1]
ifFalse:
[n isZero
ifTrue: [m - 1 ackermann: n]
ifFalse: [m - 1 ackermann: (m ackermann: n - 1)]]
].

## Smalltalk

|ackermann|
ackermann := [ :n :m |
(n = 0) ifTrue: [ (m + 1) ]
ifFalse: [
(m = 0) ifTrue: [ ackermann value: (n-1) value: 1 ]
ifFalse: [
ackermann value: (n-1)
value: ( ackermann value: n
value: (m-1) )
]
]
].

(ackermann value: 0 value: 0) displayNl.
(ackermann value: 3 value: 4) displayNl.

## SmileBASIC

DEF ACK(M,N)
IF M==0 THEN
RETURN N+1
ELSEIF M>0 AND N==0 THEN
RETURN ACK(M-1,1)
ELSE
RETURN ACK(M-1,ACK(M,N-1))
ENDIF
END

## SNOBOL4

Works with: Macro Spitbol

Both Snobol4+ and CSnobol stack overflow, at ack(3,3) and ack(3,4), respectively.

define('ack(m,n)') :(ack_end)
ack     ack = eq(m,0) n + 1 :s(return)
ack = eq(n,0) ack(m - 1,1) :s(return)
ack = ack(m - 1,ack(m,n - 1)) :(return)
ack_end

*       # Test and display ack(0,0) .. ack(3,6)
L1      str = str ack(m,n) ' '
n = lt(n,6) n + 1 :s(L1)
output = str; str = ''
n = 0; m = lt(m,3) m + 1 :s(L1)
end
Output:
1 2 3 4 5 6 7
2 3 4 5 6 7 8
3 5 7 9 11 13 15
5 13 29 61 125 253 509

## SNUSP

/==!/==atoi=@@@-@-----#
|   |                          Ackermann function
|   |       /=========\!==\!====\  recursion:
$,@/>,@/==ack=!\?\<+# | | | A(0,j) -> j+1 j i \<?\+>-@/# | | A(i,0) -> A(i-1,1) \@\>@\->@/@\<-@/# A(i,j) -> A(i-1,A(i,j-1)) | | | # # | | | /+<<<-\ /-<<+>>\!=/ \=====|==!/========?\>>>=?/<<# ? ? | \<<<+>+>>-/ \>>+<<-/!==========/ # # One could employ tail recursion elimination by replacing "@/#" with "/" in two places above. ## SPAD NNI ==> NonNegativeInteger A:(NNI,NNI) -> NNI A(m,n) == m=0 => n+1 m>0 and n=0 => A(m-1,1) m>0 and n>0 => A(m-1,A(m,n-1)) -- Example matrix [[A(i,j) for i in 0..3] for j in 0..3] Output: +1 2 3 5 + | | |2 3 5 13| (1) | | |3 4 7 29| | | +4 5 9 61+ Type: Matrix(NonNegativeInteger) ## SQL PL Works with: Db2 LUW version 9.7 or higher. With SQL PL: --#SET TERMINATOR @ SET SERVEROUTPUT ON@ CREATE OR REPLACE FUNCTION ACKERMANN( IN M SMALLINT, IN N BIGINT ) RETURNS BIGINT BEGIN DECLARE RET BIGINT; DECLARE STMT STATEMENT; IF (M = 0) THEN SET RET = N + 1; ELSEIF (N = 0) THEN PREPARE STMT FROM 'SET ? = ACKERMANN(? - 1, 1)'; EXECUTE STMT INTO RET USING M; ELSE PREPARE STMT FROM 'SET ? = ACKERMANN(? - 1, ACKERMANN(?, ? - 1))'; EXECUTE STMT INTO RET USING M, M, N; END IF; RETURN RET; END @ BEGIN DECLARE M SMALLINT DEFAULT 0; DECLARE N SMALLINT DEFAULT 0; DECLARE MAX_LEVELS CONDITION FOR SQLSTATE '54038'; DECLARE CONTINUE HANDLER FOR MAX_LEVELS BEGIN END; WHILE (N <= 6) DO WHILE (M <= 3) DO CALL DBMS_OUTPUT.PUT_LINE('ACKERMANN(' || M || ', ' || N || ') = ' || ACKERMANN(M, N)); SET M = M + 1; END WHILE; SET M = 0; SET N = N + 1; END WHILE; END @ Output: db2 -td@ db2 => CREATE OR REPLACE FUNCTION ACKERMANN( ... db2 (cont.) => END @ DB20000I The SQL command completed successfully. db2 => BEGIN db2 (cont.) => END ... DB20000I The SQL command completed successfully. ACKERMANN(0, 0) = 1 ACKERMANN(1, 0) = 2 ACKERMANN(2, 0) = 3 ACKERMANN(3, 0) = 5 ACKERMANN(0, 1) = 2 ACKERMANN(1, 1) = 3 ACKERMANN(2, 1) = 5 ACKERMANN(3, 1) = 13 ACKERMANN(0, 2) = 3 ACKERMANN(1, 2) = 4 ACKERMANN(2, 2) = 7 ACKERMANN(3, 2) = 29 ACKERMANN(0, 3) = 4 ACKERMANN(1, 3) = 5 ACKERMANN(2, 3) = 9 ACKERMANN(3, 3) = 61 ACKERMANN(0, 4) = 5 ACKERMANN(1, 4) = 6 ACKERMANN(2, 4) = 11 ACKERMANN(0, 5) = 6 ACKERMANN(1, 5) = 7 ACKERMANN(2, 5) = 13 ACKERMANN(0, 6) = 7 ACKERMANN(1, 6) = 8 ACKERMANN(2, 6) = 15 The maximum levels of cascade calls in Db2 are 16, and in some cases when executing the Ackermann function, it arrives to this limit (SQL0724N). Thus, the code catches the exception and continues with the next try. ## Standard ML fun a (0, n) = n+1 | a (m, 0) = a (m-1, 1) | a (m, n) = a (m-1, a (m, n-1)) ## Stata mata function ackermann(m,n) { if (m==0) { return(n+1) } else if (n==0) { return(ackermann(m-1,1)) } else { return(ackermann(m-1,ackermann(m,n-1))) } } for (i=0; i<=3; i++) printf("%f\n",ackermann(i,4)) 5 6 11 125 end ## Swift func ackerman(m:Int, n:Int) -> Int { if m == 0 { return n+1 } else if n == 0 { return ackerman(m-1, 1) } else { return ackerman(m-1, ackerman(m, n-1)) } } ## Tcl ### Simple Translation of: Ruby proc ack {m n} { if {$m == 0} {
expr {$n + 1} } elseif {$n == 0} {
ack [expr {$m - 1}] 1 } else { ack [expr {$m - 1}] [ack $m [expr {$n - 1}]]
}
}

### With Tail Recursion

With Tcl 8.6, this version is preferred (though the language supports tailcall optimization, it does not apply it automatically in order to preserve stack frame semantics):

proc ack {m n} {
if {$m == 0} { expr {$n + 1}
} elseif {$n == 0} { tailcall ack [expr {$m - 1}] 1
} else {
tailcall ack [expr {$m - 1}] [ack$m [expr {$n - 1}]] } } ### To Infinity… and Beyond! If we want to explore the higher reaches of the world of Ackermann's function, we need techniques to really cut the amount of computation being done. Works with: Tcl version 8.6 package require Tcl 8.6 # A memoization engine, from http://wiki.tcl.tk/18152 oo::class create cache { filter Memoize variable ValueCache method Memoize args { # Do not filter the core method implementations if {[lindex [self target] 0] eq "::oo::object"} { return [next {*}$args]
}

# Check if the value is already in the cache
set key [self target],$args if {[info exist ValueCache($key)]} {
return $ValueCache($key)
}

# Compute value, insert into cache, and return it
return [set ValueCache($key) [next {*}$args]]
}
method flushCache {} {
unset ValueCache
# Skip the cacheing
return -level 2 ""
}
}

# Make an object, attach the cache engine to it, and define ack as a method
oo::object create cached
oo::objdefine cached {
mixin cache
method ack {m n} {
if {$m==0} { expr {$n+1}
} elseif {$m==1} { # From the Mathematica version expr {$m+2}
} elseif {$m==2} { # From the Mathematica version expr {2*$n+3}
} elseif {$m==3} { # From the Mathematica version expr {8*(2**$n-1)+5}
} elseif {$n==0} { tailcall my ack [expr {$m-1}] 1
} else {
tailcall my ack [expr {\$m-1}] [my