I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Ackermann function

(Redirected from Ackermann Function)
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 AREAW&SYSNDX DS    XL8                    CONVERSION WORK AREAI&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         MENDACKERMAN CSECT         USING  ACKERMAN,R12       r12 : base register         LR     R12,R15            establish base register         ST     R14,SAVER14A       save r14         LA     R4,0               m=0LOOPM    CH     R4,=H'3'           do m=0 to 3         BH     ELOOPM         LA     R5,0               n=0LOOPN    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      LOOPNELOOPN   LA     R4,1(R4)           m=m+1         B      LOOPMELOOPM   L      R14,SAVER14A       restore r14         BR     R14                return to callerSAVER14A DS     F                  static save r14PG       DC     CL44'Ackermann(xx,xx) = xxxxxxxxxxxx'XD       DS     CL12ACKER    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         USING  STACK,R10          make storage addressable         LR     R10,R1             establish stack addressability         ST     R14,SAVER14B       save previous r14         ST     R9,SAVER10B        save previous r10         LR     R1,R3              restore saved argument r1START    ST     R1,M               stack m         ST     R2,N               stack nIF1      C      R1,=F'0'           if m<>0         BNE    IF2                then goto if2         LR     R11,R2             n         LA     R11,1(R11)         return n+1         B      EXITIF2      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      EXITIF3      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         BR     R14                return to caller         LTORG         DROP   R12                base no longer neededSTACK    DSECT                     dynamic areaSAVER14B DS     F                  saved r14SAVER10B DS     F                  saved r10M        DS     F                  mN        DS     F                  nSTACKLEN 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)     addq.l  #1,d4    cmp.l   #n,d4    ble     .loopm     addq.l  #1,d3    cmp.l   #m,d3    ble     .loopn exit    move.l  execBase,a6    move.l  dosBase,a1    jsr     _LVOCloseLibrary(a6)    rts;; ackermann function;; in:;; d3 = m; d4 = n;; out:;; d5 = ans;ackermann    move.l  d3,-(sp)    move.l  d4,-(sp)     tst.l   d3    bne     .l1    move.l  d4,d5    addq.l  #1,d5    bra     .return.l1    tst.l   d4    bne     .l2    subq.l  #1,d3    moveq   #1,d4    bsr     ackermann    bra     .return.l2    subq.l  #1,d4    bsr     ackermann    move.l  d5,d4    subq.l  #1,d3    bsr     ackermann .return    move.l  (sp)+,d4    move.l  (sp)+,d3    rts;; variables;dosBase    dc.l    0 printfArgs    dcb.l   3;; strings;dosName    dc.b    "dos.library",0 outString    dc.b    "ackermann (%ld,%ld) is: %ld",10,0

## 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.	retackm:	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 recursionackmn:	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 inNMAX:	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	; Divisorprdgt:	lxi	d,-1prdgtl:	inx	d	; Divide by 10 through trial subtraction	dad	b	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 numberpnum:	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	100hsection	.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 doneNMAX:	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	add	dl,'0'	; DX holds remainder - add ASCII 0	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 stringprstr:	mov	ah,9	int	21h	retsection	.data	db	'*****'	; Placeholder for ASCII numberpnum:	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 ; : [email protected] \ "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	[email protected] 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 ackOf0 4 ackOf1 0 ackOf1 1 ackOf2 1 ackOf2 2 ackOf3 1 ackOf3 3 ackOf4 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              *//*********************************/.datasMessResult:        .asciz "Result for @  @  : @ \n"szMessError:        .asciz "Overflow !!.\n"szCarriageReturn:   .asciz "\n" /*********************************//* UnInitialized data            *//*********************************/.bsssZoneConv:        .skip 24/*********************************//*  code section                 *//*********************************/.text.global main main:                           // entry of program     mov x3,#0    mov x4,#01:    mov x0,x3    mov x1,x4    bl ackermann    mov x5,x0    mov x0,x3    ldr x1,qAdrsZoneConv        // else display odd message    bl conversion10             // call decimal conversion    ldr x0,qAdrsMessResult    ldr x1,qAdrsZoneConv        // insert value conversion in message    bl strInsertAtCharInc    mov x6,x0    mov x0,x4    ldr x1,qAdrsZoneConv        // else display odd message    bl conversion10             // call decimal conversion    mov x0,x6    ldr x1,qAdrsZoneConv        // insert value conversion in message    bl strInsertAtCharInc    mov x6,x0    mov x0,x5    ldr x1,qAdrsZoneConv        // else display odd message    bl conversion10             // call decimal conversion    mov x0,x6    ldr x1,qAdrsZoneConv        // insert value conversion in message    bl strInsertAtCharInc    bl affichageMess    add x4,x4,#1    cmp x4,#NMAXI    blt 1b    mov x4,#0    add x3,x3,#1    cmp x3,#MMAXI    blt 1b100:                            // standard end of the program     mov x0, #0                  // return code    mov x8, #EXIT               // request to exit program    svc #0                      // perform the system call qAdrszCarriageReturn:     .quad szCarriageReturnqAdrsMessResult:          .quad sMessResultqAdrsZoneConv:            .quad sZoneConv/***************************************************//*     fonction ackermann              *//***************************************************/// x0 contains a number m// x1 contains a number n// x0 return résultackermann:    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 100f1:    mov x2,x0    sub x1,x1,#1    bl ackermann    mov x1,x0    sub x0,x2,#1    bl ackermann    b 100f5:    adds x0,x1,#1    bcc 100f    ldr x0,qAdrszMessError    bl affichageMess    mov x0,-1100:     ldp x2,x3,[sp],16         // restaur des  2 registres    ldp x1,lr,[sp],16         // restaur des  2 registres    retqAdrszMessError:        .quad szMessError /********************************************************//*        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)  FIRETURN (0) PROC Push(BYTE v)  IF stacksize=maxsize THEN    PrintE("Error: stack is full!")    Break()  FI  stack(stacksize)=v  stacksize==+1RETURN BYTE FUNC Pop()  IF IsEmpty() THEN    PrintE("Error: stack is empty!")    Break()  FI  stacksize==-1RETURN (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  ODRETURN (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  ODRETURN
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));}

with Ada.Text_IO;  use Ada.Text_IO; 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.Natopen import Data.Nat.Showopen import IO module Ackermann where ack : ℕ -> ℕ -> ℕack zero n = n + 1ack (suc m) zero = ack m 1ack (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")   endend
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)   ODEND # 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_mend.
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              *//*********************************/.datasMessResult:        .asciz "Result for @  @  : @ \n"szMessError:        .asciz "Overflow !!.\n"szCarriageReturn:   .asciz "\n" /*********************************//* UnInitialized data            *//*********************************/.bsssZoneConv:        .skip 24/*********************************//*  code section                 *//*********************************/.text.global main main:                           @ entry of program     mov r3,#0    mov r4,#01:    mov r0,r3    mov r1,r4    bl ackermann    mov r5,r0    mov r0,r3    ldr r1,iAdrsZoneConv        @ else display odd message    bl conversion10             @ call decimal conversion    ldr r0,iAdrsMessResult    ldr r1,iAdrsZoneConv        @ insert value conversion in message    bl strInsertAtCharInc    mov r6,r0    mov r0,r4    ldr r1,iAdrsZoneConv        @ else display odd message    bl conversion10             @ call decimal conversion    mov r0,r6    ldr r1,iAdrsZoneConv        @ insert value conversion in message    bl strInsertAtCharInc    mov r6,r0    mov r0,r5    ldr r1,iAdrsZoneConv        @ else display odd message    bl conversion10             @ call decimal conversion    mov r0,r6    ldr r1,iAdrsZoneConv        @ insert value conversion in message    bl strInsertAtCharInc    bl affichageMess    add r4,#1    cmp r4,#NMAXI    blt 1b    mov r4,#0    add r3,#1    cmp r3,#MMAXI    blt 1b100:                            @ standard end of the program     mov r0, #0                  @ return code    mov r7, #EXIT               @ request to exit program    svc #0                      @ perform the system call iAdrszCarriageReturn:     .int szCarriageReturniAdrsMessResult:          .int sMessResultiAdrsZoneConv:            .int sZoneConv/***************************************************//*     fonction ackermann              *//***************************************************/// r0 contains a number m// r1 contains a number n// r0 return résultackermann:    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 100f1:    mov r2,r0    sub r1,r1,#1    bl ackermann    mov r1,r0    sub r0,r2,#1    bl ackermann    b 100f5:    adds r0,r1,#1    bcc 100f    ldr r0,iAdrszMessError    bl affichageMess    bkpt100:    pop {r1-r2,lr}             @ restaur registers    bx lr                      @ returniAdrszMessError:        .int szMessError/***************************************************//*      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

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 EndIfEndFunc ### 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 wantFunc 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		Return $return EndIfEndFunc ;==>Ackermann ## AWK 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))} BEGIN { for(n=0; n < 7; n++) { for(m=0; m < 4; m++) { print "A(" m "," n ") = " ackermann(m,n) } }} ## Babel main: {((0 0) (0 1) (0 2) (0 3) (0 4) (1 0) (1 1) (1 2) (1 3) (1 4) (2 0) (2 1) (2 2) (2 3) (3 0) (3 1) (3 2) (4 0)) { dup "A(" << { %d " " . << } ... ") = " << reverse give ack %d cr << } ... } ack!: { dup zero? { <-> dup zero? { <-> cp 1 - <- <- 1 - -> ack -> ack } { <-> 1 - <- 1 -> ack } if } { zap 1 + } if } zero?!: { 0 = }  Output: A(0 0 ) = 1 A(0 1 ) = 2 A(0 2 ) = 3 A(0 3 ) = 4 A(0 4 ) = 5 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 ## BASIC ### Applesoft BASIC 100 DIM R%(2900),M(2900),N(2900)110 FOR M = 0 TO 3120 FOR N = 0 TO 4130 GOSUB 200"ACKERMANN140 PRINT "ACK("M","N") = "ACK150 NEXT N, M160 END 200 M(SP) = M210 N(SP) = N REM A(M - 1, A(M, N - 1))220 IF M > 0 AND N > 0 THEN N = N - 1 : R%(SP) = 0 : SP = SP + 1 : GOTO 200 REM A(M - 1, 1)230 IF M > 0 THEN M = M - 1 : N = 1 : R%(SP) = 1 : SP = SP + 1 : GOTO 200 REM N + 1240 ACK = N + 1 REM RETURN250 M = M(SP) : N = N(SP) : IF SP = 0 THEN RETURN260 FOR SP = SP - 1 TO 0 STEP -1 : IF R%(SP) THEN M = M(SP) : N = N(SP) : NEXT SP : SP = 0 : RETURN270 M = M - 1 : N = ACK : R%(SP) = 1 : SP = SP + 1 : GOTO 200 ### BASIC256 dim stack(5000, 3) # BASIC-256 lacks functions (as of ver. 0.9.6.66)stack[0,0] = 3 # Mstack[0,1] = 7 # Nlev = 0 gosub ackermannprint "A("+stack[0,0]+","+stack[0,1]+") = "+stack[0,2]end ackermann: if stack[lev,0]=0 then stack[lev,2] = stack[lev,1]+1 return end if if stack[lev,1]=0 then lev = lev+1 stack[lev,0] = stack[lev-1,0]-1 stack[lev,1] = 1 gosub ackermann stack[lev-1,2] = stack[lev,2] lev = lev-1 return end if lev = lev+1 stack[lev,0] = stack[lev-1,0] stack[lev,1] = stack[lev-1,1]-1 gosub ackermann stack[lev,0] = stack[lev-1,0]-1 stack[lev,1] = stack[lev,2] gosub ackermann stack[lev-1,2] = stack[lev,2] lev = lev-1 return Output:  A(3,7) = 1021  # BASIC256 since 0.9.9.1 supports functionsfor m = 0 to 3 for n = 0 to 4 print m + " " + n + " " + ackermann(m,n) next nnext mend function ackermann(m,n) 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)) endif end ifend function Output: 0 0 1 0 1 2 0 2 3 0 3 4 0 4 5 1 0 2 1 1 3 1 2 4 1 3 5 1 4 6 2 0 3 2 1 5 2 2 7 2 3 9 2 4 11 3 0 5 3 1 13 3 2 29 3 3 61 3 4 125 ### BBC BASIC  PRINT FNackermann(3, 7) END DEF FNackermann(M%, N%) IF M% = 0 THEN = N% + 1 IF N% = 0 THEN = FNackermann(M% - 1, 1) = FNackermann(M% - 1, FNackermann(M%, N%-1)) ### QuickBasic Works with: QuickBasic version 4.5 BASIC runs out of stack space very quickly. The call ack(3, 4) gives a stack error. DECLARE FUNCTION ack! (m!, n!) FUNCTION ack (m!, n!) IF m = 0 THEN ack = n + 1 IF m > 0 AND n = 0 THEN ack = ack(m - 1, 1) END IF IF m > 0 AND n > 0 THEN ack = ack(m - 1, ack(m, n - 1)) END IFEND FUNCTION ## Batch File Had trouble with this, so called in the gurus at StackOverflow. Thanks to Patrick Cuff for pointing out where I was going wrong. ::Ackermann.cmd@echo offset depth=0:ackif %1==0 goto m0if %2==0 goto n0 :elseset /a n=%2-1set /a depth+=1call :ack %1 %n%set t=%errorlevel%set /a depth-=1set /a m=%1-1set /a depth+=1call :ack %m% %t%set t=%errorlevel%set /a depth-=1if %depth%==0 ( exit %t% ) else ( exit /b %t% ) :m0set/a n=%2+1if %depth%==0 ( exit %n% ) else ( exit /b %n% ) :n0set /a m=%1-1set /a depth+=1call :ack %m% 1set t=%errorlevel%set /a depth-=1if %depth%==0 ( exit %t% ) else ( exit /b %t% ) Because of the exit statements, running this bare closes one's shell, so this test routine handles the calling of Ackermann.cmd ::Ack.cmd@echo offcmd/c ackermann.cmd %1 %2echo Ackermann(%1, %2)=%errorlevel% A few test runs: D:\Documents and Settings\Bruce>ack 0 4 Ackermann(0, 4)=5 D:\Documents and Settings\Bruce>ack 1 4 Ackermann(1, 4)=6 D:\Documents and Settings\Bruce>ack 2 4 Ackermann(2, 4)=11 D:\Documents and Settings\Bruce>ack 3 4 Ackermann(3, 4)=125 ## bc Requires a bc that supports long names and the print statement. Works with: OpenBSD bc Works with: GNU bc define ack(m, n) { if ( m == 0 ) return (n+1); if ( n == 0 ) return (ack(m-1, 1)); return (ack(m-1, ack(m, n-1)));} for (n=0; n<7; n++) { for (m=0; m<4; m++) { print "A(", m, ",", n, ") = ", ack(m,n), "\n"; }}quit ## BCPL GET "libhdr" LET ack(m, n) = m=0 -> n+1, n=0 -> ack(m-1, 1), ack(m-1, ack(m, n-1)) LET start() = VALOF{ FOR i = 0 TO 6 FOR m = 0 TO 3 DO writef("ack(%n, %n) = %n*n", m, n, ack(m,n)) RESULTIS 0} ## beeswax Iterative slow version:  >[email protected]@[email protected] if m>0 and n>0 => replace m,n with m-1,m,n-1 >@[email protected]'[email protected]@[email protected] if m>0 and n=0 => replace m,n with m-1,1_ii>[email protected]'d?g?Pfzp if m=0 => replace m,n with n+1 >I; b < <  A functional and recursive realization of the version above. Functions are realized by direct calls of functions via jumps (instruction J) to the entry points of two distinct functions: 1st function _ii (input function) with entry point at (row,col) = (4,1) 2nd function Ag~1.... (Ackermann function) with entry point at (row,col) = (1,1) Each block of 1FJ or 1fFJ in the code is a call of the Ackermann function itself. [email protected]'p?g?Pf1FJ Ackermann function. if m=0 => run Ackermann function (m, n+1) xI; [email protected]'[email protected] if m>0 and n=0 => run Ackermann (m-1,1) [email protected][email protected] if m>0 and n>0 => run Ackermann(m,Ackermann(m-1,n-1))_ii1FJ input function. Input m,n, then execute Ackermann(m,n) Highly optimized and fast version, returns A(4,1)/A(5,0) almost instantaneously:  >[email protected][email protected]@[email protected]@Php if m>4 and n>0 => replace m,n with m-1,m,n-1 >~4~L#1~2hg'[email protected]?f2h p if m>4 and n=0 => replace m,n with m-1,1 # q < /n+3 times \ #X~4K#?2Fg?PPP>@[email protected]"pb if m=4 => replace m,n with 2^(2^(....)))-3 # >~3K#?g?PPP~2BMMp>@MMMp if m=3 => replace m,n with 2^(n+3)-3_ii>[email protected]'#?g?P p M if m=0 => replace m,n with n+1 z I ~>~1K#?g?PP p if m=1 => replace m,n with n+2 f ; >2K#?g?~2.PPPp if m=2 => replace m,n with 2n+3 z b < < < d <  Higher values than A(4,1)/(5,0) lead to UInt64 wraparound, support for numbers bigger than 2^64-1 is not implemented in these solutions. ## Befunge ### Befunge-93 Translation of: ERRE Since Befunge-93 doesn't have recursive capabilities we need to use an iterative algorithm. &>&>vvg0>#0\#-:#1_1v@v:\<vp0 0:-1<\+<^>00p>:#^_$1+\:#^_$.  ### Befunge-98 Works with: CCBI version 2.1 r[1&&{0>v ju>[email protected] 1> \:v^ v:\_$1+\^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‿34 A 1‿46 A 2‿411 A 3‿4125 ## 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...

## 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            {                _m = Convert.ToInt32(Console.ReadLine());            }            catch (Exception)            {                Console.WriteLine("Please enter a number.");            }            Console.Write("n = ");            try            {                _n = Convert.ToInt32(Console.ReadLine());            }            catch (Exception)            {                Console.WriteLine("Please enter a number.");            }            //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");            Console.ReadKey();        }        public class OverflowlessStack<T>        {            internal sealed class SinglyLinkedNode            {                private const int ArraySize = 2048;                T[] _array;                int _size;                public SinglyLinkedNode Next;                public SinglyLinkedNode()                {                    _array = new T[ArraySize];                }                public bool IsEmpty { get { return _size == 0; } }                public SinglyLinkedNode Push(T item)                {                    if (_size == ArraySize - 1)                    {                        SinglyLinkedNode n = new SinglyLinkedNode();                        n.Next = this;                        n.Push(item);                        return n;                    }                    _array[_size++] = item;                    return this;                }                public T Pop()                {                    return _array[--_size];                }            }            private SinglyLinkedNode _head = new SinglyLinkedNode();             public T Pop()            {                T ret = _head.Pop();                if (_head.IsEmpty && _head.Next != null)                    _head = _head.Next;                return ret;            }            public void Push(T item)            {                _head = _head.Push(item);            }            public bool IsEmpty            {                get { return _head.Next == null && _head.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 functionack = 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)))    endend 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, "")    endend 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.       LINKAGE SECTION.       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 function0030 //0040 FUNC a#(m#,n#)0050   IF m#=0 THEN RETURN n#+10060   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 values0110 //0120 ZONE 50130 FOR m#:=0 TO 3 DO0140   FOR n#:=0 TO 4 DO PRINT a#(m#,n#),0150   PRINT0160 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))  ENDEND 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.LnEND 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))  endend #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 nothrowout(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))    ficorp; /* 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()    odcorp
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 + 1end;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 rprint r

## Egel

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

## Eiffel

 note	description: "Example of Ackerman function"	synopsis: "[		The EIS link below (in Eiffel Studio) will launch in either an in-IDE browser or		and external browser (your choice). The protocol informs Eiffel Studio about what		program to use to open the src' reference, which can be URI, PDF, or DOC. See		second EIS for more information.		]"	EIS: "name=Ackermann_function", "protocol=URI", "tag=rosetta_code",		"src=http://rosettacode.org/wiki/Ackermann_function"	EIS: "name=eis_protocols", "protocol=URI", "tag=eiffel_docs",		"src=https://docs.eiffel.com/book/eiffelstudio/protocols" class	APPLICATION create	make feature {NONE} -- Initialization 	make		do			print ("%N A(0,0):" + ackerman (0, 0).out)			print ("%N A(1,0):" + ackerman (1, 0).out)			print ("%N A(0,1):" + ackerman (0, 1).out)			print ("%N A(1,1):" + ackerman (1, 1).out)			print ("%N A(2,0):" + ackerman (2, 0).out)			print ("%N A(2,1):" + ackerman (2, 1).out)			print ("%N A(2,2):" + ackerman (2, 2).out)			print ("%N A(0,2):" + ackerman (0, 2).out)			print ("%N A(1,2):" + ackerman (1, 2).out)			print ("%N A(3,3):" + ackerman (3, 3).out)			print ("%N A(3,4):" + ackerman (3, 4).out)		end feature -- Access 	ackerman (m, n: NATURAL): NATURAL		do			if m = 0 then				Result := n + 1			elseif n = 0 then				Result := ackerman (m - 1, 1)			else				Result := ackerman (m - 1, ackerman (m, n - 1))			end		endend 

## Ela

ack 0 n = n+1ack m 0 = ack (m - 1) 1ack 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))        }    };     console.readChar()}
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.

## 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 ifend 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-\[email protected]@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 }

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

 |=  [[email protected] [email protected]]?:  =(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 -> NatA Z n = S nA (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 @. (#[email protected],&*) M.c1=: >:@] NB. if 0=x, 1+yc2=: <:@[ ack 1: NB. if 0=y, (x-1) ack 1c3=: <:@[ ack [ ack <:@] NB. else, (x-1) ack x ack y-1 Example use:  0 ack 34 1 ack 35 2 ack 39 3 ack 361 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 71  2  3  4   5   6   7    82  3  4  5   6   7   8    93  5  7  9  11  13  15   175 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 219729    5 Ack 065533

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 50 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 code3 -~ [ ({&(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) ? n.add(BigInteger.ONE) : ack(m.subtract(BigInteger.ONE), n.equals(BigInteger.ZERO) ? BigInteger.ONE : ack(m, n.subtract(BigInteger.ONE)));} Works with: Java version 8+ @FunctionalInterfacepublic 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 ) ; } public enum$ {    $$; private static <INTERMEDIARY, OUTPUT> OUTPUT new_(Stream<INTERMEDIARY> stream, Predicate<INTERMEDIARY> predicate, Function<INTERMEDIARY, OUTPUT> function) { return stream .filter(predicate) .map(function) .findAny() .orElseThrow(RuntimeException::new) ; } }} import java.math.BigInteger;import java.util.Stack;import java.util.function.BinaryOperator;import java.util.stream.Collectors;import java.util.stream.Stream; public interface Ackermann { public static Ackermann new_(BigInteger number1, BigInteger number2, Stack<BigInteger> stack, boolean flag) { return .new_(number1, number2, stack, flag); } public static void main(String... arguments) { .main(arguments); } public BigInteger number1(); public BigInteger number2(); public Stack<BigInteger> stack(); public boolean flag(); public enum  {$$;     private static final BigInteger ZERO = BigInteger.ZERO;    private static final BigInteger ONE = BigInteger.ONE;    private static final BigInteger TWO = BigInteger.valueOf(2);    private static final BigInteger THREE = BigInteger.valueOf(3);    private static final BigInteger FOUR = BigInteger.valueOf(4);     private static Ackermann new_(BigInteger number1, BigInteger number2, Stack<BigInteger> stack, boolean flag) {      return (FunctionalAckermann) field -> {        switch (field) {          case number1: return number1;          case number2: return number2;          case stack: return stack;          case flag: return flag;          default: throw new UnsupportedOperationException(            field instanceof Field              ? "Field checker has not been updated properly."              : "Field is not of the correct type."          );        }      };    }     private static final BinaryOperator<BigInteger> ACKERMANN =       TailRecursive.new_(        (BigInteger number1, BigInteger number2) ->          new_(            number1,            number2,            Stream.of(number1).collect(              Collectors.toCollection(Stack::new)            ),            false          )        ,        ackermann -> {          BigInteger number1 = ackermann.number1();          BigInteger number2 = ackermann.number2();          Stack<BigInteger> stack = ackermann.stack();          if (!stack.empty() && !ackermann.flag()) {            number1 = stack.pop();          }          switch (number1.intValue()) {            case 0:              return new_(                number1,                number2.add(ONE),                stack,                false              );            case 1:              return new_(                number1,                number2.add(TWO),                stack,                false              );            case 2:              return new_(                number1,                number2.multiply(TWO).add(THREE),                stack,                false              );            default:              if (ZERO.equals(number2)) {                return new_(                  number1.subtract(ONE),                  ONE,                  stack,                  true                );              } else {                stack.push(number1.subtract(ONE));                return new_(                  number1,                  number2.subtract(ONE),                  stack,                  true                );              }          }        },        ackermann -> ackermann.stack().empty(),        Ackermann::number2      )::apply    ;     private static void main(String... arguments) {      System.out.println(ACKERMANN.apply(FOUR, TWO));    }     private enum Field {      number1,      number2,      stack,      flag    }     @FunctionalInterface    private interface FunctionalAckermann extends FunctionalField<Field>, Ackermann {      @Override      public default BigInteger number1() {        return field(Field.number1);      }       @Override      public default BigInteger number2() {        return field(Field.number2);      }       @Override      public default Stack<BigInteger> stack() {        return field(Field.stack);      }       @Override      public default boolean flag() {        return field(Field.flag);      }    }  }}
/* * Source https://stackoverflow.com/a/51092690/5520417 */ package matematicas; import java.math.BigInteger;import java.util.HashMap;import java.util.Stack; /** * @author rodri * */ public class IterativeAckermannMemoryOptimization extends Thread {   /**   * Max percentage of free memory that the program will use. Default is 10% since   * the majority of the used devices are mobile and therefore it is more likely   * that the user will have more opened applications at the same time than in a   * desktop device   */  private static Double SYSTEM_MEMORY_LIMIT_PERCENTAGE = 0.1;   /**   * Attribute of the type IterativeAckermann   */  private IterativeAckermann iterativeAckermann;   /**   * @param iterativeAckermann   */  public IterativeAckermannMemoryOptimization(IterativeAckermann iterativeAckermann) {    super();    this.iterativeAckermann = iterativeAckermann;  }   /**   * @return   */  public IterativeAckermann getIterativeAckermann() {    return iterativeAckermann;  }   /**   * @param iterativeAckermann   */  public void setIterativeAckermann(IterativeAckermann iterativeAckermann) {    this.iterativeAckermann = iterativeAckermann;  }   public static Double getSystemMemoryLimitPercentage() {    return SYSTEM_MEMORY_LIMIT_PERCENTAGE;  }   /**   * Principal method of the thread. Checks that the memory used doesn't exceed or   * equal the limit, and informs the user when that happens.   */  @Override  public void run() {    String operating_system = System.getProperty("os.name").toLowerCase();    if ( operating_system.equals("windows") || operating_system.equals("linux") || operating_system.equals("macintosh") ) {      SYSTEM_MEMORY_LIMIT_PERCENTAGE = 0.25;    }     while ( iterativeAckermann.getConsumed_heap() >= SYSTEM_MEMORY_LIMIT_PERCENTAGE * Runtime.getRuntime().freeMemory() ) {      try {        wait();      }      catch ( InterruptedException e ) {        // TODO Auto-generated catch block        e.printStackTrace();      }    }    if ( ! iterativeAckermann.isAlive() )      iterativeAckermann.start();    else      notifyAll();   } }  public class IterativeAckermann extends Thread {   /*   * Adjust parameters conveniently   */  /**   *    */  private static final int HASH_SIZE_LIMIT = 636;   /**   *    */  private BigInteger m;   /**   *    */  private BigInteger n;   /**   *    */  private Integer hash_size;   /**   *    */  private Long consumed_heap;   /**   * @param m   * @param n   * @param invalid   * @param invalid2   */  public IterativeAckermann(BigInteger m, BigInteger n, Integer invalid, Long invalid2) {    super();    this.m = m;    this.n = n;    this.hash_size = invalid;    this.consumed_heap = invalid2;  }   /**   *    */  public IterativeAckermann() {    // TODO Auto-generated constructor stub    super();    m = null;    n = null;    hash_size = 0;    consumed_heap = 0l;  }   /**   * @return   */  public static BigInteger getLimit() {    return LIMIT;  }   /**   * @author rodri   *   * @param <T1>   * @param <T2>   */  /**   * @author rodri   *   * @param <T1>   * @param <T2>   */  static class Pair<T1, T2> {     /**     *      */    /**     *      */    T1 x;     /**     *      */    /**     *      */    T2 y;     /**     * @param x_     * @param y_     */    /**     * @param x_     * @param y_     */    Pair(T1 x_, T2 y_) {      x = x_;      y = y_;    }     /**     *     */    /**     *     */    @Override    public int hashCode() {      return x.hashCode() ^ y.hashCode();    }     /**     *     */    /**     *     */    @Override    public boolean equals(Object o_) {       if ( o_ == null ) {        return false;      }      if ( o_.getClass() != this.getClass() ) {        return false;      }      Pair<?, ?> o = (Pair<?, ?>) o_;      return x.equals(o.x) && y.equals(o.y);    }  }   /**   *    */  private static final BigInteger LIMIT = new BigInteger("6");   /**   * @param m   * @param n   * @return   */   /**   *   */  @Override  public void run() {    while ( hash_size >= HASH_SIZE_LIMIT ) {      try {        this.wait();      }      catch ( InterruptedException e ) {        // TODO Auto-generated catch block        e.printStackTrace();      }    }    for ( BigInteger i = BigInteger.ZERO; i.compareTo(LIMIT) == - 1; i = i.add(BigInteger.ONE) ) {      for ( BigInteger j = BigInteger.ZERO; j.compareTo(LIMIT) == - 1; j = j.add(BigInteger.ONE) ) {        IterativeAckermann iterativeAckermann = new IterativeAckermann(i, j, null, null);        System.out.printf("Ackmermann(%d, %d) = %d\n", i, j, iterativeAckermann.iterative_ackermann(i, j));       }    }  }   /**   * @return   */  public BigInteger getM() {    return m;  }   /**   * @param m   */  public void setM(BigInteger m) {    this.m = m;  }   /**   * @return   */  public BigInteger getN() {    return n;  }   /**   * @param n   */  public void setN(BigInteger n) {    this.n = n;  }   /**   * @return   */  public Integer getHash_size() {    return hash_size;  }   /**   * @param hash_size   */  public void setHash_size(Integer hash_size) {    this.hash_size = hash_size;  }   /**   * @return   */  public Long getConsumed_heap() {    return consumed_heap;  }   /**   * @param consumed_heap   */  public void setConsumed_heap(Long consumed_heap) {    this.consumed_heap = consumed_heap;  }   /**   * @param m   * @param n   * @return   */  public BigInteger iterative_ackermann(BigInteger m, BigInteger n) {    if ( m.compareTo(BigInteger.ZERO) != - 1 && m.compareTo(BigInteger.ZERO) != - 1 )      try {        HashMap<Pair<BigInteger, BigInteger>, BigInteger> solved_set = new HashMap<Pair<BigInteger, BigInteger>, BigInteger>(900000);        Stack<Pair<BigInteger, BigInteger>> to_solve = new Stack<Pair<BigInteger, BigInteger>>();        to_solve.push(new Pair<BigInteger, BigInteger>(m, n));         while ( ! to_solve.isEmpty() ) {          Pair<BigInteger, BigInteger> head = to_solve.peek();          if ( head.x.equals(BigInteger.ZERO) ) {            solved_set.put(head, head.y.add(BigInteger.ONE));            to_solve.pop();          }          else if ( head.y.equals(BigInteger.ZERO) ) {            Pair<BigInteger, BigInteger> next = new Pair<BigInteger, BigInteger>(head.x.subtract(BigInteger.ONE), BigInteger.ONE);            BigInteger result = solved_set.get(next);            if ( result == null ) {              to_solve.push(next);            }            else {              solved_set.put(head, result);              to_solve.pop();            }          }          else {            Pair<BigInteger, BigInteger> next0 = new Pair<BigInteger, BigInteger>(head.x, head.y.subtract(BigInteger.ONE));            BigInteger result0 = solved_set.get(next0);            if ( result0 == null ) {              to_solve.push(next0);            }            else {              Pair<BigInteger, BigInteger> next = new Pair<BigInteger, BigInteger>(head.x.subtract(BigInteger.ONE), result0);              BigInteger result = solved_set.get(next);              if ( result == null ) {                to_solve.push(next);              }              else {                solved_set.put(head, result);                to_solve.pop();              }            }          }        }        this.hash_size = solved_set.size();        System.out.println("Hash Size: " + hash_size);        consumed_heap = (Runtime.getRuntime().totalMemory() / (1024 * 1024));        System.out.println("Consumed Heap: " + consumed_heap + "m");        setHash_size(hash_size);        setConsumed_heap(consumed_heap);        return solved_set.get(new Pair<BigInteger, BigInteger>(m, n));       }      catch ( OutOfMemoryError e ) {        // TODO: handle exception        e.printStackTrace();      }    throw new IllegalArgumentException("The arguments must be non-negative integers.");  }   /**   * @param args   */  /**   * @param args   */  public static void main(String[] args) {    IterativeAckermannMemoryOptimization iterative_ackermann_memory_optimization = new IterativeAckermannMemoryOptimization(        new IterativeAckermann());    iterative_ackermann_memory_optimization.start();  }}

## JavaScript

### ES5

function ack(m, n) { return m === 0 ? n + 1 : ack(m - 1, n === 0  ? 1 : ack(m, n - 1));}

### Eliminating Tail Calls

function ack(M,N) {  for (; M > 0; M--) {    N = N === 0 ? 1 : ack(M,N-1);  }  return N+1;}

### Iterative, With Explicit Stack

function stackermann(M, N) {  const stack = [];  for (;;) {    if (M === 0) {      N++;      if (stack.length === 0) return N;      const r = stack[stack.length-1];      if (r[1] === 1) stack.length--;      else r[1]--;      M = r[0];    } else if (N === 0) {      M--;      N = 1;    } else {      M--      stack.push([M, N]);      N = 1;    }  }}

### Stackless Iterative

#!/usr/bin/env nodejsfunction ack(M, N){	const next = new Float64Array(M + 1);	const goal = new Float64Array(M + 1).fill(1, 0, M);	const n = N + 1; 	// This serves as a sentinel value;	// next[M] never equals goal[M] == -1,	// so we don't need an extra check for	// loop termination below.	goal[M] = -1; 	let v;	do {		v = next[0] + 1;		let m = 0;		while (next[m] === goal[m]) {			goal[m] = v;			next[m++]++;		}		next[m]++;	} while (next[M] !== n);	return v;}var args = process.argv;console.log(ack(parseInt(args[2]), parseInt(args[3])));
Output:
> time ./ack.js 4 1
65533
./ack.js 4 1  0,48s user 0,03s system 100% cpu 0,505 total ; AMD FX-8350 @ 4 GHz


### ES6

(() => {    'use strict';     // ackermann :: Int -> Int -> Int    const ackermann = m => n => {        const go = (m, n) =>            0 === m ? (                succ(n)            ) : go(pred(m), 0 === n ? (                1            ) : go(m, pred(n)));        return go(m, n);    };     // TEST -----------------------------------------------    const main = () => console.log(JSON.stringify(        [0, 1, 2, 3].map(            flip(ackermann)(3)        )    ));      // GENERAL FUNCTIONS ----------------------------------     // flip :: (a -> b -> c) -> b -> a -> c    const flip = f =>        x => y => f(y)(x);     // pred :: Enum a => a -> a    const pred = x => x - 1;     // succ :: Enum a => a -> a    const succ = x => 1 + x;      // MAIN ---    return main();})();
Output:
[4,5,9,61]

## Joy

From here

DEFINE ack == [ [ [pop null]  popd succ ]                 [ [null]  pop pred 1 ack ]                 [ [dup pred swap] dip pred ack ack ] ]               cond.

another using a combinator

DEFINE ack == [ [ [pop null]  [popd succ] ] 		[ [null]  [pop pred 1]  [] ] 		[ [[dup pred swap] dip pred] [] [] ] ]               condnestrec.

Whenever there are two definitions with the same name, the last one is the one that is used, when invoked.

## jq

Works with: jq version 1.4

# input: [m,n]def ack:  .[0] as $m | .[1] as$n  | if $m == 0 then$n + 1    elif $n == 0 then [$m-1, 1] | ack    else [$m-1, ([$m, $n-1 ] | ack)] | ack 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.jqA(0,0) = 1A(0,1) = 2A(0,2) = 3A(0,3) = 4A(0,4) = 5A(0,5) = 6A(1,0) = 2A(1,1) = 3A(1,2) = 4A(1,3) = 5A(1,4) = 6A(1,5) = 7A(2,0) = 3A(2,1) = 5A(2,2) = 7A(2,3) = 9A(2,4) = 11A(2,5) = 13A(3,0) = 5A(3,1) = 13A(3,2) = 29A(3,3) = 61A(3,4) = 125A(3,5) = 253A(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 | cache(key) end end; def A(m;n): [m,n,{}] | ack | .[0];  Example: A(4,1) Output: 65533 ## Jsish From javascript entry. /* Ackermann function, in Jsish */ function ack(m, n) { return m === 0 ? n + 1 : ack(m - 1, n === 0 ? 1 : ack(m, n - 1));} if (Interp.conf('unitTest')) { Interp.conf({maxDepth:4096});; ack(1,3);; ack(2,3);; ack(3,3);; ack(1,5);; ack(2,5);; ack(3,5);} /*=!EXPECTSTART!=ack(1,3) ==> 5ack(2,3) ==> 9ack(3,3) ==> 61ack(1,5) ==> 7ack(2,5) ==> 13ack(3,5) ==> 253=!EXPECTEND!=*/ Output: prompt jsish --U Ackermann.jsi 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)) endend 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; LINK; =M0M2; (push return address); 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); M0M2; =LINK; (return address := top of 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 nlmsec 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 = 10Lconst 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 switchend 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-1end ## 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 MKAYIF 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 innerIM 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 luajitlocal 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_dlocal z_cmp, z_cmp_ui, z_init_d, z_set= gmp.z_cmp, gmp.z_cmp_ui, gmp.z_init_set_d, gmp.z_setlocal 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 vend 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 [email protected] 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)))')')')dnlack(3,3) Output: 61  ## MAD 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.8SHOW 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 ifend 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 ifend 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 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=InfinityAckermann1[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] = 3Ackermann2[1,2] = 4Ackermann2[1,3] = 5Ackermann2[1,4] = 6Ackermann2[1,5] = 7Ackermann2[1,6] = 8Ackermann2[1,7] = 9Ackermann2[1,8] = 10Ackermann2[2,1] = 5Ackermann2[2,2] = 7Ackermann2[2,3] = 9Ackermann2[2,4] = 11Ackermann2[2,5] = 13Ackermann2[2,6] = 15Ackermann2[2,7] = 17Ackermann2[2,8] = 19Ackermann2[3,1] = 13Ackermann2[3,2] = 29Ackermann2[3,3] = 61Ackermann2[3,4] = 125Ackermann2[3,5] = 253Ackermann2[3,6] = 509Ackermann2[3,7] = 1021Ackermann2[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: 655332003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880........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) ); endend ## 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 forend for ## МК-61/52 П1 <-> П0 ПП 06 С/П ИП0 x=0 13 ИП11 + В/О ИП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 limitMCSKIP 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 0ACK(%%T1.-1.,1)MCGO L0%L2.ACK(%%T1.-1.,ACK(%T1.,%%T2.-1.))>"" Macro ACK now defined, so try it outa(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) => 1a(0,1) => 2a(0,2) => 3a(0,3) => 4a(0,4) => 5a(0,5) => 6a(1,0) => 2a(1,1) => 3a(1,2) => 4a(1,3) => 5a(1,4) => 6a(2,0) => 3a(2,1) => 5a(2,2) => 7a(2,3) => 9a(3,0) => 5a(3,1) => 13a(3,2) => 29a(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)) ENDEND 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.WriteLnEND ackerman. Output: [email protected]:~/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) ; 10Write Ackermann(2,8) ; 19Write 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++) { print("ackermann(m, n) = (ackermann(m, n))\n"); }}  A terser version using implicit match (which doesn't use the alias A internally):  def ackermann(m, n) { | (0, n) => n + 1 | (m, 0) when m > 0 => ackermann(m - 1, 1) | (m, n) when m > 0 && n > 0 => ackermann(m - 1, ackermann(m, n - 1)) | _ => throw Exception("invalid inputs");}  Or, if we were set on using the A notation, we could do this:  def ackermann = { def A(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"); } A}  ## NetRexx /* NetRexx */options replace format comments java crossref symbols binary numeric digits 66 parse arg j_ k_ .if j_ = '' | j_ = '.' | \j_.datatype('w') then j_ = 3if k_ = '' | k_ = '.' | \k_.datatype('w') then k_ = 5 loop m_ = 0 to j_ say loop n_ = 0 to k_ say 'ackermann('m_','n_') =' ackermann(m_, n_).right(5) end n_ end m_return method ackermann(m, n) public static select when m = 0 then rval = n + 1 when n = 0 then rval = ackermann(m - 1, 1) otherwise rval = ackermann(m - 1, ackermann(m, n - 1)) end return rval  ## NewLISP  #! /usr/local/bin/newlisp (define (ackermann m n) (cond ((zero? m) (inc n)) ((zero? n) (ackermann (dec m) 1)) (true (ackermann (- m 1) (ackermann m (dec n))))))  In case of stack overflow error, you have to start your program with a proper "-s <value>" flag as "newlisp -s 100000 ./ackermann.lsp". See http://www.newlisp.org/newlisp_manual.html#stack_size  ## Nim from strutils import parseInt proc ackermann(m, n: int64): int64 = if m == 0: result = n + 1 elif n == 0: result = ackermann(m - 1, 1) else: result = ackermann(m - 1, ackermann(m, n - 1)) proc getNumber(): int = try: result = stdin.readLine.parseInt except ValueError: echo "An integer, please!" result = getNumber() if result < 0: echo "Please Enter a non-negative Integer: " result = getNumber() echo "First non-negative Integer please: "let first = getNumber()echo "Second non-negative Integer please: "let second = getNumber()echo "Result: ", ackermann(first, second)  ## Nit Source: the official Nit’s repository. # Task: Ackermann function## A simple straightforward recursive implementation.module ackermann_function fun ack(m, n: Int): Intdo 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)) ENDEND 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.LnEND 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_intlet one = unit_big_intlet zero = zero_big_intlet succ = succ_big_intlet pred = pred_big_intlet 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_intlet one = unit_big_intlet zero = zero_big_intlet succ = succ_big_intlet pred = pred_big_intlet add = add_big_intlet sub = sub_big_intlet eq = eq_big_intlet 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)); endifendfunction 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; ## 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) endend ::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 endifenddef 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 outputcheck_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 guardstablea(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.)tablea2(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 definitionm 0 eq{n 1 add}ifm 0 gt n 0 eq and{m 1 sub 1 ackermann}ifm 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?} condend}. ## 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 DIM m AS QUAD, n AS QUAD 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 IFEND 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 numbersvoid 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) { stdoutprint(paste(ackermann(m, n), " ")) } stdoutprintln("") }} 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 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)) EndIfEndProcedure 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 nextnext 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 okRaise("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: a0beqz a1, npe #case m = 0beqz a2, mme #case m > 0 & n = 0addi sp, sp, -8 #case m > 0 & n > 0sw ra, 4(sp)sw a1, 0(sp)addi a2, a2, -1jal ackermannlw a1, 0(sp)addi a1, a1, -1mv a2, a0jal ackermannlw t0, 4(sp)addi sp, sp, 8jr t0, 0npe:addi a0, a2, 1jr ra, 0mme:addi sp, sp, -4sw ra, 0(sp)addi a1, a1, -1li a2, 1jal ackermannlw t0, 0(sp)addi sp, sp, 4jr t0, 0  ## Ruby Translation of: Ada def ack(m, n) if m == 0 n + 1 elsif n == 0 ack(m-1, 1) else ack(m-1, ack(m, n-1)) endend 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 clearfunction 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 endendfunctionfunction printacker(m,n) global calls calls=0 printf('ackermann(%d,%d)=',m,n) printf('%d calls=%d\n',ackermann(m,n),calls)endfunctionmaxi=3; maxj=6for i=0:maxi for j=0:maxj printacker(i,j) endend 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 ENDEND Output: Ackermann(4, 0) = 13 Ackermann(3, 3) = 61 Ackermann(2, 6) = 15 Ackermann(1, 9) = 11 Ackermann(0,12) = 13  ## Slate [email protected](Integer traits) ackermann: [email protected](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)) ENDIFEND ## 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  /==!/[email protected]@@[email protected]# | | Ackermann function | | /=========\!==\!====\ recursion:,@/>,@/==ack=!\?\<+# | | | A(0,j) -> j+1 j i \<?\+>[email protected]/# | | A(i,0) -> A(i-1,1) \@\>@\->@/@\<[email protected]/# 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 [email protected] 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 matafunction 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))5611125end ## 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/18152oo::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 methodoo::object create cachedoo::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 ack m [expr {n-1}]] } }} # Some small tweaks...interp recursionlimit {} 100000interp alias {} ack {} cacheable ack But even with all this, you still run into problems calculating ${\displaystyle {\mathit {ack}}(4,3)}$ as that's kind-of large… ## TI-83 BASIC This program assumes the variables N and M are the arguments of the function, and that the list L1 is empty. It stores the result in the system variable ANS. (Program names can be no longer than 8 characters, so I had to truncate the function's name.) PROGRAM:ACKERMAN:If not(M:Then:N+1→N:Return:Else:If not(N:Then:1→N:M-1→M:prgmACKERMAN:Else:N-1→N:M→L1(1+dim(L1:prgmACKERMAN:Ans→N:L1(dim(L1))-1→M:dim(L1)-1→dim(L1:prgmACKERMAN:End:End Here is a handler function that makes the previous function easier to use. (You can name it whatever you want.) PROGRAM:AHANDLER:0→dim(L1:Prompt M:Prompt N:prgmACKERMAN:Disp Ans ## TI-89 BASIC Define A(m,n) = when(m=0, n+1, when(n=0, A(m-1,1), A(m-1, A(m, n-1)))) ## TorqueScript function ackermann(%m,%n){ if(%m==0) return %n+1; if(%m>0&&%n==0) return ackermann(%m-1,1); if(%m>0&&%n>0) return ackermann(%m-1,ackermann(%m,%n-1));} ## TSE SAL // library: math: get: ackermann: recursive <description></description> <version>1.0.0.0.5</version> <version control></version control> (filenamemacro=getmaare.s) [kn, ri, tu, 27-12-2011 14:46:59]INTEGER PROC FNMathGetAckermannRecursiveI( INTEGER mI, INTEGER nI ) IF ( mI == 0 ) RETURN( nI + 1 ) ENDIF IF ( nI == 0 ) RETURN( FNMathGetAckermannRecursiveI( mI - 1, 1 ) ) ENDIF RETURN( FNMathGetAckermannRecursiveI( mI - 1, FNMathGetAckermannRecursiveI( mI, nI - 1 ) ) )END PROC Main()STRING s1[255] = "2"STRING s2[255] = "3"IF ( NOT ( Ask( "math: get: ackermann: recursive: m = ", s1, _EDIT_HISTORY_ ) ) AND ( Length( s1 ) > 0 ) ) RETURN() ENDIFIF ( NOT ( Ask( "math: get: ackermann: recursive: n = ", s2, _EDIT_HISTORY_ ) ) AND ( Length( s2 ) > 0 ) ) RETURN() ENDIF Message( FNMathGetAckermannRecursiveI( Val( s1 ), Val( s2 ) ) ) // gives e.g. 9END ## TXR Translation of: Scheme with memoization. (defmacro defmemofun (name (. args) . body) (let ((hash (gensym "hash-")) (argl (gensym "args-")) (hent (gensym "hent-")) (uniq (copy-str "uniq"))) ^(let ((,hash (hash :equal-based))) (defun ,name (,*args) (let* ((,argl (list ,*args)) (,hent (inhash ,hash ,argl ,uniq))) (if (eq (cdr ,hent) ,uniq) (set (cdr ,hent) (block ,name (progn ,*body))) (cdr ,hent))))))) (defmemofun ack (m n) (cond ((= m 0) (+ n 1)) ((= n 0) (ack (- m 1) 1)) (t (ack (- m 1) (ack m (- n 1)))))) (each ((i (range 0 3))) (each ((j (range 0 4))) (format t "ack(~a, ~a) = ~a\n" i j (ack i j)))) 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 ## UNIX Shell Works with: Bash ack() { local m=1 local n=2 if [ m -eq 0 ]; then echo -n ((n+1)) elif [ n -eq 0 ]; then ack ((m-1)) 1 else ack ((m-1)) (ack m ((n-1))) fi} Example: for ((m=0;m<=3;m++)); do for ((n=0;n<=6;n++)); do ack m n echo -n " " done echodone 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 ## Ursala Anonymous recursion is the usual way of doing things like this. #import std#import nat ackermann = ~&al^?\[email protected] ~&ar?( ^R/~&f ^/[email protected] ^|R/~& ^|/~& predecessor, ^|R/~& ~&\1+ [email protected]) test program for the first 4 by 7 numbers: #cast %nLL test = block7 ackermann*K0 iota~~/4 7 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>> ## V Translation of: Joy [ack [ [pop zero?] [popd succ] [zero?] [pop pred 1 ack] [true] [[dup pred swap] dip pred ack ack ] ] when]. using destructuring view [ack [ [pop zero?] [ [m n : [n succ]] view i] [zero?] [ [m n : [m pred 1 ack]] view i] [true] [ [m n : [m pred m n pred ack ack]] view i] ] when]. ## Vala uint64 ackermann(uint64 m, uint64 n) { if (m == 0) return n + 1; if (n == 0) return ackermann(m - 1, 1); return ackermann(m - 1, ackermann(m, n - 1));} void main () { for (uint64 m = 0; m < 4; ++m) { for (uint64 n = 0; n < 10; ++n) { print(@"A(m,n) = (ackermann(m,n))\n"); } }} 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(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  ## VBA Private Function Ackermann_function(m As Variant, n As Variant) As Variant Dim result As Variant Debug.Assert m >= 0 Debug.Assert n >= 0 If m = 0 Then result = CDec(n + 1) Else If n = 0 Then result = Ackermann_function(m - 1, 1) Else result = Ackermann_function(m - 1, Ackermann_function(m, n - 1)) End If End If Ackermann_function = CDec(result)End FunctionPublic Sub main() Debug.Print " n=", For j = 0 To 7 Debug.Print j, Next j Debug.Print For i = 0 To 3 Debug.Print "m=" & i, For j = 0 To 7 Debug.Print Ackermann_function(i, j), Next j Debug.Print Next iEnd Sub Output:  n= 0 1 2 3 4 5 6 7 m=0 1 2 3 4 5 6 7 8 m=1 2 3 4 5 6 7 8 9 m=2 3 5 7 9 11 13 15 17 m=3 5 13 29 61 125 253 509 1021  ## VBScript Based on BASIC version. Uncomment all the lines referring to depth and see just how deep the recursion goes. Implementation option explicit'~ dim depthfunction ack(m, n) '~ wscript.stdout.write depth & " " if m = 0 then '~ depth = depth + 1 ack = n + 1 '~ depth = depth - 1 elseif m > 0 and n = 0 then '~ depth = depth + 1 ack = ack(m - 1, 1) '~ depth = depth - 1 '~ elseif m > 0 and n > 0 then else '~ depth = depth + 1 ack = ack(m - 1, ack(m, n - 1)) '~ depth = depth - 1 end if end function Invocation wscript.echo ack( 1, 10 )'~ depth = 0wscript.echo ack( 2, 1 )'~ depth = 0wscript.echo ack( 4, 4 ) Output: 12 5 C:\foo\ackermann.vbs(16, 3) Microsoft VBScript runtime error: Out of stack space: 'ack'  ## Visual Basic Translation of: Rexx Works with: Visual Basic version VB6 Standard  Option ExplicitDim calls As LongSub main() Const maxi = 4 Const maxj = 9 Dim i As Long, j As Long For i = 0 To maxi For j = 0 To maxj Call print_acker(i, j) Next j Next iEnd Sub 'mainSub print_acker(m As Long, n As Long) calls = 0 Debug.Print "ackermann("; m; ","; n; ")="; Debug.Print ackermann(m, n), "calls="; callsEnd Sub 'print_ackerFunction ackermann(m As Long, n As Long) As Long calls = calls + 1 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 If End IfEnd Function 'ackermann 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( 0 , 7 )= 8 calls= 1 ackermann( 0 , 8 )= 9 calls= 1 ackermann( 0 , 9 )= 10 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( 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( 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 ackermann( 3 , 9 )= 4093 calls= 11164370 ackermann( 4 , 0 )= 13 calls= 107 ackermann( 4 , 1 )= out of stack space ## Vlang fn ackermann(m int, n int ) int { if m == 0 { return n + 1 } else if n == 0 { return ackermann(m - 1, 1) } return ackermann(m - 1, ackermann(m, n - 1) )} fn main() { for m := 0; m <= 4; m++ { for n := 0; n < ( 6 - m ); n++ { println('Ackermann(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(0, 5) = 6 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(3, 0) = 5 Ackermann(3, 1) = 13 Ackermann(3, 2) = 29 Ackermann(4, 0) = 13 Ackermann(4, 1) = 65533  ## Wart def (ackermann m n) (if m=0 n+1 n=0 (ackermann m-1 1) :else (ackermann m-1 (ackermann m n-1))) ## WDTE let memo a m n => true { == m 0 => + n 1; == n 0 => a (- m 1) 1; true => a (- m 1) (a m (- n 1));}; ## Wren // To use recursion definition and declaration must be on separate linesvar Ackermann Ackermann = Fn.new {|m, n| if (m == 0) return n + 1 if (n == 0) return Ackermann.call(m - 1, 1) return Ackermann.call(m - 1, Ackermann.call(m, n - 1))} var pairs = [ [1, 3], [2, 3], [3, 3], [1, 5], [2, 5], [3, 5] ]for (pair in pairs) { var p1 = pair[0] var p2 = pair[1] System.print("A[%(p1), %(p2)] = %(Ackermann.call(p1, p2))")} Output: A[1, 3] = 5 A[2, 3] = 9 A[3, 3] = 61 A[1, 5] = 7 A[2, 5] = 13 A[3, 5] = 253  ## X86 Assembly Works with: nasm Works with: windows  section .text global _main_main: mov eax, 3 ;m mov ebx, 4 ;n call ack ;returns number in ebx ret ack: cmp eax, 0 je M0 ;if M == 0 cmp ebx, 0 je N0 ;if N == 0 dec ebx ;else N-1 push eax ;save M call ack1 ;ack(m,n) -> returned in ebx so no further instructions needed pop eax ;restore M dec eax ;M - 1 call ack1 ;return ack(m-1,ack(m,n-1)) ret M0: inc ebx ;return n + 1 ret N0: dec eax inc ebx ;ebx always 0: inc -> ebx = 1 call ack1 ;return ack(M-1,1) ret  ## XLISP (defun ackermann (m n) (cond ((= m 0) (+ n 1)) ((= n 0) (ackermann (- m 1) 1)) (t (ackermann (- m 1) (ackermann m (- n 1)))))) Test it: (print (ackermann 3 9)) Output (after a very perceptible pause): 4093 That worked well. Test it again: (print (ackermann 4 1)) Output (after another pause): Abort: control stack overflow happened in: #<Code ACKERMANN> ## XPL0 include c:\cxpl\codes; func Ackermann(M, N);int 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));]; \Ackermann int M, N;[for M:= 0 to 3 do [for N:= 0 to 7 do [IntOut(0, Ackermann(M, N)); ChOut(0,9\tab$$];    CrLf(0);    ];]

Recursion overflows the stack if either M or N is extended by a single count.

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


## XSLT

The following named template calculates the Ackermann function:

   <xsl:template name="ackermann">    <xsl:param name="m"/>    <xsl:param name="n"/>     <xsl:choose>      <xsl:when test="$m = 0"> <xsl:value-of select="$n+1"/>      </xsl:when>      <xsl:when test="$n = 0"> <xsl:call-template name="ackermann"> <xsl:with-param name="m" select="$m - 1"/>          <xsl:with-param name="n" select="'1'"/>        </xsl:call-template>      </xsl:when>      <xsl:otherwise>        <xsl:variable name="p">          <xsl:call-template name="ackermann">            <xsl:with-param name="m" select="$m"/> <xsl:with-param name="n" select="$n - 1"/>          </xsl:call-template>        </xsl:variable>         <xsl:call-template name="ackermann">          <xsl:with-param name="m" select="$m - 1"/> <xsl:with-param name="n" select="$p"/>        </xsl:call-template>      </xsl:otherwise>    </xsl:choose>  </xsl:template> 

Here it is as part of a template

 <?xml version="1.0" encoding="UTF-8"?><xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="1.0">   <xsl:template match="arguments">      <xsl:for-each select="args">        <div>          <xsl:value-of select="m"/>, <xsl:value-of select="n"/>:          <xsl:call-template name="ackermann">            <xsl:with-param name="m" select="m"/>            <xsl:with-param name="n" select="n"/>          </xsl:call-template>        </div>      </xsl:for-each>  </xsl:template>   <xsl:template name="ackermann">    <xsl:param name="m"/>    <xsl:param name="n"/>     <xsl:choose>      <xsl:when test="$m = 0"> <xsl:value-of select="$n+1"/>      </xsl:when>      <xsl:when test="$n = 0"> <xsl:call-template name="ackermann"> <xsl:with-param name="m" select="$m - 1"/>          <xsl:with-param name="n" select="'1'"/>        </xsl:call-template>      </xsl:when>      <xsl:otherwise>        <xsl:variable name="p">          <xsl:call-template name="ackermann">            <xsl:with-param name="m" select="$m"/> <xsl:with-param name="n" select="$n - 1"/>          </xsl:call-template>        </xsl:variable>         <xsl:call-template name="ackermann">          <xsl:with-param name="m" select="$m - 1"/> <xsl:with-param name="n" select="$p"/>        </xsl:call-template>      </xsl:otherwise>    </xsl:choose>  </xsl:template></xsl:stylesheet> 

Which will transform this input

 <?xml version="1.0" ?><?xml-stylesheet type="text/xsl" href="ackermann.xslt"?><arguments>  <args>    <m>0</m>    <n>0</n>  </args>  <args>    <m>0</m>    <n>1</n>  </args>  <args>    <m>0</m>    <n>2</n>  </args>  <args>    <m>0</m>    <n>3</n>  </args>  <args>    <m>0</m>    <n>4</n>  </args>  <args>    <m>0</m>    <n>5</n>  </args>  <args>    <m>0</m>    <n>6</n>  </args>  <args>    <m>0</m>    <n>7</n>  </args>  <args>    <m>0</m>    <n>8</n>  </args>  <args>    <m>1</m>    <n>0</n>  </args>  <args>    <m>1</m>    <n>1</n>  </args>  <args>    <m>1</m>    <n>2</n>  </args>  <args>    <m>1</m>    <n>3</n>  </args>  <args>    <m>1</m>    <n>4</n>  </args>  <args>    <m>1</m>    <n>5</n>  </args>  <args>    <m>1</m>    <n>6</n>  </args>  <args>    <m>1</m>    <n>7</n>  </args>  <args>    <m>1</m>    <n>8</n>  </args>  <args>    <m>2</m>    <n>0</n>  </args>  <args>    <m>2</m>    <n>1</n>  </args>  <args>    <m>2</m>    <n>2</n>  </args>  <args>    <m>2</m>    <n>3</n>  </args>  <args>    <m>2</m>    <n>4</n>  </args>  <args>    <m>2</m>    <n>5</n>  </args>  <args>    <m>2</m>    <n>6</n>  </args>  <args>    <m>2</m>    <n>7</n>  </args>  <args>    <m>2</m>    <n>8</n>  </args>  <args>    <m>3</m>    <n>0</n>  </args>  <args>    <m>3</m>    <n>1</n>  </args>  <args>    <m>3</m>    <n>2</n>  </args>  <args>    <m>3</m>    <n>3</n>  </args>  <args>    <m>3</m>    <n>4</n>  </args>  <args>    <m>3</m>    <n>5</n>  </args>  <args>    <m>3</m>    <n>6</n>  </args>  <args>    <m>3</m>    <n>7</n>  </args>  <args>    <m>3</m>    <n>8</n>  </args></arguments> 

into this output

0, 0: 1
0, 1: 2
0, 2: 3
0, 3: 4
0, 4: 5
0, 5: 6
0, 6: 7
0, 7: 8
0, 8: 9
1, 0: 2
1, 1: 3
1, 2: 4
1, 3: 5
1, 4: 6
1, 5: 7
1, 6: 8
1, 7: 9
1, 8: 10
2, 0: 3
2, 1: 5
2, 2: 7
2, 3: 9
2, 4: 11
2, 5: 13
2, 6: 15
2, 7: 17
2, 8: 19
3, 0: 5
3, 1: 13
3, 2: 29
3, 3: 61
3, 4: 125
3, 5: 253
3, 6: 509
3, 7: 1021
3, 8: 2045


## Yabasic

sub ack(M,N)    if M = 0 return N + 1    if N = 0 return ack(M-1,1)    return ack(M-1,ack(M, N-1))end sub print ack(3, 4) 

What smart code can get. Fast as lightning!

Translation of: Phix
sub ack(m, 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 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 ifend sub sub Ackermann()    local i, j    for i=0 to 3        for j=0 to 10            print ack(i,j) using "#####";        next        print    next    print "ack(4,1) ";: print ack(4,1) using "#####"end sub Ackermann()

## Yorick

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

Example invocation:

for(m = 0; m <= 3; m++) {    for(n = 0; n <= 6; n++)        write, format="%d ", ack(m, n);    write, "";}
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

## Z80 Assembly

This function does 16-bit math. Sjasmplus syntax, CP/M executable.

    OPT --syntax=abf : OUTPUT "ackerman.com"    ORG $100 jr demo_start ;--------------------------------------------------------------------------------------------------------------------; entry: ackermann_fn; input: bc = m, hl = n; output: hl = A(m,n) (16bit only)ackermann_fn.inc_n: inc hlackermann_fn: inc hl ld a,c or b ret z ; m == 0 -> return n+1 ; m > 0 case ; bc = m, hl = n+1 dec bc dec hl ; m-1, n restored ld a,l or h jr z,.inc_n ; n == 0 -> return A(m-1, 1) ; m > 0, n > 0 ; bc = m-1, hl = n push bc inc bc dec hl call ackermann_fn ; n = A(m, n-1) pop bc jp ackermann_fn ; return A(m-1,A(m, n-1)) ;--------------------------------------------------------------------------------------------------------------------; helper functions for demo printing 4x9 tableprint_str: push bc push hl ld c,9.call_cpm: call 5 pop hl pop bc retprint_hl: ld b,' ' ld e,b call print_char ld de,-10000 call extract_digit ld de,-1000 call extract_digit ld de,-100 call extract_digit ld de,-10 call extract_digit ld a,lprint_digit: ld b,'0' add a,b ld e,aprint_char: push bc push hl ld c,2 jr print_str.call_cpmextract_digit: ld a,-1.digit_loop: inc a add hl,de jr c,.digit_loop sbc hl,de or a jr nz,print_digit ld e,b jr print_char ;--------------------------------------------------------------------------------------------------------------------demo_start: ; do m: [0,4) cross n: [0,9) table ld bc,0.loop_m: ld hl,0 ; bc = m, hl = n = 0 ld de,txt_m_is call print_str ld a,c or '0' ld e,a call print_char ld e,':' call print_char.loop_n: push bc push hl call ackermann_fn call print_hl pop hl pop bc inc hl ld a,l cp 9 jr c,.loop_n ld de,crlf call print_str inc bc ld a,c cp 4 jr c,.loop_m rst 0 ; return to CP/M txt_m_is: db "m=$"crlf:       db  10,13,'\$'
Output:
m=0:     1     2     3     4     5     6     7     8     9
m=1:     2     3     4     5     6     7     8     9    10
m=2:     3     5     7     9    11    13    15    17    19
m=3:     5    13    29    61   125   253   509  1021  2045


## ZED

Source -> http://ideone.com/53FzPA Compiled -> http://ideone.com/OlS7zL

(A) m ncomment:(=) m 0(add1) n (A) m ncomment:(=) n 0(A) (sub1) m 1 (A) m ncomment:#true(A) (sub1) m (A) m (sub1) n (add1) ncomment:#true(003) "+" n 1 (sub1) ncomment:#true(003) "-" n 1 (=) n1 n2comment:#true(003) "=" n1 n2

## Zig

pub fn ack(m: u64, n: u64) u64 {    if (m == 0) return n + 1;    if (n == 0) return ack(m - 1, 1);    return ack(m - 1, ack(m, n - 1));} pub fn main() !void {    const stdout = @import("std").io.getStdOut().writer();     var m: u8 = 0;    while (m <= 3) : (m += 1) {        var n: u8 = 0;        while (n <= 8) : (n += 1)            try stdout.print("{d:>8}", .{ack(m, n)});        try stdout.print("\n", .{});    }}
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

## ZX Spectrum Basic

Translation of: BASIC256
10 DIM s(2000,3)20 LET s(1,1)=3: REM M30 LET s(1,2)=7: REM N40 LET lev=150 GO SUB 10060 PRINT "A(";s(1,1);",";s(1,2);") = ";s(1,3)70 STOP 100 IF s(lev,1)=0 THEN LET s(lev,3)=s(lev,2)+1: RETURN 110 IF s(lev,2)=0 THEN LET lev=lev+1: LET s(lev,1)=s(lev-1,1)-1: LET s(lev,2)=1: GO SUB 100: LET s(lev-1,3)=s(lev,3): LET lev=lev-1: RETURN 120 LET lev=lev+1130 LET s(lev,1)=s(lev-1,1)140 LET s(lev,2)=s(lev-1,2)-1150 GO SUB 100160 LET s(lev,1)=s(lev-1,1)-1170 LET s(lev,2)=s(lev,3)180 GO SUB 100190 LET s(lev-1,3)=s(lev,3)200 LET lev=lev-1210 RETURN 
Output:
A(3,7) = 1021`