Movatterモバイル変換

[0]ホーム
URL:

Jump to content
Rosetta Code
Search

Ackermann function

From Rosetta Code
Task
Ackermann function
You are encouraged tosolve this task according to the task description, using any language you may know.

TheAckermann function is a classic example of a recursive function, notable especially because it is not aprimitive recursive function. It grows very quickly in value, as does the size of its call tree.


The Ackermann function is usually defined as follows:

A(m,n)={n+1if m=0A(m−1,1)if m>0 and n=0A(m−1,A(m,n−1))if m>0 and n>0.{\displaystyle {\displaystyle A(m,n)={\begin{cases}n+1&{\mbox{if }}m=0\\A(m-1,1)&{\mbox{if }}m>0{\mbox{ and }}n=0\\A(m-1,A(m,n-1))&{\mbox{if }}m>0{\mbox{ and }}n>0.\end{cases}}}}


Its arguments are never negative and it always terminates.


Task

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


See also



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

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) =            1Ackermann( 0, 1) =            2Ackermann( 0, 2) =            3Ackermann( 0, 3) =            4Ackermann( 0, 4) =            5Ackermann( 0, 5) =            6Ackermann( 0, 6) =            7Ackermann( 0, 7) =            8Ackermann( 0, 8) =            9Ackermann( 1, 0) =            2Ackermann( 1, 1) =            3Ackermann( 1, 2) =            4Ackermann( 1, 3) =            5Ackermann( 1, 4) =            6Ackermann( 1, 5) =            7Ackermann( 1, 6) =            8Ackermann( 1, 7) =            9Ackermann( 1, 8) =           10Ackermann( 2, 0) =            3Ackermann( 2, 1) =            5Ackermann( 2, 2) =            7Ackermann( 2, 3) =            9Ackermann( 2, 4) =           11Ackermann( 2, 5) =           13Ackermann( 2, 6) =           15Ackermann( 2, 7) =           17Ackermann( 2, 8) =           19Ackermann( 3, 0) =            5Ackermann( 3, 1) =           13Ackermann( 3, 2) =           29Ackermann( 3, 3) =           61Ackermann( 3, 4) =          125Ackermann( 3, 5) =          253Ackermann( 3, 6) =          509Ackermann( 3, 7) =         1021Ackermann( 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;_LVOOpenLibraryequ-552_LVOCloseLibraryequ-414_LVOVPrintfequ-954mequ3; Nr of iterations for the main loop.nequ5; 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=4startmove.lexecBase,a6leadosName,a1moveq#36,d0jsr_LVOOpenLibrary(a6)move.ld0,dosBasebeqexitmove.ldosBase,a6leaprintfArgs,a2clr.ld3; m.loopnclr.ld4; n.loopmbsrackermannmove.ld3,0(a2)move.ld4,4(a2)move.ld5,8(a2)move.l#outString,d1move.la2,d2jsr_LVOVPrintf(a6)addq.l#1,d4cmp.l#n,d4ble.loopmaddq.l#1,d3cmp.l#m,d3ble.loopnexitmove.lexecBase,a6move.ldosBase,a1jsr_LVOCloseLibrary(a6)rts;; ackermann function;; in:;; d3 = m; d4 = n;; out:;; d5 = ans;ackermannmove.ld3,-(sp)move.ld4,-(sp)tst.ld3bne.l1move.ld4,d5addq.l#1,d5bra.return.l1tst.ld4bne.l2subq.l#1,d3moveq#1,d4bsrackermannbra.return.l2subq.l#1,d4bsrackermannmove.ld5,d4subq.l#1,d3bsrackermann.returnmove.l(sp)+,d4move.l(sp)+,d3rts;; variables;dosBasedc.l0printfArgsdcb.l3;; strings;dosNamedc.b"dos.library",0outStringdc.b"ackermann(%ld,%ld)is:%ld",10,0

8080 Assembly

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

org100hjmpdemo;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;ACK(M,N); DE=M, HL=N, return value in HL.ack:mova,d; M=0?oraejnzackminxh; If so, N+1.retackm:mova,h; N=0?oraljnzackmnlxih,1; If so, N=1,dcxd; N-=1,jmpack; A(M,N) - tail recursionackmn:pushd; M>0 and N>0: store M on the stackdcxh; N-=1callack; N = ACK(M,N-1)popd; Restore previous Mdcxd; M-=1jmpack; A(M,N) - tail recursion;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;Print table of ack(m,n)MMAX:equ4; Size of table to print. Note that math is done inNMAX:equ9; 16 bits. demo:lhld6; Put stack pointer at top of available memorysphllxib,0; let B,C hold 8-bit M and N.acknum:xraa; Set high bit of M and N to zeromovd,a; DE = B (M)move,bmovh,a; HL = C (N)movl,ccallack; HL = ack(DE,HL)callprhl; Print the numberinrc; N += 1mvia,NMAX; Time for next line?cmpcjnzacknum; If not, print next numberpushb; Otherwise, save BCmvic,9; Print newlinelxid,nlcall5popb; Restore BCmvic,0; Set N to 0inrb; M += 1mvia,MMAX; Time to stop?cmpbjnzacknum; If not, print next numberrst0;;;Print HL as ASCII number.prhl:pushh; Save all registerspushdpushblxib,pnum; Store pointer to num string on stackpushblxib,-10; Divisorprdgt:lxid,-1prdgtl:inxd; Divide by 10 through trial subtractiondadbjcprdgtlmvia,'0'+10addl; L = remainder - 10poph; Get pointer from stackdcxh; Store digitmovm,apushh; Put pointer back on stackxchg; Put quotient in HLmova,h; Check if zero oraljnzprdgt; If not, next digitpopd; Get pointer and put in DEmvic,9; CP/M print stringcall5popb; Restore registers popdpophretdb'*****'; Placeholder for numberpnum:db9,'$'nl:db13,10,'$'
Output:
1       2       3       4       5       6       7       8       92       3       4       5       6       7       8       9       103       5       7       9       11      13      15      17      195       13      29      61      125     253     509     1021    2045

8086 Assembly

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

cpu8086bits16org100hsection.textjmpdemo;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;ACK(M,N); DX=M, AX=N, return value in AX.ack:anddx,dx; N=0?jnz.mincax; If so, return N+1ret.m:andax,ax; M=0?jnz.mnmovax,1; If so, N=1,decdx; M -= 1jmpack; ACK(M-1,1) - tail recursion.mn:pushdx; Keep M on the stackdecax; N-=1callack; N = ACK(M,N-1)popdx; Restore Mdecdx; M -= 1jmpack; ACK(M-1,ACK(M,N-1)) - tail recursion;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;Print table of ack(m,n)MMAX:equ4; Size of table to print. Noe that math is doneNMAX:equ9; in 16 bits.demo:xorsi,si; Let SI hold M,xordi,di; and DI hold N.acknum:movdx,si; Calculate ack(M,N)movax,dicallackcallprax; Print numberincdi; N += 1cmpdi,NMAX; Row done?jbacknum; If not, print next number on rowxordi,di; Otherwise, N=0,incsi; M += 1movdx,nl; Print newlinecallprstrcmpsi,MMAX; Done?jbacknum; If not, start next rowret; Otherwise, stop.;;;Print AX as ASCII number.prax:movbx,pnum; Pointer to number stringmovcx,10; Divisor.dgt:xordx,dx; Divide AX by tendivcxadddl,'0'; DX holds remainder - add ASCII 0decbx; Move pointer backwardsmov[bx],dl; Save digit in stringandax,ax; Are we done yet?jnz.dgt; If not, next digitmovdx,bx; Tell DOS to print the stringprstr:movah,9int21hretsection.datadb'*****'; Placeholder for ASCII numberpnum:db9,'$'nl:db13,10,'$'
Output:
1       2       3       4       5       6       7       8       92       3       4       5       6       7       8       9       103       5       7       9       11      13      15      17      195       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!100000stack-size\ This is where memoized values are stored:{}var,dict\ Simple accessor words:dict!\ "key" val --dict@-rotm:!drop;:dict@\ "key" -- valdict@swapm:@nip;defer:ack1\ We just jam the string representation of the two numbers together for a key::makeKey\ m n -- m n key2dup>sswap>ss:+;:ack2\ m n -- AmakeKeydupdict@null?if\ can't find key in dict\ m n key nulldrop\ m n key-rot\ key m nack1\ key Atuck\ A key Adict!\ Aelse\ found value\ m n key value>rdrop2dropr>then;:ack\ m n -- Aovernotifnipn:1+elsedupnotifdropn:1-1ack2elseoverswapn:1-ack2swapn:1-swapack2thenthen;'ackisack1:ackOf\ m n --2dup"Ack(".swap.","..")=".ack.cr;00ackOf04ackOf10ackOf11ackOf21ackOf22ackOf31ackOf33ackOf40ackOf\ this last requires a very large data stack.  So start 8th with a parameter '-k 100000'41ackOfbye
The output:
Ack(0, 0) = 1Ack(0, 4) = 5Ack(1, 0) = 2Ack(1, 1) = 3Ack(2, 1) = 5Ack(2, 2) = 7Ack(3, 1) = 13Ack(3, 3) = 61Ack(4, 0) = 13Ack(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  : 1Result for 0  1  : 2Result for 0  2  : 3Result for 0  3  : 4Result for 0  4  : 5Result for 0  5  : 6Result for 0  6  : 7Result for 0  7  : 8Result for 0  8  : 9Result for 0  9  : 10Result for 1  0  : 2Result for 1  1  : 3Result for 1  2  : 4Result for 1  3  : 5Result for 1  4  : 6Result for 1  5  : 7Result for 1  6  : 8Result for 1  7  : 9Result for 1  8  : 10Result for 1  9  : 11Result for 2  0  : 3Result for 2  1  : 5Result for 2  2  : 7Result for 2  3  : 9Result for 2  4  : 11Result for 2  5  : 13Result for 2  6  : 15Result for 2  7  : 17Result for 2  8  : 19Result for 2  9  : 21Result for 3  0  : 5Result for 3  1  : 13Result for 3  2  : 29Result for 3  3  : 61Result for 3  4  : 125Result for 3  5  : 253Result for 3  6  : 509Result for 3  7  : 1021Result for 3  8  : 2045Result for 3  9  : 4093

ABAP

REPORTzhuberv_ackermann.CLASSzcl_ackermannDEFINITION.PUBLIC SECTION.CLASS-METHODSackermannIMPORTINGmTYPEinTYPEiRETURNINGvalue(v)TYPEi.ENDCLASS."zcl_ackermann DEFINITIONCLASSzcl_ackermannIMPLEMENTATION.METHOD:ackermann.DATA:lv_new_mTYPEi,lv_new_nTYPEi.IFm=0.v=n+1.ELSEIFm>0ANDn=0.lv_new_m=m-1.lv_new_n=1.v=ackermann(m=lv_new_mn=lv_new_n).ELSEIFm>0ANDn>0.lv_new_m=m-1.lv_new_n=n-1.lv_new_n=ackermann(m=mn=lv_new_n).v=ackermann(m=lv_new_mn=lv_new_n).ENDIF.ENDMETHOD."ackermannENDCLASS."zcl_ackermann IMPLEMENTATIONPARAMETERS:pa_mTYPEi,pa_nTYPEi.DATA:lv_resultTYPEi.START-OF-SELECTION.lv_result=zcl_ackermann=>ackermann(m=pa_mn=pa_n).WRITE:/lv_result.

ABC

HOW TO RETURN m ack n:    SELECT:        m=0: RETURN n+1        m>0 AND n=0: RETURN (m-1) ack 1        m>0 AND n>0: RETURN (m-1) ack (m ack (n-1))FOR m IN {0..3}:    FOR n IN {0..8}:        WRITE (m ack n)>>6    WRITE /
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

Acornsoft Lisp

Translation of:Common Lisp
(defunack(mn)(cond((zeropm)(add1n))((zeropn)(ack(sub1m)1))(t(ack(sub1m)(ackm(sub1n))))))
Output:
Evaluate : (ack 3 5)Value is : 253

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==+1RETURNBYTE 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:

Screenshot from Atari 8-bit computer

Ack(0,0)=1Ack(0,1)=2Ack(0,2)=3Ack(0,3)=4Ack(0,4)=5Ack(1,0)=2Ack(1,1)=3Ack(1,2)=4Ack(1,3)=5Ack(1,4)=6Ack(2,0)=3Ack(2,1)=5Ack(2,2)=7Ack(2,3)=9Ack(2,4)=11Ack(3,0)=5Ack(3,1)=13Ack(3,2)=29Ack(3,3)=61Ack(3,4)=125

ActionScript

publicfunctionackermann(m:uint,n:uint):uint{if(m==0){returnn+1;}if(n==0){returnackermann(m-1,1);}returnackermann(m-1,ackermann(m,n-1));}

Ada

withAda.Text_IO;useAda.Text_IO;procedureTest_AckermannisfunctionAckermann(M,N:Natural)returnNaturalisbeginifM=0thenreturnN+1;elsifN=0thenreturnAckermann(M-1,1);elsereturnAckermann(M-1,Ackermann(M,N-1));endif;endAckermann;beginforMin0..3loopforNin0..6loopPut(Natural'Image(Ackermann(M,N)));endloop;New_Line;endloop;endTest_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.6.3
Library:agda-stdlib v1.7
moduleAckermannwhereopenimportData.Natusing(ℕ;zero;suc;_+_)ack:ℕ→ℕ→ℕackzeron=n+1ack(sucm)zero=ackm1ack(sucm)(sucn)=ackm(ack(sucm)n)openimportAgda.Builtin.IOusing(IO)openimportAgda.Builtin.Unitusing(⊤)openimportAgda.Builtin.Stringusing(String)openimportData.Nat.Showusing(show)postulateputStrLn:String→IO⊤{-# FOREIGN GHC import qualified Data.Text as T #-}{-# COMPILE GHC putStrLn = putStrLn . T.unpack #-}main:IO⊤main=putStrLn(show(ack39))-- Output:-- 4093

The Unicode characters can be entered in Emacs Agda as follows:

  • ℕ : \bN
  • → : \to
  • ⊤ : \top

Running in Bash:

agda--compileAckermann.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

Translation of:Ada
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
ack←{0=⍺:1+⍵⋄0=⍵:(⍺-1)∇1⋄(⍺-1)∇⍺∇⍵-1}

A version that takes the arguments together in a single array:

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

AppleScript

onackermann(m,n)ifmis equalto0thenreturnn+1ifnis equalto0thenreturnackermann(m-1,1)returnackermann(m-1,ackermann(m,n-1))endackermann

Argile

Works with:Argile version 1.0.0
use stdfor 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))

ArkScript

Works with:ArkScript version 3.x
(let ackermann (fun (m n) {  (if (> m 0)    (if (= 0 n)      (ackermann (- m 1) 1)      (ackermann (- m 1) (ackermann m (- n 1))))    (+ 1 n)) }))(assert (= 509 (ackermann 3 6)) "(ackermann 3 6) == 509")

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            : 1Result for 0            1            : 2Result for 0            2            : 3Result for 0            3            : 4Result for 0            4            : 5Result for 0            5            : 6Result for 0            6            : 7Result for 0            7            : 8Result for 0            8            : 9Result for 0            9            : 10Result for 1            0            : 2Result for 1            1            : 3Result for 1            2            : 4Result for 1            3            : 5Result for 1            4            : 6Result for 1            5            : 7Result for 1            6            : 8Result for 1            7            : 9Result for 1            8            : 10Result for 1            9            : 11Result for 2            0            : 3Result for 2            1            : 5Result for 2            2            : 7Result for 2            3            : 9Result for 2            4            : 11Result for 2            5            : 13Result for 2            6            : 15Result for 2            7            : 17Result for 2            8            : 19Result for 2            9            : 21Result for 3            0            : 5Result for 3            1            : 13Result for 3            2            : 29Result for 3            3            : 61Result for 3            4            : 125Result for 3            5            : 253Result for 3            6            : 509Result for 3            7            : 1021Result for 3            8            : 2045Result for 3            9            : 4093

Arturo

ackermann:function[m,n][(m=0)?->n+1[(n=0)?->ackermannm-11->ackermannm-1ackermannmn-1]]loop0..3'a[loop0..4'b[print["ackermann"ab"=>"ackermannab]]]
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)ReturnA(m-1,1)ElseIf(m>0)&&(n>0)ReturnA(m-1,A(m,n-1))ElseIf(m=0)Returnn+1}; Example:MsgBox,%"A(1,2) = "A(1,2)

AutoIt

Classical version

FuncAckermann($m,$n)If($m=0)ThenReturn$n+1ElseIf($n=0)ThenReturnAckermann($m-1,1)ElsereturnAckermann($m-1,Ackermann($m,$n-1))EndIfEndIfEndFunc

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 wantFuncAckermann($m,$n)If($ackermann[$m][$n]<>0)ThenReturn$ackermann[$m][$n]ElseIf($m=0)Then$return=$n+1ElseIf($n=0)Then$return=Ackermann($m-1,1)Else$return=Ackermann($m-1,Ackermann($m,$n-1))EndIfEndIf$ackermann[$m][$n]=$returnReturn$returnEndIfEndFunc;==>Ackermann

AWK

functionackermann(m,n){if(m==0){returnn+1}if(n==0){returnackermann(m-1,1)}returnackermann(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 ) = 1A(0 1 ) = 2A(0 2 ) = 3A(0 3 ) = 4A(0 4 ) = 5A(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

Ballerina

importballerina/io;functionackermann(intm,intn)returnsint{ifm==0{returnn+1;}ifn==0{returnackermann(m-1,1);}returnackermann(m-1,ackermann(m,n-1));}publicfunctionmain(){int[][]pairs=[[1,3],[2,3],[3,3],[1,5],[2,5],[3,5]];foreachvarpinpairs{io:println(`A[${p[0]}, ${p[1]}] = ${ackermann(p[0], p[1])}`);}}
Output:
A[1, 3] = 5A[2, 3] = 9A[3, 3] = 61A[1, 5] = 7A[2, 5] = 13A[3, 5] = 253

BASIC

Applesoft BASIC

Works with:Chipmunk Basic
100DIMR%(2900),M(2900),N(2900)110FORM=0TO3120FORN=0TO4130GOSUB200"ACKERMANN140PRINT"ACK("M","N") = "ACK150NEXTN,M160END200M(SP)=M210N(SP)=NREM A(M - 1, A(M, N - 1))220IFM>0ANDN>0THENN=N-1:R%(SP)=0:SP=SP+1:GOTO200REM A(M - 1, 1)230IFM>0THENM=M-1:N=1:R%(SP)=1:SP=SP+1:GOTO200REM N + 1240ACK=N+1REM RETURN250M=M(SP):N=N(SP):IFSP=0THENRETURN260FORSP=SP-1TO0STEP-1:IFR%(SP)THENM=M(SP):N=N(SP):NEXTSP:SP=0:RETURN270M=M-1:N=ACK:R%(SP)=1:SP=SP+1:GOTO200

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]endackermann:if stack[lev,0]=0 thenstack[lev,2] = stack[lev,1]+1returnend ifif stack[lev,1]=0 then lev = lev+1stack[lev,0] = stack[lev-1,0]-1stack[lev,1] = 1gosub ackermannstack[lev-1,2] = stack[lev,2]lev = lev-1returnend iflev = lev+1stack[lev,0] = stack[lev-1,0]stack[lev,1] = stack[lev-1,1]-1gosub ackermannstack[lev,0] = stack[lev-1,0]-1stack[lev,1] = stack[lev,2]gosub ackermannstack[lev-1,2] = stack[lev,2]lev = lev-1return
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 mendfunction 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 10 1 20 2 30 3 40 4 51 0 21 1 31 2 41 3 51 4 62 0 32 1 52 2 72 3 92 4 113 0 53 1 133 2 293 3 613 4 125

BBC BASIC

PRINTFNackermann(3,7)ENDDEFFNackermann(M%,N%)IFM%=0THEN=N%+1IFN%=0THEN=FNackermann(M%-1,1)=FNackermann(M%-1,FNackermann(M%,N%-1))

Chipmunk Basic

Works with:Chipmunk Basic version 3.6.4
100form=0to4110printusing"###";m;120forn=0to6130ifm=4andn=1thengoto160140printusing"######";ack(m,n);150nextn160print170nextm180end190suback(m,n)200ifm=0thenack=n+1210ifm>0andn=0thenack=ack(m-1,1)220ifm>0andn>0thenack=ack(m-1,ack(m,n-1))230endsub

True BASIC

FUNCTIONack(m,n)IFm=0THENLETack=n+1IFm>0ANDn=0THENLETack=ack(m-1,1)IFm>0ANDn>0THENLETack=ack(m-1,ack(m,n-1))ENDFUNCTIONFORm=0TO4PRINTUSING"###":m;FORn=0TO8!A(4,1)ORhigherwillRUNOUTofstackmemory(default1M)!changen=1TOn=2TOcalculateA(4,2),increasestack!IFm=4ANDn=1THENEXITFORPRINTUSING"######":ack(m,n);NEXTnPRINTNEXTmEND

QuickBasic

Works with:QuickBasic version 4.5

BASIC runs out of stack space very quickly. The callack(3, 4) gives a stack error.

DECLAREFUNCTIONack!(m!,n!)FUNCTIONack(m!,n!)IFm=0THENack=n+1IFm>0ANDn=0THENack=ack(m-1,1)ENDIFIFm>0ANDn>0THENack=ack(m-1,ack(m,n-1))ENDIFENDFUNCTION

Batch File

Had trouble with this, so called in the gurus atStackOverflow. Thanks to Patrick Cuff for pointing out where I was going wrong.

::Ackermann.cmd@echo offsetdepth=0:ackif%1==0gotom0if%2==0goton0:elseset/an=%2-1set/adepth+=1call:ack%1%n%sett=%errorlevel%set/adepth-=1set/am=%1-1set/adepth+=1call:ack%m%%t%sett=%errorlevel%set/adepth-=1if%depth%==0(exit%t%)else(exit /b%t%):m0set/an=%2+1if%depth%==0(exit%n%)else(exit /b%n%):n0set/am=%1-1set/adepth+=1call:ack%m% 1sett=%errorlevel%set/adepth-=1if%depth%==0(exit%t%)else(exit /b%t%)

Because of theexit 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 4Ackermann(0, 4)=5D:\Documents and Settings\Bruce>ack 1 4Ackermann(1, 4)=6D:\Documents and Settings\Bruce>ack 2 4Ackermann(2, 4)=11D:\Documents and Settings\Bruce>ack 3 4Ackermann(3, 4)=125

bc

Requires abc that supports long names and theprint 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:

                         >M?f@h@gMf@h3yzp            if m>0 and n>0 => replace m,n with m-1,m,n-1                    >@h@g'b?1f@h@gM?f@hzp            if m>0 and n=0 => replace m,n with m-1,1_ii>Ag~1?~Lpz1~2h@g'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 (instructionJ) to the entry points of two distinct functions:

1st function_ii (input function) with entry point at (row,col) = (4,1)

2nd functionAg~1.... (Ackermann function) with entry point at (row,col) = (1,1)

Each block of1FJ or1fFJ in the code is a call of the Ackermann function itself.

Ag~1?Lp1~2@g'p?g?Pf1FJ                               Ackermann function.  if m=0 => run Ackermann function (m, n+1)      xI;    x@g'p??@Mf1fFJ                                               if m>0 and n=0 => run Ackermann (m-1,1)                 xM@~gM??f~f@f1FJ                                         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:

                             >Mf@Ph?@g@2h@Mf@Php     if m>4 and n>0 => replace m,n with m-1,m,n-1                   >~4~L#1~2hg'd?1f@hgM?f2h      p     if m>4 and n=0 => replace m,n with m-1,1                #            q      <                                                   /n+3 times  \                #X~4K#?2Fg?PPP>@B@M"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>Ag~1?~Lpz1~2h@gX'#?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:\<vp00:-1<\+<^>00p>:#^_$1+\:#^_$.

Befunge-98

Works with:CCBI version 2.1
r[1&&{0>vju>.@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.

Binary Lambda Calculus

The Ackermann function on Church numerals (arbitrary precision), as shown inhttps://github.com/tromp/AIT/blob/master/fast_growing_and_conjectures/ackermann.lam is the 63 bit BLCprogram

010000010110000001010111110101100010110000000011100101111011010

BQN

A←{A0‿n:n+1;Am‿0:A(m-1)‿1;Am‿n:A(m-1)‿(Am‿(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):1A$(3,13):65533A$(3,14):131069A$(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):65533AckFormula$(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

Bruijn

:import std/Combinator .:import std/Number/Unary U:import std/Math .# unary ackermannackermann-unary [0 [[U.inc 0 1 (+1u)]] U.inc]:test (ackermann-unary (+0u) (+0u)) ((+1u)):test (ackermann-unary (+3u) (+4u)) ((+125u))# ternary ackermann (lower space complexity)ackermann-ternary y [[[=?1 ++0 (=?0 (2 --1 (+1)) (2 --1 (2 1 --0)))]]]:test ((ackermann-ternary (+0) (+0)) =? (+1)) ([[1]]):test ((ackermann-ternary (+3) (+4)) =? (+125)) ([[1]])

C

Straightforward implementation per Ackermann definition:

#include<stdio.h>intackermann(intm,intn){if(!m)returnn+1;if(!n)returnackermann(m-1,1);returnackermann(m-1,ackermann(m,n-1));}intmain(){intm,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));return0;}
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) = 13A(4, 1) = 65533

Ackermann function makesa 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>intm_bits,n_bits;int*cache;intackermann(intm,intn){intidx,res;if(!m)returnn+1;if(n>=1<<n_bits){printf("%d, %d\n",m,n);idx=0;}else{idx=(m<<n_bits)+n;if(cache[idx])returncache[idx];}if(!n)res=ackermann(m-1,1);elseres=ackermann(m-1,ackermann(m,n-1));if(idx)cache[idx]=res;returnres;}intmain(){intm,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));return0;}
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) = 13A(4, 1) = 65533

Whee. Well, with some extra work, we calculatedone 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 spacequickly, unlike the first solution...

A couple of alternative approaches...

/* Thejaka Maldeniya */#include<conio.h>unsignedlonglongHR(unsignedintn,unsignedlonglonga,unsignedlonglongb){// (Internal) Recursive Hyperfunction: Perform a Hyperoperation...unsignedlonglongr=1;while(b--)r=n-3?HR(n-1,a,r):/* Exponentiation */r*a;returnr;}unsignedlonglongH(unsignedintn,unsignedlonglonga,unsignedlonglongb){// Hyperfunction (Recursive-Iterative-O(1) Hybrid): Perform a Hyperoperation...switch(n){case0:// Incrementreturn++b;case1:// Additionreturna+b;case2:// Multiplicationreturna*b;}returnHR(n,a,b);}unsignedlonglongAPH(unsignedintm,unsignedintn){// Ackermann-Péter Function (Recursive-Iterative-O(1) Hybrid)returnH(m,2,n+3)-3;}unsignedlonglong*p=0;unsignedlonglongAPRR(unsignedintm,unsignedintn){if(!m)return++n;unsignedlonglongr=p?p[m]:APRR(m-1,1);--m;while(n--)r=APRR(m,r);returnr;}unsignedlonglongAPRA(unsignedintm,unsignedintn){returnm?n?APRR(m,n):p?p[m]:APRA(--m,1):++n;}unsignedlonglongAPR(unsignedintm,unsignedintn){unsignedlonglongr=0;// Allocatep=(unsignedlonglong*)malloc(sizeof(unsignedlonglong)*(m+1));// Initializefor(;r<=m;++r)p[r]=r?APRA(r-1,1):APRA(r,0);// Calculater=APRA(m,n);// Freefree(p);returnr;}unsignedlonglongAP(unsignedintm,unsignedintn){returnAPH(m,n);returnAPR(m,n);}intmain(intn,char**a){unsignedintM,N;if(n!=3){printf("Usage: %s <m> <n>\n",*a);return1;}printf("AckermannPeter(%u, %u) = %llu\n",M=atoi(a[1]),N=atoi(a[2]),AP(M,N));//printf("\nPress any key...");//getch();return0;}

A couple of more iterative techniques...

/* Thejaka Maldeniya */#include<conio.h>unsignedlonglongHI(unsignedintn,unsignedlonglonga,unsignedlonglongb){// Hyperfunction (Iterative): Perform a Hyperoperation...unsignedlonglong*I,r=1;unsignedintN=n-3;if(!N)// Exponentiationwhile(b--)r*=a;elseif(b){n-=2;// AllocateI=(unsignedlonglong*)malloc(sizeof(unsignedlonglong)*n--);// InitializeI[n]=b;// Calculatefor(;;){if(I[n]){--I[n];if(n)I[--n]=r,r=1;elser*=a;}elsefor(;;)if(n==N)gotoa;elseif(I[++n])break;}a:// Freefree(I);}returnr;}unsignedlonglongH(unsignedintn,unsignedlonglonga,unsignedlonglongb){// Hyperfunction (Iterative-O(1) Hybrid): Perform a Hyperoperation...switch(n){case0:// Incrementreturn++b;case1:// Additionreturna+b;case2:// Multiplicationreturna*b;}returnHI(n,a,b);}unsignedlonglongAPH(unsignedintm,unsignedintn){// Ackermann-Péter Function (Recursive-Iterative-O(1) Hybrid)returnH(m,2,n+3)-3;}unsignedlonglong*p=0;unsignedlonglongAPIA(unsignedintm,unsignedintn){if(!m)return++n;// Initializeunsignedlonglong*I,r=p?p[m]:APIA(m-1,1);unsignedintM=m;if(n){// AllocateI=(unsignedlonglong*)malloc(sizeof(unsignedlonglong)*(m+1));// InitializeI[m]=n;// Calculatefor(;;){if(I[m]){if(m)--I[m],I[--m]=r,r=p?p[m]:APIA(m-1,1);elser+=I[m],I[m]=0;}elsefor(;;)if(m==M)gotoa;elseif(I[++m])break;}a:// Freefree(I);}returnr;}unsignedlonglongAPI(unsignedintm,unsignedintn){unsignedlonglongr=0;// Allocatep=(unsignedlonglong*)malloc(sizeof(unsignedlonglong)*(m+1));// Initializefor(;r<=m;++r)p[r]=r?APIA(r-1,1):APIA(r,0);// Calculater=APIA(m,n);// Freefree(p);returnr;}unsignedlonglongAP(unsignedintm,unsignedintn){returnAPH(m,n);returnAPI(m,n);}intmain(intn,char**a){unsignedintM,N;if(n!=3){printf("Usage: %s <m> <n>\n",*a);return1;}printf("AckermannPeter(%u, %u) = %llu\n",M=atoi(a[1]),N=atoi(a[2]),AP(M,N));//printf("\nPress any key...");//getch();return0;}

A few further tweaks/optimizations may be possible.

C#

Basic Version

usingSystem;classProgram{publicstaticlongAckermann(longm,longn){if(m>0){if(n>0)returnAckermann(m-1,Ackermann(m,n-1));elseif(n==0)returnAckermann(m-1,1);}elseif(m==0){if(n>=0)returnn+1;}thrownewSystem.ArgumentOutOfRangeException();}staticvoidMain(){for(longm=0;m<=3;++m){for(longn=0;n<=4;++n){Console.WriteLine("Ackermann({0}, {1}) = {2}",m,n,Ackermann(m,n));}}}}
Output:
Ackermann(0, 0) = 1Ackermann(0, 1) = 2Ackermann(0, 2) = 3Ackermann(0, 3) = 4Ackermann(0, 4) = 5Ackermann(1, 0) = 2Ackermann(1, 1) = 3Ackermann(1, 2) = 4Ackermann(1, 3) = 5Ackermann(1, 4) = 6Ackermann(2, 0) = 3Ackermann(2, 1) = 5Ackermann(2, 2) = 7Ackermann(2, 3) = 9Ackermann(2, 4) = 11Ackermann(3, 0) = 5Ackermann(3, 1) = 13Ackermann(3, 2) = 29Ackermann(3, 3) = 61Ackermann(3, 4) = 125

Efficient Version

usingSystem;usingSystem.Numerics;usingSystem.IO;usingSystem.Diagnostics;namespaceAckermann_Function{classProgram{staticvoidMain(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);//    }//}DateTimenow=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();}publicclassOverflowlessStack<T>{internalsealedclassSinglyLinkedNode{privateconstintArraySize=2048;T[]_array;int_size;publicSinglyLinkedNodeNext;publicSinglyLinkedNode(){_array=newT[ArraySize];}publicboolIsEmpty{get{return_size==0;}}publicSinglyLinkedNodePush(Titem){if(_size==ArraySize-1){SinglyLinkedNoden=newSinglyLinkedNode();n.Next=this;n.Push(item);returnn;}_array[_size++]=item;returnthis;}publicTPop(){return_array[--_size];}}privateSinglyLinkedNode_head=newSinglyLinkedNode();publicTPop(){Tret=_head.Pop();if(_head.IsEmpty&&_head.Next!=null)_head=_head.Next;returnret;}publicvoidPush(Titem){_head=_head.Push(item);}publicboolIsEmpty{get{return_head.Next==null&&_head.IsEmpty;}}}publicstaticBigIntegerAckermann(BigIntegerm,BigIntegern){varstack=newOverflowlessStack<BigInteger>();stack.Push(m);while(!stack.IsEmpty){m=stack.Pop();skipStack:if(m==0)n=n+1;elseif(m==1)n=n+2;elseif(m==2)n=n*2+3;elseif(n==0){--m;n=1;gotoskipStack;}else{stack.Push(m-1);--n;gotoskipStack;}}returnn;}}}

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>unsignedintackermann(unsignedintm,unsignedintn){if(m==0){returnn+1;}if(n==0){returnackermann(m-1,1);}returnackermann(m-1,ackermann(m,n-1));}intmain(){for(unsignedintm=0;m<4;++m){for(unsignedintn=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>usingbig_int=boost::multiprecision::cpp_int;big_intipow(big_intbase,big_intexp){big_intresult(1);while(exp){if(exp&1){result*=base;}exp>>=1;base*=base;}returnresult;}big_intackermann(unsignedm,unsignedn){staticbig_int(*ack)(unsigned,big_int)=[](unsignedm,big_intn)->big_int{switch(m){case0:returnn+1;case1:returnn+2;case2:return3+2*n;case3:return5+8*(ipow(big_int(2),n)-1);default:returnn==0?ack(m-1,big_int(1)):ack(m-1,ack(m,n-1));}};returnack(m,big_int(n));}intmain(){for(unsignedm=0;m<4;++m){for(unsignedn=0;n<10;++n){std::cout<<"A("<<m<<", "<<n<<") = "<<ackermann(m,n)<<"\n";}}std::cout<<"A(4, 1) = "<<ackermann(4,1)<<"\n";std::stringstreamss;ss<<ackermann(4,2);autotext=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) = 1A(0, 1) = 2A(0, 2) = 3A(0, 3) = 4A(0, 4) = 5A(0, 5) = 6A(0, 6) = 7A(0, 7) = 8A(0, 8) = 9A(0, 9) = 10A(1, 0) = 2A(1, 1) = 3A(1, 2) = 4A(1, 3) = 5A(1, 4) = 6A(1, 5) = 7A(1, 6) = 8A(1, 7) = 9A(1, 8) = 10A(1, 9) = 11A(2, 0) = 3A(2, 1) = 5A(2, 2) = 7A(2, 3) = 9A(2, 4) = 11A(2, 5) = 13A(2, 6) = 15A(2, 7) = 17A(2, 8) = 19A(2, 9) = 21A(3, 0) = 5A(3, 1) = 13A(3, 2) = 29A(3, 3) = 61A(3, 4) = 125A(3, 5) = 253A(3, 6) = 509A(3, 7) = 1021A(3, 8) = 2045A(3, 9) = 4093A(4, 1) = 65533A(4, 2) = (19729 digits)2003529930406846464979072351560255750447825475569751419265016973710894059556311...4717124577965048175856395072895337539755822087777506072339445587895905719156733

Chapel

procA(m:int,n:int):int{ifm==0thenreturnn+1;elseifn==0thenreturnA(m-1,1);elsereturnA(m-1,A(m,n-1));}

Clay

ackermann(m,n){if(m==0)returnn+1;if(n==0)returnackermann(m-1,1);returnackermann(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)5CLIPS> (ackerman 1 4)6CLIPS> (ackerman 2 4)11CLIPS> (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) = 125A(2,4) = 11A(1,4) = 6A(0,4) = 5CLIPS> (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

(defnackermann[mn](cond(zero?m)(incn)(zero?n)(ackermann(decm)1):else(ackermann(decm)(ackermannm(decn)))))

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

IDENTIFICATIONDIVISION.PROGRAM-ID.Ackermann.DATADIVISION.LINKAGESECTION.01MUSAGEUNSIGNED-LONG.01NUSAGEUNSIGNED-LONG.01Return-ValUSAGEUNSIGNED-LONG.PROCEDUREDIVISIONUSINGMNReturn-Val.EVALUATEMALSONWHEN0ALSOANYADD1TONGIVINGReturn-ValWHENNOT0ALSO0SUBTRACT1FROMMCALL"Ackermann"USINGBYCONTENTMBYCONTENT1BYREFERENCEReturn-ValWHENNOT0ALSONOT0SUBTRACT1FROMNCALL"Ackermann"USINGBYCONTENTMBYCONTENTNBYREFERENCEReturn-ValSUBTRACT1FROMMCALL"Ackermann"USINGBYCONTENTMBYCONTENTReturn-ValBYREFERENCEReturn-ValEND-EVALUATEGOBACK.

CoffeeScript

ackermann=(m, n) ->ifmis0thenn+1elseifm>0andnis0thenackermannm-1,1elseackermannm-1,ackermannm,n-1

Comal

0010//0020// Ackermann function0030//0040FUNCa#(m#,n#)0050IFm#=0THENRETURNn#+10060IFn#=0THENRETURNa#(m#-1,1)0070RETURNa#(m#-1,a#(m#,n#-1))0080ENDFUNCa#0090//0100// Print table of Ackermann values0110//0120ZONE50130FORm#:=0TO3DO0140FORn#:=0TO4DOPRINTa#(m#,n#),0150PRINT0160ENDFORm#0170END
Output:
1    2    3    4    52    3    4    5    63    5    7    9    115    13   29   61   125

Common Lisp

(defunackermann(mn)(cond((zeropm)(1+n))((zeropn)(ackermann(1-m)1))(t(ackermann(1-m)(ackermannm(1-n))))))

More elaborately:

(defunackermann(mn)(casem((0)(1+n))((1)(+2n))((2)(+nn3))((3)(-(expt2(+3n))3))(otherwise(ackermann(1-m)(if(zeropn)1(ackermannm(1-n)))))))(loopformfrom0to4do(loopfornfrom(-5m)to(-6m)do(formatt"A(~d, ~d) = ~d~%"mn(ackermannmn))))
Output:
A(0, 5) = 6
A(0, 6) = 7A(1, 4) = 6A(1, 5) = 7A(2, 3) = 9A(2, 4) = 11A(3, 2) = 29A(3, 3) = 61A(4, 1) = 65533
A(4, 2) = 2003529930 <... skipping a few digits ...> 56733

Component Pascal

BlackBox Component Builder

MODULENpctAckerman;IMPORTStdLog;VARm,n:INTEGER;PROCEDUREAckerman(x,y:INTEGER):INTEGER;BEGINIFx=0THENRETURNy+1ELSIFy=0THENRETURNAckerman(x-1,1)ELSERETURNAckerman(x-1,Ackerman(x,y-1))ENDENDAckerman;PROCEDUREDo*;BEGINFORm:=0TO3DOFORn:=0TO6DOStdLog.Int(Ackerman(m,n));StdLog.Char(' ')END;StdLog.LnEND;StdLog.LnENDDo;ENDNpctAckerman.

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

Standard

Fixpointack(m:nat):nat->nat:=fixack_m(n:nat):nat:=matchmwith|0=>Sn|Spm=>matchnwith|0=>ackpm1|Spn=>ackpm(ack_mpn)endend.(*  Example:    A(3, 2) = 29*)Evalcomputeinack32.
Output:
     = 29     : nat

Using fold

RequireImportUtf8.SectionFOLD.Context{A:Type}(f:A→A)(a:A).Fixpointfold(n:nat):A:=matchnwith|O=>a|Sk=>f(foldk)end.EndFOLD.Definitionackermann:nat→nat→nat:=fold(λg,foldg(g(SO)))S.

Crystal

Translation of:Ruby
defack(m,n)ifm==0n+1elsifn==0ack(m-1,1)elseack(m-1,ack(m,n-1))endend#Example:(0..3).eachdo|m|puts(0..6).map{|n|ack(m,n)}.join(' ')end
Output:
1 2 3 4 5 6 72 3 4 5 6 7 83 5 7 9 11 13 155 13 29 61 125 253 509

D

Basic version

ulongackermann(inulongm,inulongn)purenothrow@nogc{if(m==0)returnn+1;if(n==0)returnackermann(m-1,1);returnackermann(m-1,ackermann(m,n-1));}voidmain(){assert(ackermann(2,4)==11);}

More Efficient Version

Translation of:Mathematica
importstd.stdio,std.bigint,std.conv;BigIntipow(BigIntbase,BigIntexp)purenothrow{autoresult=1.BigInt;while(exp){if(exp&1)result*=base;exp>>=1;base*=base;}returnresult;}BigIntackermann(inuintm,inuintn)purenothrowout(result){assert(result>=0);}body{staticBigIntack(inuintm,inBigIntn)purenothrow{switch(m){case0:returnn+1;case1:returnn+2;case2:return3+2*n;//case 3: return 5 + 8 * (2 ^^ n - 1);case3:return5+8*(ipow(2.BigInt,n)-1);default:return(n==0)?ack(m-1,1.BigInt):ack(m-1,ack(m,n-1));}}returnack(m,n.BigInt);}voidmain(){foreach(immutablem;1..4)foreach(immutablen;1..9)writefln("ackermann(%d, %d): %s",m,n,ackermann(m,n));writefln("ackermann(4, 1): %s",ackermann(4,1));immutablea=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): 3ackermann(1, 2): 4ackermann(1, 3): 5ackermann(1, 4): 6ackermann(1, 5): 7ackermann(1, 6): 8ackermann(1, 7): 9ackermann(1, 8): 10ackermann(2, 1): 5ackermann(2, 2): 7ackermann(2, 3): 9ackermann(2, 4): 11ackermann(2, 5): 13ackermann(2, 6): 15ackermann(2, 7): 17ackermann(2, 8): 19ackermann(3, 1): 13ackermann(3, 2): 29ackermann(3, 3): 61ackermann(3, 4): 125ackermann(3, 5): 253ackermann(3, 6): 509ackermann(3, 7): 1021ackermann(3, 8): 2045ackermann(4, 1): 65533ackermann(4, 2)) (19729 digits):2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880...699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156733

Dart

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

intA(intm,intn)=>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 withr (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))] sA3 9 lA x f
Output:
4093

Delphi

functionAckermann(m,n:Int64):Int64;beginifm=0thenResult:=n+1elseifn=0thenResult:=Ackermann(m-1,1)elseResult:=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

functionAckermann(m,n:Integer):Integer;beginifm=0thenResult:=n+1elseifn=0thenResult:=Ackermann(m-1,1)elseResult:=Ackermann(m-1,Ackermann(m,n-1));end;

Dylan

definemethodack(m==0,n::<integer>)n+1end;definemethodack(m::<integer>,n::<integer>)ack(m-1,if(n==0)1elseack(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 .   if m = 0      return n + 1   elif n = 0      return ackerm (m - 1) 1   else      return ackerm (m - 1) ackerm m (n - 1)   ..print ackerm 3 6

Egel

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

Eiffel

Example code

Test of Example code

classACKERMAN_EXAMPLEfeature-- Basic Operationsackerman(m,n:NATURAL):NATURAL-- Recursively compute the n-th term of a series.requirenon_negative_m:m>=0non_negative_n:n>=0doifm=0thenResult:=n+1elseifm>0andn=0thenResult:=ackerman(m-1,1)elseifm>0andn>0thenResult:=ackerman(m-1,ackerman(m,n-1))elsecheckinvalid_arg_state:Falseendendendend

Ela

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

Elena

ELENA 6.x :

import extensions;// --- Ackermann function ---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)=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)=253

Elixir

defmoduleAckermanndodefack(0,n),do:n+1defack(m,0),do:ack(m-1,1)defack(m,n),do:ack(m-1,ack(m,n-1))endEnum.each(0..3,fnm->IO.putsEnum.map_join(0..6," ",fnn->Ackermann.ack(m,n)end)end)
Output:
1 2 3 4 5 6 72 3 4 5 6 7 83 5 7 9 11 13 155 13 29 61 125 253 509

Emacs Lisp

(defunackermann(mn)(cond((zeropm)(1+n))((zeropn)(ackermann(1-m)1))(t(ackermann(1-m)(ackermannm(1-n))))))

EMal

fun ackermann ← <int m, int n|when(m æ 0,  n + 1,  when(n æ 0,  ackermann(m - 1, 1),  ackermann(m - 1, ackermann(m, n - 1))))for int m ← 0; m ≤ 3; ++m  for int n ← 0; n ≤ 6; ++n    writeLine("Ackermann(" + m + ", " + n + ") = ", ackermann(m, n))  endend
Output:
Ackermann(0, 0) = 1Ackermann(0, 1) = 2Ackermann(0, 2) = 3Ackermann(0, 3) = 4Ackermann(0, 4) = 5Ackermann(0, 5) = 6Ackermann(0, 6) = 7Ackermann(1, 0) = 2Ackermann(1, 1) = 3Ackermann(1, 2) = 4Ackermann(1, 3) = 5Ackermann(1, 4) = 6Ackermann(1, 5) = 7Ackermann(1, 6) = 8Ackermann(2, 0) = 3Ackermann(2, 1) = 5Ackermann(2, 2) = 7Ackermann(2, 3) = 9Ackermann(2, 4) = 11Ackermann(2, 5) = 13Ackermann(2, 6) = 15Ackermann(3, 0) = 5Ackermann(3, 1) = 13Ackermann(3, 2) = 29Ackermann(3, 3) = 61Ackermann(3, 4) = 125Ackermann(3, 5) = 253Ackermann(3, 6) = 509

Erlang

-module(ackermann).-export([ackermann/2]).ackermann(0,N)->N+1;ackermann(M,0)->ackermann(M-1,1);ackermann(M,N)whenM>0andalsoN>0->ackermann(M-1,ackermann(M,N-1)).

ERRE

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

PROGRAM ACKERMAN!! computes Ackermann function! (second version for rosettacode.org)!!$INTEGERDIM STACK[10000]!$INCLUDE="PC.LIB"PROCEDURE ACK(M,N->N)  LOOP    CURSOR_SAVE(->CURX%,CURY%)     LOCATE(8,1)    PRINT("Livello Stack:";S;"  ")    LOCATE(CURY%,CURX%)    IF M<>0 THEN       IF N<>0 THEN           STACK[S]=M           S+=1           N-=1        ELSE           M-=1           N+=1        END IF        CONTINUE LOOP     ELSE        N+=1        S-=1    END IF    IF S<>0 THEN        M=STACK[S]        M-=1        CONTINUE LOOP      ELSE        EXIT PROCEDURE    END IF  END LOOPEND PROCEDUREBEGIN   PRINT(CHR$(12);)   FOR X=0 TO 3 DO     FOR Y=0 TO 9 DO        S=1        ACK(X,Y->ANS)        PRINT(ANS;)     END FOR     PRINT   END FOREND PROGRAM

Prints a list of Ackermann function values: from A(0,0) to A(3,9). Uses a stack to avoidoverflow.Formating options to make this pretty are available, but for this example only basic output is used.

 1  2  3  4  5  6  7  8  9  10 2  3  4  5  6  7  8  9  10  11 3  5  7  9  11  13  15  17  19  21 5  13  29  61  125  253  509  1021  2045  4093Stack Level: 1

Euler Math Toolbox

>M=zeros(1000,1000);>function map A(m,n) ...$  global M;$  if m==0 then return n+1; endif;$  if n==0 then return A(m-1,1); endif;$  if m<=cols(M) and n<=cols(M) then$    M[m,n]=A(m-1,A(m,n-1));$    return M[m,n];$  else return A(m-1,A(m,n-1));$  endif;$endfunction>shortestformat; A((0:3)',0:5)         1         2         3         4         5         6          2         3         4         5         6         7          3         5         7         9        11        13          5        13        29        61       125       253

Euphoria

This is based on theVBScript 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 functionfor 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.

letrecackermannmn=matchm,nwith|0,n->n+1|m,0->ackermann(m-1)1|m,n->ackermann(m-1)ackermannm(n-1)doprintfn"%A"(ackermann(intfsi.CommandLineArgs.[1])(intfsi.CommandLineArgs.[2]))

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

letackermannMN=letrecacker(m,n,k)=matchm,nwith|0,n->k(n+1)|m,0->acker((m-1),1,k)|m,n->acker(m,(n-1),(funx->acker((m-1),x,k)))acker(M,N,(funx->x))

Factor

USING:kernelmathlocalscombinators;IN:ackermann::ackermann(mn--u){{[m0=][n1+]}{[n0=][m1-1ackermann]}[m1-mn1-ackermannackermann]}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 ) ) )endfor M in [ 0:4 ] for N in [ 0:7 ]   >> ackermann( M, N ), " " end >end

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

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

FALSE

[$$[%  \$$[%     1-\$@@a;!  { i j -> A(i-1, A(i, j-1)) }  1]?0=[     %1         { i 0 -> A(i-1, 1) }   ]?  \1-a;!1]?0=[  %1+           { 0 j -> j+1 } ]?]a: { j i }3 3 a;! .  { 61 }

Fantom

class Main{  // assuming m,n are positive  static Int ackermann (Int m, Int n)  {    if (m == 0)      return n + 1    else if (n == 0)      return ackermann (m - 1, 1)    else      return ackermann (m - 1, ackermann (m, n - 1))  }  public static Void main ()  {    (0..3).each |m|    {      (0..6).each |n|      {        echo ("Ackerman($m, $n) = ${ackermann(m, n)}")      }    }  }}
Output:
Ackerman(0, 0) = 1Ackerman(0, 1) = 2Ackerman(0, 2) = 3Ackerman(0, 3) = 4Ackerman(0, 4) = 5Ackerman(0, 5) = 6Ackerman(0, 6) = 7Ackerman(1, 0) = 2Ackerman(1, 1) = 3Ackerman(1, 2) = 4Ackerman(1, 3) = 5Ackerman(1, 4) = 6Ackerman(1, 5) = 7Ackerman(1, 6) = 8Ackerman(2, 0) = 3Ackerman(2, 1) = 5Ackerman(2, 2) = 7Ackerman(2, 3) = 9Ackerman(2, 4) = 11Ackerman(2, 5) = 13Ackerman(2, 6) = 15Ackerman(3, 0) = 5Ackerman(3, 1) = 13Ackerman(3, 2) = 29Ackerman(3, 3) = 61Ackerman(3, 4) = 125Ackerman(3, 5) = 253Ackerman(3, 6) = 509

FBSL

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

#APPTYPECONSOLETestAckermann()PAUSESUBTestAckermann()FORDIMm=0TO3FORDIMn=0TO10PRINTAckermannF(m,n)," ";NEXTPRINTNEXTENDSUBFUNCTIONAckermannF(mASINTEGER,nASINTEGER)ASINTEGERIFNOTmTHENRETURNn+1IFNOTnTHENRETURNAckermannA(m-1,1)RETURNAckermannC(m-1,AckermannF(m,n-1))ENDFUNCTIONDYNCAckermannC(mASINTEGER,nASINTEGER)ASINTEGER
intAckermann(intm,intn){if(!m)returnn+1;if(!n)returnAckermann(m-1,1);returnAckermann(m-1,Ackermann(m,n-1));}intmain(intm,intn){returnAckermann(m,n);}
ENDDYNCDYNASMAckermannA(mASINTEGER,nASINTEGER)ASINTEGER
ENTER0,0INVOKEAckermann,m,nLEAVERET@AckermannENTER0,0.IFDWORDPTR[m].THENJMP@F.ENDIFMOVEAX,nINCEAXJMPxit@@.IFDWORDPTR[n].THENJMP@F.ENDIFMOVEAX,mDECEAXINVOKEAckermann,EAX,1JMPxit@@MOVEAX,nDECEAXINVOKEAckermann,m,EAXMOVECX,mDECECXINVOKEAckermann,ECX,EAX@xitLEAVERET8
ENDDYNASM
Output:
1 2 3 4 5 6 7 8 9 10 112 3 4 5 6 7 8 9 10 11 123 5 7 9 11 13 15 17 19 21 235 13 29 61 125 253 509 1021 2045 4093 8189Press any key to continue...

Fermat

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

Forth

:acker( m n -- u )over0=IFnip1+EXITTHENswap1-swap( m-1 n -- )dup0=IF1+recurseEXITTHEN1-over1+swaprecurserecurse;
Example of use:
FORTH> 0 0 acker . 1  okFORTH> 3 4 acker . 125  ok

An optimized version:

:ackermann( m n -- u )over( case statement)0over=ifdropnip1+else1over=ifdropnip2+else2over=ifdropnip2*3+else3over=ifdropswap5+swaplshift3-elsedropswap1-swapdupif1-over1+swaprecurserecurseexitelse1+recurseexit\ allow tail recursionthenthenthenthenthen;

Fortran

Works with:Fortran version 90 and later
PROGRAMEXAMPLEIMPLICIT NONEINTEGER::i,jDOi=0,3DOj=0,6WRITE(*,"(I10)",ADVANCE="NO")Ackermann(i,j)END DO    WRITE(*,*)END DOCONTAINS  RECURSIVE FUNCTIONAckermann(m,n)RESULT(ack)INTEGER::ack,m,nIF(m==0)THENack=n+1ELSE IF(n==0)THENack=Ackermann(m-1,1)ELSEack=Ackermann(m-1,Ackermann(m,n-1))END IF  END FUNCTIONAckermannEND PROGRAMEXAMPLE

Free Pascal

See#Delphi or#Pascal.

FreeBASIC

' version 28-10-2016' compile with: fbc -s console' to do A(4, 2) the stack size needs to be increased' compile with: fbc -s console -t 2000Functionackerman(mAsLong,nAsLong)AsLongIfm=0Thenackerman=n+1Ifm>0ThenIfn=0Thenackerman=ackerman(m-1,1)ElseIfn>0Thenackerman=ackerman(m-1,ackerman(m,n-1))EndIfEndIfEndIfEndFunction' ------=< MAIN >=------DimAsLongm,nPrintForm=0To4PrintUsing"###";m;Forn=0To10' A(4, 1) or higher will run out of stack memory (default 1M)' change n = 1 to n = 2 to calculate A(4, 2), increase stack!Ifm=4Andn=1ThenExitForPrintUsing"######";ackerman(m,n);NextPrintNext' empty keyboard bufferWhileInKey<>"":WendPrint:Print"hit any key to end program"SleepEnd
Output:
  0     1     2     3     4     5     6     7     8     9    10    11  1     2     3     4     5     6     7     8     9    10    11    12  2     3     5     7     9    11    13    15    17    19    21    23  3     5    13    29    61   125   253   509  1021  2045  4093  8189  4    13

FunL

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

Futhark

funackermann(m:int,n:int):int=ifm==0thenn+1elseifn==0thenackermann(m-1,1)elseackermann(m-1,ackermann(m,n-1))

FutureBasic

include "NSLog.incl"local fn Ackerman( m as NSInteger, n as NSInteger ) as NSInteger  NSInteger result    select    case m == 0 : result = ( n + 1 )    case n == 0 : result = fn Ackerman( ( m - 1 ), 1 )    case else   : result = fn Ackerman( ( m - 1 ), fn Ackerman( m, ( n - 1 ) ) )  end selectend fn = resultNSInteger          m, nCFMutableStringRef mutStrmutStr = fn StringWithCapacity( 0 )for m = 0 to 3  for n = 0 to 9    StringAppendString( mutStr, fn StringWithFormat( @"fn Ackerman( %ld, %ld ) = %ld\n", m, n, fn Ackerman( m, n ) ) )  nextnextNSLog( @"%@", mutStr )HandleEvents

Output:

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

Fōrmulæ

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

Programs in Fōrmulæ are created/edited online in itswebsite.

Inthis page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.

Solution

Test case

Gambas

PublicFunctionAckermann(mAsFloat,nAsFloat)AsFloatIfm=0ThenReturnn+1EndIfIfn=0ThenReturnAckermann(m-1,1)EndIfReturnAckermann(m-1,Ackermann(m,n-1))EndPublicSubMain()Dimm,nAsFloatForm=0To3Forn=0To4Print"Ackermann(";m;", ";n;") = ";Ackermann(m,n)NextNextEnd

GAP

ack:=function(m,n)ifm=0thenreturnn+1;elif(m>0)and(n=0)thenreturnack(m-1,1);elif(m>0)and(n>0)thenreturnack(m-1,ack(m,n-1));elsereturnfail;fi;end;

Genyris

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

GML

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

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

gnuplot

A(m, n)=m==0?n+1:n==0?A(m-1,1):A(m-1,A(m,n-1))printA(0,4)printA(1,4)printA(2,4)printA(3,4)
Output:
5611stack overflow

Go

Classic version

funcAckermann(m,nuint)uint{switch0{casem:returnn+1casen:returnAckermann(m-1,1)}returnAckermann(m-1,Ackermann(m,n-1))}

Expanded version

funcAckermann2(m,nuint)uint{switch{casem==0:returnn+1casem==1:returnn+2casem==2:return2*n+3casem==3:return8<<n-3casen==0:returnAckermann2(m-1,1)}returnAckermann2(m-1,Ackermann2(m,n-1))}

Expanded version with arbitrary precision

packagemainimport("fmt""math/big""math/bits"// Added in Go 1.9)varone=big.NewInt(1)vartwo=big.NewInt(2)varthree=big.NewInt(3)vareight=big.NewInt(8)funcAckermann2(m,n*big.Int)*big.Int{ifm.Cmp(three)<=0{switchm.Int64(){case0:returnnew(big.Int).Add(n,one)case1:returnnew(big.Int).Add(n,two)case2:r:=new(big.Int).Lsh(n,1)returnr.Add(r,three)case3:ifnb:=n.BitLen();nb>bits.UintSize{// n is too large to represent as a// uint for use in the Lsh method.panic(TooBigError(nb))// If we tried to continue anyway, doing// 8*2^n-3 as bellow, we'd use hundreds// of megabytes and lots of CPU time// without the Exp call even returning.r:=new(big.Int).Exp(two,n,nil)r.Mul(eight,r)returnr.Sub(r,three)}r:=new(big.Int).Lsh(eight,uint(n.Int64()))returnr.Sub(r,three)}}ifn.BitLen()==0{returnAckermann2(new(big.Int).Sub(m,one),one)}returnAckermann2(new(big.Int).Sub(m,one),Ackermann2(m,new(big.Int).Sub(n,one)))}typeTooBigErrorintfunc(eTooBigError)Error()string{returnfmt.Sprintf("A(m,n) had n of %d bits; too large",int(e))}funcmain(){show(0,0)show(1,2)show(2,4)show(3,100)show(3,1e6)show(4,1)show(4,2)show(4,3)}funcshow(m,nint64){deferfunc(){// Ackermann2 could/should have returned an error// instead of a panic. But here's how to recover// from the panic, and report "expected" errors.ife:=recover();e!=nil{iferr,ok:=e.(TooBigError);ok{fmt.Println("Error:",err)}else{panic(e)}}}()fmt.Printf("A(%d, %d) = ",m,n)a:=Ackermann2(big.NewInt(m),big.NewInt(n))ifa.BitLen()<=256{fmt.Println(a)}else{s:=a.String()fmt.Printf("%d digits starting/ending with: %s...%s\n",len(s),s[:20],s[len(s)-20:],)}}
Output:
A(0, 0) = 1A(1, 2) = 4A(2, 4) = 11A(3, 100) = 10141204801825835211973625643005A(3, 1000000) = 301031 digits starting/ending with: 79205249834367186005...39107225301976875005A(4, 1) = 65533A(4, 2) = 19729 digits starting/ending with: 20035299304068464649...45587895905719156733A(4, 3) = Error: A(m,n) had n of 65536 bits; too large

Golfscript

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

Groovy

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

Test program:

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

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

Hare

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

Haskell

ack::Int->Int->Intack0n=succnackm0=ack(predm)1ackmn=ack(predm)(ackm(predn))main::IO()main=mapM_print$uncurryack<$>[(0,0),(3,4)]
Output:
1125

Generating a list instead:

importData.List(mapAccumL)-- everything here are [Int] or [[Int]], which would overflow-- * had it not overrun the stack first *ackermann=iterateack[1..]whereacka=swheres=snd$mapAccumLf(taila)(1:zipWith(-)s(1:s))fab=(aa,headaa)whereaa=dropbamain=mapM_print$map(\n->take(6-n)$ackermann!!n)[0..5]

Haxe

classRosettaDemo{staticpublicfunctionmain(){Sys.print(ackermann(3,4));}staticfunctionackermann(m:Int,n:Int){if(m==0){returnn+1;}elseif(n==0){returnackermann(m-1,1);}returnackermann(m-1,ackermann(m,n-1));}}

Hoon

|=  [m=@ud n=@ud]?:  =(m 0)  +(n)?:  =(n 0)  $(n 1, m (dec m))$(m (dec m), n $(n (dec n)))

Icon andUnicon

Library:Icon Programming Library

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

procedureacker(i,j)staticmemoryinitial{memory:=table()everymemory[0to100]:=table()}ifi=0thenreturnj+1ifj=0then/memory[i][j]:=acker(i-1,1)else/memory[i][j]:=acker(i-1,acker(i,j-1))returnmemory[i][j]endproceduremain()everym:=0to3do{everyn:=0to8do{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->NatAZn=SnA(Sm)Z=Am(SZ)A(Sm)(Sn)=Am(A(Sm)n)

Ioke

Translation of:Clojure
ackermann=method(m,n,cond(mzero?,nsucc,nzero?,ackermann(mpred,1),ackermann(mpred,ackermann(m,npred))))

J

ack=:>:@]`(<:@[$:1:)`(<:@[$:($:<:))@.(,&*i.0:)M.

The different cases can be split into different lines:

c1=:>:@]NB. if 0=x, 1+yc2=:<:@[ack1:NB. if 0=y, (x-1) ack 1c3=:<:@[ack[ack<:@]NB. else,   (x-1) ack x ack y-1ack=:c1`c2`c3@.(,&*i.0:)M.
Example use:
0ack341ack352ack393ack361

J's stack was too small for me to compute4 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-~[({&(24$'>:  2x&+')::(,&'&1'&'2x&*'@:(-&2))"0@:[128!:2])3+]
Example use:
0123Ack0123456712345678234567893579111315175132961125253509102134Ack012513...13655332003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933348101038234342907263181822949382118812668869506364761547029165041871916351587966347219442930927982084309104855990570159318959639524863372367203002916...4#@:":@:Ack2NB. Number of digits of 4 Ack 2197295Ack065533

A structured derivation of Ack follows:

o=.@:NB. Composition of verbs (functions)x=.o[NB. Composing the left noun (argument)(rows2up=.,&'&1'&'2x&*')oi.42x&*2x&*&12x&*&1&12x&*&1&1&1NB. 2's multiplication, exponentiation, tetration, pentation, etc.012(BuckTruncated=.(rows2upxapply])f.)01234502468...124816...12416655362003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933348101038234342907263181822949382118812668869506364761547029165041871916351587966347219442930927982084309104855990570159318959639524863372367203...NB. Buck truncated function (missing the first two rows)BuckTruncatedNB. Buck truncated function-level code,&'&1'&'2x&*'@:[128!:2](rows01=.{&('>:',:'2x&+'))01NB. The missing first two rows>:2x&+Buck=.(rows01::(rows2upo(-&2)))"0xapply](Ack=.(3-~[Buck3+])f.)NB. Ackermann function-level code3-~[({&(24$'>:  2x&+')::(,&'&1'&'2x&*'@:(-&2))"0@:[128!:2])3+]

Java

importjava.math.BigInteger;publicstaticBigIntegerack(BigIntegerm,BigIntegern){returnm.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+
@FunctionalInterfacepublicinterfaceFunctionalField<FIELDextendsEnum<?>>{publicObjectuntypedField(FIELDfield);@SuppressWarnings("unchecked")publicdefault<VALUE>VALUEfield(FIELDfield){return(VALUE)untypedField(field);}}
importjava.util.function.BiFunction;importjava.util.function.Function;importjava.util.function.Predicate;importjava.util.function.UnaryOperator;importjava.util.stream.Stream;publicinterfaceTailRecursive{publicstatic<INPUT,INTERMEDIARY,OUTPUT>Function<INPUT,OUTPUT>new_(Function<INPUT,INTERMEDIARY>toIntermediary,UnaryOperator<INTERMEDIARY>unaryOperator,Predicate<INTERMEDIARY>predicate,Function<INTERMEDIARY,OUTPUT>toOutput){returninput->$.new_(Stream.iterate(toIntermediary.apply(input),unaryOperator),predicate,toOutput);}publicstatic<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);}publicenum${$$;privatestatic<INTERMEDIARY,OUTPUT>OUTPUTnew_(Stream<INTERMEDIARY>stream,Predicate<INTERMEDIARY>predicate,Function<INTERMEDIARY,OUTPUT>function){returnstream.filter(predicate).map(function).findAny().orElseThrow(RuntimeException::new);}}}
importjava.math.BigInteger;importjava.util.Stack;importjava.util.function.BinaryOperator;importjava.util.stream.Collectors;importjava.util.stream.Stream;publicinterfaceAckermann{publicstaticAckermannnew_(BigIntegernumber1,BigIntegernumber2,Stack<BigInteger>stack,booleanflag){return$.new_(number1,number2,stack,flag);}publicstaticvoidmain(String...arguments){$.main(arguments);}publicBigIntegernumber1();publicBigIntegernumber2();publicStack<BigInteger>stack();publicbooleanflag();publicenum${$$;privatestaticfinalBigIntegerZERO=BigInteger.ZERO;privatestaticfinalBigIntegerONE=BigInteger.ONE;privatestaticfinalBigIntegerTWO=BigInteger.valueOf(2);privatestaticfinalBigIntegerTHREE=BigInteger.valueOf(3);privatestaticfinalBigIntegerFOUR=BigInteger.valueOf(4);privatestaticAckermannnew_(BigIntegernumber1,BigIntegernumber2,Stack<BigInteger>stack,booleanflag){return(FunctionalAckermann)field->{switch(field){casenumber1:returnnumber1;casenumber2:returnnumber2;casestack:returnstack;caseflag:returnflag;default:thrownewUnsupportedOperationException(fieldinstanceofField?"Field checker has not been updated properly.":"Field is not of the correct type.");}};}privatestaticfinalBinaryOperator<BigInteger>ACKERMANN=TailRecursive.new_((BigIntegernumber1,BigIntegernumber2)->new_(number1,number2,Stream.of(number1).collect(Collectors.toCollection(Stack::new)),false),ackermann->{BigIntegernumber1=ackermann.number1();BigIntegernumber2=ackermann.number2();Stack<BigInteger>stack=ackermann.stack();if(!stack.empty()&&!ackermann.flag()){number1=stack.pop();}switch(number1.intValue()){case0:returnnew_(number1,number2.add(ONE),stack,false);case1:returnnew_(number1,number2.add(TWO),stack,false);case2:returnnew_(number1,number2.multiply(TWO).add(THREE),stack,false);default:if(ZERO.equals(number2)){returnnew_(number1.subtract(ONE),ONE,stack,true);}else{stack.push(number1.subtract(ONE));returnnew_(number1,number2.subtract(ONE),stack,true);}}},ackermann->ackermann.stack().empty(),Ackermann::number2)::apply;privatestaticvoidmain(String...arguments){System.out.println(ACKERMANN.apply(FOUR,TWO));}privateenumField{number1,number2,stack,flag}@FunctionalInterfaceprivateinterfaceFunctionalAckermannextendsFunctionalField<Field>,Ackermann{@OverridepublicdefaultBigIntegernumber1(){returnfield(Field.number1);}@OverridepublicdefaultBigIntegernumber2(){returnfield(Field.number2);}@OverridepublicdefaultStack<BigInteger>stack(){returnfield(Field.stack);}@Overridepublicdefaultbooleanflag(){returnfield(Field.flag);}}}}

Template:Iterative version

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

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.

jq

Works with:jq version 1.4

Also works with gojq, the Go implementation of jq.

Except for a minor tweak to the line using string interpolation, the following have also been tested using jaq, the Rust implementation of jq, as of April 13, 2023.

For infinite-precision integer arithmetic, use gojq or fq.

Without Memoization

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

Examples:

A(4;1)
Output:
65533

Using gojq:

A(4;2), A(3;1000000) | tostring | length
Output:
19729301031

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.jsiack(1,3) ==> 5ack(2,3) ==> 9ack(3,3) ==> 61ack(1,5) ==> 7ack(2,5) ==> 13ack(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)65533julia> @time ack3(4,1)elapsed time: 0.49337724 seconds (30405308 bytes allocated)65533

K

Works with:Kona
   ack:{:[0=x;y+1;0=y;_f[x-1;1];_f[x-1;_f[x;y-1]]]}   ack[2;2]7   ack[2;7]17

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 = 4Lfun 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: 21, 2: 41, 4: 61, 6: 81, 8: 102, 0: 32, 2: 72, 4: 112, 6: 152, 8: 193, 0: 53, 2: 293, 4: 1253, 6: 5093, 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.3HOW 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 SOIM 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 outerKTHXBYE

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.printflocal 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 iclocal END=n+1local ntmp,gtmprepeatic=0ntmp,gtmp=nxt[ic], goal[ic]z_add_ui(v, ntmp, 1)while z_cmp(ntmp, gtmp) == 0 doz_set(gtmp,v)z_add_ui(ntmp, ntmp, 1)nxt[ic], goal[ic]=ntmp, gtmpic=ic+1ntmp,gtmp=nxt[ic], goal[ic]endz_add_ui(ntmp, ntmp, 1)nxt[ic]=ntmpuntil z_cmp_ui(nxt[i], END) == 0return vendif #arg<1 thenprint("Ackermann: "..arg[0].." <num1> [num2]")elseprintf("%Zd\n", ack(tonumber(arg[1]), arg[2] and tonumber(arg[2]) or 0))end
Output:
> time ./ackermann_iter.lua 4 165533./ackermann_iter.lua 4 1  0,01s user 0,01s system 95% cpu 0,015 total // AMD FX-8350@4 GHz> time ./ackermann.lua 3 10                                              ⏎8189./ackermann.lua 3 10  0,22s user 0,00s system 98% cpu 0,222 total // recursive solution> time ./ackermann_iter.lua 3 108189./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)}}}CheckitModule 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

MACRO-11

        .TITLE  ACKRMN        .MCALL  .TTYOUT,.EXITACKRMN::JMP     MKTBL        ; R0 = ACK(R0,R1)ACK:    MOV     SP,R2           ; KEEP OLD STACK PTR        MOV     #ASTK,SP        ; USE PRIVATE STACK        JSR     PC,1$        MOV     R2,SP           ; RESTORE STACK PTR        RTS     PC1$:     TST     R0        BNE     2$        INC     R1        MOV     R1,R0         RTS     PC2$:     TST     R1        BNE     3$        DEC     R0        INC     R1        BR      1$3$:     MOV     R0,-(SP)        DEC     R1        JSR     PC,1$        MOV     R0,R1        MOV     (SP)+,R0        DEC     R0        BR      1$        .BLKB   4000           ; BIG STACKASTK    =       .        ; PRINT TABLEMMAX    =       4NMAX    =       7MKTBL:  CLR     R31$:     CLR     R42$:     MOV     R3,R0        MOV     R4,R1         JSR     PC,ACK        JSR     PC,PR0         INC     R4        CMP     R4,#NMAX        BLT     2$        MOV     #15,R0        .TTYOUT        MOV     #12,R0        .TTYOUT        INC     R3        CMP     R3,#MMAX        BLT     1$        .EXIT                ; PRINT NUMBER IN R0 AS DECIMALPR0:    MOV     #4$,R11$:     MOV     #-1,R22$:     INC     R2        SUB     #12,R0        BCC     2$        ADD     #72,R0        MOVB    R0,-(R1)        MOV     R2,R0        BNE     1$3$:     MOVB    (R1)+,R0        .TTYOUT        BNE     3$        RTS     PC        .ASCII  /...../4$:     .BYTE   11,0        .END    ACKRMN
Output:
1       2       3       4       5       6       72       3       4       5       6       7       83       5       7       9       11      13      155       13      29      61      125     253     509

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 theSET LIST) command.Values have to be pushed and popped from it by hand (usingSAVE andRESTORE), and fora 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 isdone 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 passesthe 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) =    1ACK(0,1) =    2ACK(0,2) =    3ACK(0,3) =    4ACK(0,4) =    5ACK(0,5) =    6ACK(0,6) =    7ACK(0,7) =    8ACK(0,8) =    9ACK(1,0) =    2ACK(1,1) =    3ACK(1,2) =    4ACK(1,3) =    5ACK(1,4) =    6ACK(1,5) =    7ACK(1,6) =    8ACK(1,7) =    9ACK(1,8) =   10ACK(2,0) =    3ACK(2,1) =    5ACK(2,2) =    7ACK(2,3) =    9ACK(2,4) =   11ACK(2,5) =   13ACK(2,6) =   15ACK(2,7) =   17ACK(2,8) =   19ACK(3,0) =    5ACK(3,1) =   13ACK(3,2) =   29ACK(3,3) =   61ACK(3,4) =  125ACK(3,5) =  253ACK(3,6) =  509ACK(3,7) = 1021ACK(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 ofm{\displaystyle {\displaystyle m}}. (SeeWikipedia: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 computeAckermann( 4, 1 ) andAckermann( 4, 2 ) essentially instantly, thoughAckermann( 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 athttps://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. Theack/3 predicate is implemented in terms of theack/2 function. Theack/2 function is implemented in terms of theack/3 predicate. This makes the code both more concise and easier to follow than would otherwise be the case. Theinteger type is used instead ofint 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С/ПИП0x=013ИП11+В/ОИП1x=024ИП01П1-П0ПП06В/ОИП0П2ИП11-П1ПП06П1ИП21-П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 xfun test_tuples (x, y) = append_map (fn a = map (fn b = (b, a)) ` jota x) ` jota ymap 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:
jan@Beryllium:~/modula/rosetta$ ackerman
1       2       3       4       5       6       72       3       4       5       6       7       83       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+1If 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.nekoprompt$ neko ackermann.n 3 4Ackermann(3,4): 125prompt$ time neko ackermann.n 4 1Ackermann(4,1): Stack Overflowreal    0m31.475suser    0m31.460ssys     0m0.012sprompt$ time neko ackermann 3 10Ackermann(3,10): 8189real    0m1.865suser    0m1.862ssys     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 implicitmatch (which doesn't use the aliasA 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 theA 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 binarynumeric digits 66parse arg j_ k_ .if j_ = '' | j_ = '.' | \j_.datatype('w') then j_ = 3if k_ = '' | k_ = '.' | \k_.datatype('w') then k_ = 5loop m_ = 0 to j_  say  loop n_ = 0 to k_    say 'ackermann('m_','n_') =' ackermann(m_, n_).right(5)    end n_  end m_returnmethod 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>" flagas "newlisp -s 100000 ./ackermann.lsp".See http://www.newlisp.org/newlisp_manual.html#stack_size

Nim

from strutils import parseIntproc 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_functionfun ack(m, n: Int): Intdoif m == 0 then return n + 1if n == 0 then return ack(m-1,1)return ack(m-1, ack(m, n-1))endfor m in [0..3] dofor n in [0..6] doprint ack(m,n)endprint ""end

Output:

1234567234567835791113155132961125253509

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) = 1Ackermann(0, 1) = 2Ackermann(0, 2) = 3Ackermann(0, 3) = 4Ackermann(0, 4) = 5Ackermann(1, 0) = 2Ackermann(1, 1) = 3Ackermann(1, 2) = 4Ackermann(1, 3) = 5Ackermann(1, 4) = 6Ackermann(2, 0) = 3Ackermann(2, 1) = 5Ackermann(2, 2) = 7Ackermann(2, 3) = 9Ackermann(2, 4) = 11Ackermann(3, 0) = 5Ackermann(3, 1) = 13Ackermann(3, 2) = 29Ackermann(3, 3) = 61Ackermann(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 4001let 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 ofm andn 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_intlet 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 atail-recursive version:

let rec find_option h v =  try Some(Hashtbl.find h v)  with Not_found -> Nonelet 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_intlet 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 -> Nonelet 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));  endifendfunctionfor i = 0:3  disp(ackerman(i, 4));endfor

Oforth

: A( m n -- p )   m ifZero: [ n 1+ return ]   m 1- n ifZero: [ 1 ] else: [ A( m, n 1- ) ] A;

Ol

; simple version(define (A m n)    (cond        ((= m 0) (+ n 1))        ((= n 0) (A (- m 1) 1))        (else (A (- m 1) (A m (- n 1))))))(print "simple version (A 3 6): " (A 3 6)); smart (lazy) version(define (ints-from n)   (cons* n (delay (ints-from (+ n 1)))))(define (knuth-up-arrow a n b)  (let loop ((n n) (b b))    (cond ((= b 0) 1)          ((= n 1) (expt a b))          (else    (loop (- n 1) (loop n (- b 1)))))))(define (A+ m n)   (define (A-stream)      (cons*         (ints-from 1) ;; m = 0         (ints-from 2) ;; m = 1         ;; m = 2         (lmap (lambda (n)                  (+ (* 2 (+ n 1)) 1))            (ints-from 0))         ;; m = 3         (lmap (lambda (n)               (- (knuth-up-arrow 2 (- m 2) (+ n 3)) 3))            (ints-from 0))         ;; m = 4...         (delay (ldrop (A-stream) 3))))   (llref (llref (A-stream) m) n))(print "extended version (A 3 6): " (A+ 3 6))
Output:
simple version (A 3 6): 509extended version (A 3 6): 509

OOC

ack: func (m: Int, n: Int) -> Int {  if (m == 0) {    n + 1   } else if (n == 0) {    ack(m - 1, 1)  } else {    ack(m - 1, ack(m, n - 1))   }}main: func {  for (m in 0..4) {    for (n in 0..10) {      "ack(#{m}, #{n}) = #{ack(m, n)}" println()    }     }}

ooRexx

loop m = 0 to 3    loop n = 0 to 6        say "Ackermann("m", "n") =" ackermann(m, n)    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) = 1Ackermann(0, 1) = 2Ackermann(0, 2) = 3Ackermann(0, 3) = 4Ackermann(0, 4) = 5Ackermann(0, 5) = 6Ackermann(0, 6) = 7Ackermann(1, 0) = 2Ackermann(1, 1) = 3Ackermann(1, 2) = 4Ackermann(1, 3) = 5Ackermann(1, 4) = 6Ackermann(1, 5) = 7Ackermann(1, 6) = 8Ackermann(2, 0) = 3Ackermann(2, 1) = 5Ackermann(2, 2) = 7Ackermann(2, 3) = 9Ackermann(2, 4) = 11Ackermann(2, 5) = 13Ackermann(2, 6) = 15Ackermann(3, 0) = 5Ackermann(3, 1) = 13Ackermann(3, 2) = 29Ackermann(3, 3) = 61Ackermann(3, 4) = 125Ackermann(3, 5) = 253Ackermann(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  endin  {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.

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.


PascalABC.NET

function Ackermann(m,n: integer): integer;begin  if (m < 0) or (n < 0) then    raise new System.ArgumentOutOfRangeException();  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;begin  for var m := 0 to 3 do  for var n := 0 to 4 do    Println($'Ackermann({m}, {n}) = {Ackermann(m,n)}');end.
Output:
Ackermann(0, 0) = 1Ackermann(0, 1) = 2Ackermann(0, 2) = 3Ackermann(0, 3) = 4Ackermann(0, 4) = 5Ackermann(1, 0) = 2Ackermann(1, 1) = 3Ackermann(1, 2) = 4Ackermann(1, 3) = 5Ackermann(1, 4) = 6Ackermann(2, 0) = 3Ackermann(2, 1) = 5Ackermann(2, 2) = 7Ackermann(2, 3) = 9Ackermann(2, 4) = 11Ackermann(3, 0) = 5Ackermann(3, 1) = 13Ackermann(3, 2) = 29Ackermann(3, 3) = 61Ackermann(3, 4) = 125

Perl

We memoize calls toA to makeA(2,n) andA(3,n) feasible for larger values ofn.

{    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 125ack2(4,1) is 65533ack2(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

functionack(integerm,integern)ifm=0thenreturnn+1elsifm=1thenreturnn+2elsifm=2thenreturn2*n+3elsifm=3thenreturnpower(2,n+3)-3elsifm>0andn=0thenreturnack(m-1,1)elsereturnack(m-1,ack(m,n-1))endifendfunctionconstantlimit=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}atomt0=time()printf(1,"   0")forj=1tolimitdostringfmt=sprintf(" %%%dd",fmtlens[j+1])printf(1,fmt,j)endforprintf(1,"\n")fori=0to5doprintf(1,"%d:",i)forj=0toiff(i>=4?5-i:limit)dostringfmt=sprintf(" %%%dd",fmtlens[j+1])printf(1,fmt,{ack(i,j)})endforprintf(1,"\n")endfor
Output:
   0  1  2  3   4   5   6    7    8    9   10    11    12    13     14     15     16      17      18      19      20       21       22       230: 1  2  3  4   5   6   7    8    9   10   11    12    13    14     15     16     17      18      19      20      21       22       23       241: 2  3  4  5   6   7   8    9   10   11   12    13    14    15     16     17     18      19      20      21      22       23       24       252: 3  5  7  9  11  13  15   17   19   21   23    25    27    29     31     33     35      37      39      41      43       45       47       493: 5 13 29 61 125 253 509 1021 2045 4093 8189 16381 32765 65533 131069 262141 524285 1048573 2097149 4194301 8388605 16777213 33554429 671088614: 13 655335: 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.exwincludempfr.eprocedureack(integerm,mpzn)ifm=0thenmpz_add_ui(n,n,1)-- return n+1elsifm=1thenmpz_add_ui(n,n,2)-- return n+2elsifm=2thenmpz_mul_si(n,n,2)mpz_add_ui(n,n,3)-- return 2*n+3elsifm=3thenifnotmpz_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.)integerbn=mpz_sizeinbase(n,2)throw(sprintf("A(m,n) had n of %d bits; too large",bn))endifintegerni=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)-3elsifmpz_cmp_si(n,0)=0thenmpz_set_si(n,1)ack(m-1,n)-- return ack(m-1,1)elsempz_sub_ui(n,n,1)ack(m,n)ack(m-1,n)-- return ack(m-1,ack(m,n-1))endifendprocedureconstantlimit=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}}procedureackermann_tests()atomt0=time()atomn=mpz_init()printf(1,"   0")forj=1tolimitdostringfmt=sprintf(" %%%dd",fmtlens[j+1])printf(1,fmt,j)endforprintf(1,"\n")fori=0to5doprintf(1,"%d:",i)forj=0toiff(i>=4?5-i:limit)dompz_set_si(n,j)ack(i,n)stringfmt=sprintf(" %%%ds",fmtlens[j+1])printf(1,fmt,{mpz_get_str(n)})endforprintf(1,"\n")endforprintf(1,"\n")fori=1tolength(extras)dointeger{em,en}=extras[i]mpz_set_si(n,en)stringrestryack(em,n)res=mpz_get_str(n)integerlr=length(res)iflr>50thenres[21..-21]="..."res&=sprintf(" (%d digits)",lr)endifcatche-- ack(4,3), ack(5,1) and ack(6,0) all fail,            --                   just as they should dores="***ERROR***: "&e[E_USER]endtryprintf(1,"ack(%d,%d) %s\n",{em,en,res})endforn=mpz_free(n)printf(1,"\n")printf(1,"ackermann_tests completed (%s)\n\n",{elapsed(time()-t0)})endprocedureackermann_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       230: 1  2  3  4   5   6   7    8    9   10   11    12    13    14     15     16     17      18      19      20      21       22       23       241: 2  3  4  5   6   7   8    9   10   11   12    13    14    15     16     17     18      19      20      21      22       23       24       252: 3  5  7  9  11  13  15   17   19   21   23    25    27    29     31     33     35      37      39      41      43       45       47       493: 5 13 29 61 125 253 509 1021 2045 4093 8189 16381 32765 65533 131069 262141 524285 1048573 2097149 4194301 8388605 16777213 33554429 671088614: 13 655335: 65533ack(3,100) 10141204801825835211973625643005ack(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 largeackermann_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    endifenddef3 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): 65533a2(3,10000): 15960504935046067079..454194438340773675005digits = 3012CPU time 0.02 seconds.a2(4,2): 20035299304068464649..445587895905719156733digits = 19729CPU 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:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww

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) = 1A(1,0) = 2A(2,0) = 3A(3,0) = 5A(0,1) = 2A(1,1) = 3A(2,1) = 5A(3,1) = 13A(0,2) = 3A(1,2) = 4A(2,2) = 7A(3,2) = 29A(0,3) = 4A(1,3) = 5A(2,3) = 9A(3,3) = 61A(0,4) = 5A(1,4) = 6A(2,4) = 11A(3,4) = 125A(0,5) = 6A(1,5) = 7A(2,5) = 13A(3,5) = 253A(0,6) = 7A(1,6) = 8A(2,6) = 15A(3,6) = 509

Pluto

function ack(m,n)  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)) endendfor i = 0,3 do   for j = 0,8 do      print($"A({i},{j})={ack(i,j)}")   endend
Output:
A(0,0)=1A(0,1)=2A(0,2)=3A(0,3)=4A(0,4)=5A(0,5)=6A(0,6)=7A(0,7)=8A(0,8)=9A(1,0)=2A(1,1)=3A(1,2)=4A(1,3)=5A(1,4)=6A(1,5)=7A(1,6)=8A(1,7)=9A(1,8)=10A(2,0)=3A(2,1)=5A(2,2)=7A(2,3)=9A(2,4)=11A(2,5)=13A(2,6)=15A(2,7)=17A(2,8)=19A(3,0)=5A(3,1)=13A(3,2)=29A(3,3)=61A(3,4)=125A(3,5)=253A(3,6)=509A(3,7)=1021A(3,8)=2045

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 FUNCTIONFUNCTION 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 theFormat-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  72  3  4  5  6  7  83  5  7  9  11  13  155  13  29  61  125  253  509

Processing Python mode

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

from __future__ import print_functiondef setup():    for m in range(4):        for n in range(7):            print("{} ".format(ackermann(m, n)), end = "")        print()    # print('finished')def ackermann(m, n):    if m == 0:        return n + 1    elif m > 0 and n == 0:        return ackermann(m - 1, 1)    else:        return ackermann(m - 1, ackermann(m, n - 1))

Processing.R

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

setup <- function() {  for (m in 0:3) {    for (n in 0:4) {      stdout$print(paste(ackermann(m, n), " "))    }    stdout$println("")  }}ackermann <- function(m, n) {  if ( m == 0 ) {    return(n+1)  } else if ( n == 0 ) {    ackermann(m-1, 1)  } else {    ackermann(m-1, ackermann(m, n-1))  }}
Output:
1  2  3  4  5  2  3  4  5  6  3  5  7  9  11  5  13  29  61  125

Prolog

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

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

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

Pure

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

Pure Data

#N canvas 741 265 450 436 10;#X obj 83 111 t b l;#X obj 115 163 route 0;#X obj 115 185 + 1;#X obj 83 380 f;#X obj 161 186 swap;#X obj 161 228 route 0;#X obj 161 250 - 1;#X obj 161 208 pack;#X obj 115 314 t f f;#X msg 161 272 \$1 1;#X obj 115 142 t l;#X obj 207 250 swap;#X obj 273 271 - 1;#X obj 207 272 t f f;#X obj 207 298 - 1;#X obj 207 360 pack;#X obj 239 299 pack;#X obj 83 77 inlet;#X obj 83 402 outlet;#X connect 0 0 3 0;#X connect 0 1 10 0;#X connect 1 0 2 0;#X connect 1 1 4 0;#X connect 2 0 8 0;#X connect 3 0 18 0;#X connect 4 0 7 0;#X connect 4 1 7 1;#X connect 5 0 6 0;#X connect 5 1 11 0;#X connect 6 0 9 0;#X connect 7 0 5 0;#X connect 8 0 3 1;#X connect 8 1 15 1;#X connect 9 0 10 0;#X connect 10 0 1 0;#X connect 11 0 13 0;#X connect 11 1 12 0;#X connect 12 0 16 1;#X connect 13 0 14 0;#X connect 13 1 16 0;#X connect 14 0 15 0;#X connect 15 0 10 0;#X connect 16 0 10 0;#X connect 17 0 0 0;

PureBasic

Procedure.q Ackermann(m, n)  If m = 0    ProcedureReturn n + 1  ElseIf  n = 0    ProcedureReturn Ackermann(m - 1, 1)  Else    ProcedureReturn Ackermann(m - 1, Ackermann(m, n - 1))  EndIfEndProcedureDebug 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 dequedef 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 nsIn [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 floatIn [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:
6553319729 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]    ]]

Refal

$ENTRY Go {    = <Prout 'A(3,9) = ' <A 3 9>>;};A {    0   s.N   = <+ s.N 1>;    s.M 0     = <A <- s.M 1> 1>;    s.M s.N   = <A <- s.M 1> <A s.M <- s.N 1>>>;};
Output:
A(3,9) = 4093

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 3ackermann(2, 3) = 9$ node acker.bs.js 3 4ackermann(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=                       1Ackermann(0, 1)=                       2              calls=                       1Ackermann(0, 2)=                       3              calls=                       1Ackermann(0, 3)=                       4              calls=                       1Ackermann(0, 4)=                       5              calls=                       1Ackermann(0, 5)=                       6              calls=                       1Ackermann(0, 6)=                       7              calls=                       1Ackermann(0, 7)=                       8              calls=                       1Ackermann(0, 8)=                       9              calls=                       1Ackermann(0, 9)=                      10              calls=                       1Ackermann(0,10)=                      11              calls=                       1Ackermann(0,11)=                      12              calls=                       1Ackermann(0,12)=                      13              calls=                       1Ackermann(0,13)=                      14              calls=                       1Ackermann(0,14)=                      15              calls=                       1Ackermann(0,15)=                      16              calls=                       1Ackermann(0,16)=                      17              calls=                       1Ackermann(0,17)=                      18              calls=                       1Ackermann(0,18)=                      19              calls=                       1Ackermann(0,19)=                      20              calls=                       1Ackermann(0,20)=                      21              calls=                       1Ackermann(0,21)=                      22              calls=                       1Ackermann(0,22)=                      23              calls=                       1Ackermann(0,23)=                      24              calls=                       1Ackermann(0,24)=                      25              calls=                       1Ackermann(1, 0)=                       2              calls=                       2Ackermann(1, 1)=                       3              calls=                       4Ackermann(1, 2)=                       4              calls=                       6Ackermann(1, 3)=                       5              calls=                       8Ackermann(1, 4)=                       6              calls=                      10Ackermann(1, 5)=                       7              calls=                      12Ackermann(1, 6)=                       8              calls=                      14Ackermann(1, 7)=                       9              calls=                      16Ackermann(1, 8)=                      10              calls=                      18Ackermann(1, 9)=                      11              calls=                      20Ackermann(1,10)=                      12              calls=                      22Ackermann(1,11)=                      13              calls=                      24Ackermann(1,12)=                      14              calls=                      26Ackermann(1,13)=                      15              calls=                      28Ackermann(1,14)=                      16              calls=                      30Ackermann(1,15)=                      17              calls=                      32Ackermann(1,16)=                      18              calls=                      34Ackermann(1,17)=                      19              calls=                      36Ackermann(1,18)=                      20              calls=                      38Ackermann(1,19)=                      21              calls=                      40Ackermann(1,20)=                      22              calls=                      42Ackermann(1,21)=                      23              calls=                      44Ackermann(1,22)=                      24              calls=                      46Ackermann(1,23)=                      25              calls=                      48Ackermann(1,24)=                      26              calls=                      50Ackermann(2, 0)=                       3              calls=                       5Ackermann(2, 1)=                       5              calls=                      14Ackermann(2, 2)=                       7              calls=                      27Ackermann(2, 3)=                       9              calls=                      44Ackermann(2, 4)=                      11              calls=                      65Ackermann(2, 5)=                      13              calls=                      90Ackermann(2, 6)=                      15              calls=                     119Ackermann(2, 7)=                      17              calls=                     152Ackermann(2, 8)=                      19              calls=                     189Ackermann(2, 9)=                      21              calls=                     230Ackermann(2,10)=                      23              calls=                     275Ackermann(2,11)=                      25              calls=                     324Ackermann(2,12)=                      27              calls=                     377Ackermann(3, 0)=                       5              calls=                      15Ackermann(3, 1)=                      13              calls=                     106Ackermann(3, 2)=                      29              calls=                     541Ackermann(3, 3)=                      61              calls=                    2432Ackermann(3, 4)=                     125              calls=                   10307Ackermann(3, 5)=                     253              calls=                   42438Ackermann(3, 6)=                     509              calls=                  172233Ackermann(3, 7)=                    1021              calls=                  693964Ackermann(3, 8)=                    2045              calls=                 2785999

This output is from Regina and takes about 4 seconds. Running under ooRexx, the last line displayed is 'Ackermann(3, 6)...' and then the program just stops at (3,7). Looks like very deep recursion is more limited in ooRexx.

Regina reaches somewhat higher: (3,9) = 4094 in 12s and 11m calls, (3,10) = 8189 in 55s and 45m calls, (3,11) = 16381 in 250s and 180m calls. But (4,1) is also out of reach for Regina...

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=         1Ackermann(0, 1)=                       2              calls=         1Ackermann(0, 2)=                       3              calls=         1Ackermann(0, 3)=                       4              calls=         1Ackermann(0, 4)=                       5              calls=         1Ackermann(0, 5)=                       6              calls=         1Ackermann(0, 6)=                       7              calls=         1Ackermann(0, 7)=                       8              calls=         1Ackermann(0, 8)=                       9              calls=         1Ackermann(0, 9)=                      10              calls=         1Ackermann(0,10)=                      11              calls=         1Ackermann(0,11)=                      12              calls=         1Ackermann(0,12)=                      13              calls=         1Ackermann(0,13)=                      14              calls=         1Ackermann(0,14)=                      15              calls=         1Ackermann(0,15)=                      16              calls=         1Ackermann(0,16)=                      17              calls=         1Ackermann(0,17)=                      18              calls=         1Ackermann(0,18)=                      19              calls=         1Ackermann(0,19)=                      20              calls=         1Ackermann(0,20)=                      21              calls=         1Ackermann(0,21)=                      22              calls=         1Ackermann(0,22)=                      23              calls=         1Ackermann(0,23)=                      24              calls=         1Ackermann(0,24)=                      25              calls=         1Ackermann(1, 0)=                       2              calls=         2Ackermann(1, 1)=                       3              calls=         4Ackermann(1, 2)=                       4              calls=         6Ackermann(1, 3)=                       5              calls=         8Ackermann(1, 4)=                       6              calls=        10Ackermann(1, 5)=                       7              calls=        12Ackermann(1, 6)=                       8              calls=        14Ackermann(1, 7)=                       9              calls=        16Ackermann(1, 8)=                      10              calls=        18Ackermann(1, 9)=                      11              calls=        20Ackermann(1,10)=                      12              calls=        22Ackermann(1,11)=                      13              calls=        24Ackermann(1,12)=                      14              calls=        26Ackermann(1,13)=                      15              calls=        28Ackermann(1,14)=                      16              calls=        30Ackermann(1,15)=                      17              calls=        32Ackermann(1,16)=                      18              calls=        34Ackermann(1,17)=                      19              calls=        36Ackermann(1,18)=                      20              calls=        38Ackermann(1,19)=                      21              calls=        40Ackermann(1,20)=                      22              calls=        42Ackermann(1,21)=                      23              calls=        44Ackermann(1,22)=                      24              calls=        46Ackermann(1,23)=                      25              calls=        48Ackermann(1,24)=                      26              calls=        50Ackermann(2, 0)=                       3              calls=         5Ackermann(2, 1)=                       5              calls=         1Ackermann(2, 2)=                       7              calls=         1Ackermann(2, 3)=                       9              calls=         1Ackermann(2, 4)=                      11              calls=         1Ackermann(2, 5)=                      13              calls=         1Ackermann(2, 6)=                      15              calls=         1Ackermann(2, 7)=                      17              calls=         1Ackermann(2, 8)=                      19              calls=         1Ackermann(2, 9)=                      21              calls=         1Ackermann(2,10)=                      23              calls=         1Ackermann(2,11)=                      25              calls=         1Ackermann(2,12)=                      27              calls=         1Ackermann(3, 0)=                       5              calls=         2Ackermann(3, 1)=                      13              calls=         4Ackermann(3, 2)=                      29              calls=         6Ackermann(3, 3)=                      61              calls=         8Ackermann(3, 4)=                     125              calls=        10Ackermann(3, 5)=                     253              calls=        12Ackermann(3, 6)=                     509              calls=        14Ackermann(3, 7)=                    1021              calls=        16Ackermann(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=         1Ackermann(0, 1)=                       2              calls=         1Ackermann(0, 2)=                       3              calls=         1Ackermann(0, 3)=                       4              calls=         1Ackermann(0, 4)=                       5              calls=         1Ackermann(0, 5)=                       6              calls=         1Ackermann(0, 6)=                       7              calls=         1Ackermann(0, 7)=                       8              calls=         1Ackermann(0, 8)=                       9              calls=         1Ackermann(0, 9)=                      10              calls=         1Ackermann(0,10)=                      11              calls=         1Ackermann(0,11)=                      12              calls=         1Ackermann(0,12)=                      13              calls=         1Ackermann(0,13)=                      14              calls=         1Ackermann(0,14)=                      15              calls=         1Ackermann(0,15)=                      16              calls=         1Ackermann(0,16)=                      17              calls=         1Ackermann(0,17)=                      18              calls=         1Ackermann(0,18)=                      19              calls=         1Ackermann(0,19)=                      20              calls=         1Ackermann(0,20)=                      21              calls=         1Ackermann(0,21)=                      22              calls=         1Ackermann(0,22)=                      23              calls=         1Ackermann(0,23)=                      24              calls=         1Ackermann(0,24)=                      25              calls=         1Ackermann(1, 0)=                       2              calls=         1Ackermann(1, 1)=                       3              calls=         1Ackermann(1, 2)=                       4              calls=         1Ackermann(1, 3)=                       5              calls=         1Ackermann(1, 4)=                       6              calls=         1Ackermann(1, 5)=                       7              calls=         1Ackermann(1, 6)=                       8              calls=         1Ackermann(1, 7)=                       9              calls=         1Ackermann(1, 8)=                      10              calls=         1Ackermann(1, 9)=                      11              calls=         1Ackermann(1,10)=                      12              calls=         1Ackermann(1,11)=                      13              calls=         1Ackermann(1,12)=                      14              calls=         1Ackermann(1,13)=                      15              calls=         1Ackermann(1,14)=                      16              calls=         1Ackermann(1,15)=                      17              calls=         1Ackermann(1,16)=                      18              calls=         1Ackermann(1,17)=                      19              calls=         1Ackermann(1,18)=                      20              calls=         1Ackermann(1,19)=                      21              calls=         1Ackermann(1,20)=                      22              calls=         1Ackermann(1,21)=                      23              calls=         1Ackermann(1,22)=                      24              calls=         1Ackermann(1,23)=                      25              calls=         1Ackermann(1,24)=                      26              calls=         1Ackermann(2, 0)=                       3              calls=         1Ackermann(2, 1)=                       5              calls=         1Ackermann(2, 2)=                       7              calls=         1Ackermann(2, 3)=                       9              calls=         1Ackermann(2, 4)=                      11              calls=         1Ackermann(2, 5)=                      13              calls=         1Ackermann(2, 6)=                      15              calls=         1Ackermann(2, 7)=                      17              calls=         1Ackermann(2, 8)=                      19              calls=         1Ackermann(2, 9)=                      21              calls=         1Ackermann(2,10)=                      23              calls=         1Ackermann(2,11)=                      25              calls=         1Ackermann(2,12)=                      27              calls=         1Ackermann(3, 0)=                       5              calls=         1Ackermann(3, 1)=                      13              calls=         1Ackermann(3, 2)=                      29              calls=         1Ackermann(3, 3)=                      61              calls=         1Ackermann(3, 4)=                     125              calls=         1Ackermann(3, 5)=                     253              calls=         1Ackermann(3, 6)=                     509              calls=         1Ackermann(3, 7)=                    1021              calls=         1Ackermann(3, 8)=                    2045              calls=         1Ackermann(4, 0)=                      13              calls=         1Ackermann(4, 1)=                   65533              calls=         1Ackermann(4, 2)=89506130880933368E+19728              calls=         1

The last value is correct in magnitude, but not in value (only last digits plus exponent). Some other entries and Wikipedia give 2.0035...E+19728.
But leaving out the formatting and running with 20000 digits, the last value is correct shown in its full 19728 digits.
By the way, this version does not illustrate recursion anymore, because all workable values are captured as special values. Ackermann(4,2) = 2^65536-3 (19768 digits) and Ackerman(4,3) = 2^(2^65536)-3, far beyond REXX' (and other languages) capabilities in expressing numbers.

Ring

Translation of:C#
for m = 0 to 3        for n = 0 to 4                see "Ackermann(" + m + ", " + n + ") = " + Ackermann(m, n) + nl         nextnextfunc 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) = 1Ackermann(0, 1) = 2Ackermann(0, 2) = 3Ackermann(0, 3) = 4Ackermann(0, 4) = 5Ackermann(1, 0) = 2Ackermann(1, 1) = 3Ackermann(1, 2) = 4Ackermann(1, 3) = 5Ackermann(1, 4) = 6Ackermann(2, 0) = 3Ackermann(2, 1) = 5Ackermann(2, 2) = 7Ackermann(2, 3) = 9Ackermann(2, 4) = 11Ackermann(3, 0) = 5Ackermann(3, 1) = 13Ackermann(3, 2) = 29Ackermann(3, 3) = 61Ackermann(3, 4) = 125

RISC-V Assembly

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

RPL

Works with:RPL version HP49-C
« CASE      OVER NOTTHEN NIP 1 +END      DUP NOTTHEN DROP 1 - 1ACKEREND      OVER 1 - ROT ROT 1 -ACKERACKEREND» 'ACKER' STO
3 4ACKER
Output:
1: 125

Runs in 7 min 13 secs on a HP-50g. Speed could be increased by replacing every1 by1., which would force calculations to be made with floating-point numbers, but we would then lose the arbitrary precision.

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 ofINT, the classINTI 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 definesKnuth 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=1ackermann(0,1)=2  calls=1ackermann(0,2)=3  calls=1ackermann(0,3)=4  calls=1ackermann(0,4)=5  calls=1ackermann(0,5)=6  calls=1ackermann(0,6)=7  calls=1ackermann(1,0)=2  calls=2ackermann(1,1)=3  calls=4ackermann(1,2)=4  calls=6ackermann(1,3)=5  calls=8ackermann(1,4)=6  calls=10ackermann(1,5)=7  calls=12ackermann(1,6)=8  calls=14ackermann(2,0)=3  calls=5ackermann(2,1)=5  calls=14ackermann(2,2)=7  calls=27ackermann(2,3)=9  calls=44ackermann(2,4)=11  calls=65ackermann(2,5)=13  calls=90ackermann(2,6)=15  calls=119ackermann(3,0)=5  calls=15ackermann(3,1)=13  calls=106ackermann(3,2)=29  calls=541ackermann(3,3)=61  calls=2432ackermann(3,4)=125  calls=10307ackermann(3,5)=253  calls=42438ackermann(3,6)=509  calls=172233

Seed7

Basic version

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]

Improved version

$ include "seed7_05.s7i";  include "bigint.s7i";  const func bigInteger: ackermann (in bigInteger: m, in bigInteger: n) is func  result    var bigInteger: ackermann is 0_;  begin    case m of      when {0_}: ackermann := succ(n);      when {1_}: ackermann := n + 2_;      when {2_}: ackermann := 3_ + 2_ * n;      when {3_}: ackermann := 5_ + 8_ * pred(2_ ** ord(n));      otherwise:        if n = 0_ then          ackermann := ackermann(pred(m), 1_);        else          ackermann := ackermann(pred(m), ackermann(m, pred(n)));        end if;    end case;  end func;    const proc: main is func  local    var bigInteger: m is 0_;    var bigInteger: n is 0_;    var string: stri is "";  begin    for m range 0_ to 3_ do      for n range 0_ to 9_ do        writeln("A(" <& m <& ", " <& n <& ") = " <& ackermann(m, n));      end for;    end for;    writeln("A(4, 0) = " <& ackermann(4_, 0_));    writeln("A(4, 1) = " <& ackermann(4_, 1_));    stri := str(ackermann(4_, 2_));    writeln("A(4, 2) = (" <& length(stri) <& " digits)");    writeln(stri[1 len 80]);    writeln("...");    writeln(stri[length(stri) - 79 ..]);  end func;

Original source:[3]

Output:
A(0, 0) = 1A(0, 1) = 2A(0, 2) = 3A(0, 3) = 4A(0, 4) = 5A(0, 5) = 6A(0, 6) = 7A(0, 7) = 8A(0, 8) = 9A(0, 9) = 10A(1, 0) = 2A(1, 1) = 3A(1, 2) = 4A(1, 3) = 5A(1, 4) = 6A(1, 5) = 7A(1, 6) = 8A(1, 7) = 9A(1, 8) = 10A(1, 9) = 11A(2, 0) = 3A(2, 1) = 5A(2, 2) = 7A(2, 3) = 9A(2, 4) = 11A(2, 5) = 13A(2, 6) = 15A(2, 7) = 17A(2, 8) = 19A(2, 9) = 21A(3, 0) = 5A(3, 1) = 13A(3, 2) = 29A(3, 3) = 61A(3, 4) = 125A(3, 5) = 253A(3, 6) = 509A(3, 7) = 1021A(3, 8) = 2045A(3, 9) = 4093A(4, 0) = 13A(4, 1) = 65533A(4, 2) = (19729 digits)20035299304068464649790723515602557504478254755697514192650169737108940595563114...84717124577965048175856395072895337539755822087777506072339445587895905719156733

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) = 13Ackermann(3, 3) = 61Ackermann(2, 6) = 15Ackermann(1, 9) = 11Ackermann(0,12) = 13

Slate

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

Smalltalk

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

SmileBASIC

DEF ACK(M,N) IF M==0 THEN  RETURN N+1 ELSEIF M>0 AND N==0 THEN  RETURN ACK(M-1,1) ELSE  RETURN ACK(M-1,ACK(M,N-1)) 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 72 3 4 5 6 7 83 5 7 9 11 13 155 13 29 61 125 253 509

SNUSP

   /==!/==atoi=@@@-@-----#   |   |                          Ackermann function   |   |       /=========\!==\!====\  recursion:$,@/>,@/==ack=!\?\<+#    |   |     |   A(0,j) -> j+1 j   i           \<?\+>-@/#  |     |   A(i,0) -> A(i-1,1)                    \@\>@\->@/@\<-@/#  A(i,j) -> A(i-1,A(i,j-1))                      |  |     |            #      #  |  |     |             /+<<<-\              /-<<+>>\!=/  \=====|==!/========?\>>>=?/<<#            ?      ?           |   \<<<+>+>>-/            \>>+<<-/!==========/            #      #

One could employtail recursion elimination by replacing "@/#" with "/" in two places above.

SPAD

Works with:FriCAS, OpenAxiom, Axiom
NNI ==> NonNegativeIntegerA:(NNI,NNI) -> NNIA(m,n) ==  m=0 => n+1  m>0 and n=0 => A(m-1,1)  m>0 and n>0 => A(m-1,A(m,n-1))  -- Example  matrix [[A(i,j) for i in 0..3] for j in 0..3]
Output:
        +1  2  3  5 +        |           |        |2  3  5  13|   (1)  |           |        |3  4  7  29|        |           |        +4  5  9  61+                                             Type: Matrix(NonNegativeInteger)

SQL PL

Works with:Db2 LUW

version 9.7 or higher.

With SQL PL:

--#SET TERMINATOR @SET SERVEROUTPUT ON@CREATE OR REPLACE FUNCTION ACKERMANN(  IN M SMALLINT,  IN N BIGINT ) RETURNS BIGINT BEGIN  DECLARE RET BIGINT;  DECLARE STMT STATEMENT;  IF (M = 0) THEN   SET RET = N + 1;  ELSEIF (N = 0) THEN   PREPARE STMT FROM 'SET ? = ACKERMANN(? - 1, 1)';   EXECUTE STMT INTO RET USING M;  ELSE   PREPARE STMT FROM 'SET ? = ACKERMANN(? - 1, ACKERMANN(?, ? - 1))';   EXECUTE STMT INTO RET USING M, M, N;  END IF;  RETURN RET; END @ BEGIN DECLARE M SMALLINT DEFAULT 0; DECLARE N SMALLINT DEFAULT 0; DECLARE MAX_LEVELS CONDITION FOR SQLSTATE '54038'; DECLARE CONTINUE HANDLER FOR MAX_LEVELS BEGIN END; WHILE (N <= 6) DO  WHILE (M <= 3) DO   CALL DBMS_OUTPUT.PUT_LINE('ACKERMANN(' || M || ', ' || N || ') = ' || ACKERMANN(M, N));   SET M = M + 1;  END WHILE;  SET M = 0;  SET N = N + 1; END WHILE;END @

Output:

db2 -td@db2 => CREATE OR REPLACE FUNCTION ACKERMANN(...db2 (cont.) => END @DB20000I  The SQL command completed successfully.db2 => BEGINdb2 (cont.) => END...DB20000I  The SQL command completed successfully.ACKERMANN(0, 0) = 1ACKERMANN(1, 0) = 2ACKERMANN(2, 0) = 3ACKERMANN(3, 0) = 5ACKERMANN(0, 1) = 2ACKERMANN(1, 1) = 3ACKERMANN(2, 1) = 5ACKERMANN(3, 1) = 13ACKERMANN(0, 2) = 3ACKERMANN(1, 2) = 4ACKERMANN(2, 2) = 7ACKERMANN(3, 2) = 29ACKERMANN(0, 3) = 4ACKERMANN(1, 3) = 5ACKERMANN(2, 3) = 9ACKERMANN(3, 3) = 61ACKERMANN(0, 4) = 5ACKERMANN(1, 4) = 6ACKERMANN(2, 4) = 11ACKERMANN(0, 5) = 6ACKERMANN(1, 5) = 7ACKERMANN(2, 5) = 13ACKERMANN(0, 6) = 7ACKERMANN(1, 6) = 8ACKERMANN(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

Stax

{n!{sd^}{c!{dv1y!}{vscvsay!y!}?}?}Y
0 0y!P0 4y!P1 0y!P1 1y!P2 1y!P2 2y!P3 1y!P3 3y!P3 1y!P
Output:
152357136113

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

TAV

ackermann (n) (m) :  ? n = 0    :> m+1  ? m = 0    :> ackermann (n-1) 1  :> ackermann (n-1) ackermann n (m-1) \ = ackermann (n-1) (ackermann n (m-1))\ test itmain(params):+  p1 =: string params[1] as integer else 3  p2 =: string params[2] as integer else 5  print "ackermann(" _ p1 _ "," _ p2 _ ") = " _ ackermann p1 p2

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 calculatingack(4,3){\displaystyle {\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));}

Transd

#lang transdMainModule: {    Ack: Lambda<Int Int Int>(λ m Int() n Int()         (if (not m) (ret (+ n 1)))        (if (not n) (ret (exec Ack (- m 1) 1)))        (ret (exec Ack (- m 1) (exec Ack m (- n 1))))    ),    _start: (λ (textout (exec Ack 3 1) "\n"                         (exec Ack 3 2) "\n"                        (exec Ack 3 3)))}
Output:
132961

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 ) ) )ENDPROC 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) = 1ack(0, 1) = 2ack(0, 2) = 3ack(0, 3) = 4ack(0, 4) = 5ack(1, 0) = 2ack(1, 1) = 3ack(1, 2) = 4ack(1, 3) = 5ack(1, 4) = 6ack(2, 0) = 3ack(2, 1) = 5ack(2, 2) = 7ack(2, 3) = 9ack(2, 4) = 11ack(3, 0) = 5ack(3, 1) = 13ack(3, 2) = 29ack(3, 3) = 61ack(3, 4) = 125

Uiua

A ←|2.1 (  ◡(×+1>0:>0)  sw(+1pop|A-1:1pop:    |A-1:off(A:-1:)))A 1 1
Output:
3

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 72 3 4 5 6 7 83 5 7 9 11 13 155 13 29 61 125 253 509

Ursalang

let A = fn(m, n) {    if m == 0 {n + 1}    else if m > 0 and n == 0 {A(m - 1, 1)}    else {A(m - 1, A(m, n - 1))}} print(A(0, 0))print(A(3, 4))print(A(3, 1))

Ursala

Anonymous recursion is the usual way of doing things like this.

#import std#import natackermann = ~&al^?\successor@ar ~&ar?(   ^R/~&f ^/predecessor@al ^|R/~& ^|/~& predecessor,   ^|R/~& ~&\1+ predecessor@l)

test program for the first 4 by 7 numbers:

#cast %nLLtest = 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) = 1A(0,1) = 2A(0,2) = 3A(0,3) = 4A(0,4) = 5A(0,5) = 6A(0,6) = 7A(0,7) = 8A(0,8) = 9A(0,9) = 10A(1,0) = 2A(1,1) = 3A(1,2) = 4A(1,3) = 5A(1,4) = 6A(1,5) = 7A(1,6) = 8A(1,7) = 9A(1,8) = 10A(1,9) = 11A(2,0) = 3A(2,1) = 5A(2,2) = 7A(2,3) = 9A(2,4) = 11A(2,5) = 13A(2,6) = 15A(2,7) = 17A(2,8) = 19A(2,9) = 21A(3,0) = 5A(3,1) = 13A(3,2) = 29A(3,3) = 61A(3,4) = 125A(3,5) = 253A(3,6) = 509A(3,7) = 1021A(3,8) = 2045A(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 todepth 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 + 1ack = n + 1'~ depth = depth - 1elseif m > 0 and n = 0 then'~ depth = depth + 1ack = ack(m - 1, 1)'~ depth = depth - 1'~ elseif m > 0 and n > 0 thenelse'~ depth = depth + 1ack = ack(m - 1, ack(m, n - 1))'~ depth = depth - 1end ifend function
Invocation
wscript.echo ack( 1, 10 )'~ depth = 0wscript.echo ack( 2, 1 )'~ depth = 0wscript.echo ack( 4, 4 )
Output:
125C:\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

V (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) = 1Ackermann(0, 1) = 2Ackermann(0, 2) = 3Ackermann(0, 3) = 4Ackermann(0, 4) = 5Ackermann(0, 5) = 6Ackermann(1, 0) = 2Ackermann(1, 1) = 3Ackermann(1, 2) = 4Ackermann(1, 3) = 5Ackermann(1, 4) = 6Ackermann(2, 0) = 3Ackermann(2, 1) = 5Ackermann(2, 2) = 7Ackermann(2, 3) = 9Ackermann(3, 0) = 5Ackermann(3, 1) = 13Ackermann(3, 2) = 29Ackermann(4, 0) = 13Ackermann(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] = 5A[2, 3] = 9A[3, 3] = 61A[1, 5] = 7A[2, 5] = 13A[3, 5] = 253

X86 Assembly

Works with:nasm
Works with:windows
section .textglobal _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 overflowhappened 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));]; \Ackermannint 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: 10, 1: 20, 2: 30, 3: 40, 4: 50, 5: 60, 6: 70, 7: 80, 8: 91, 0: 21, 1: 31, 2: 41, 3: 51, 4: 61, 5: 71, 6: 81, 7: 91, 8: 102, 0: 32, 1: 52, 2: 72, 3: 92, 4: 112, 5: 132, 6: 152, 7: 172, 8: 193, 0: 53, 1: 133, 2: 293, 3: 613, 4: 1253, 5: 2533, 6: 5093, 7: 10213, 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 subprint 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 subsub 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/Mtxt_m_is:   db  "m=$"crlf:       db  10,13,'$'
Output:
m=0:     1     2     3     4     5     6     7     8     9m=1:     2     3     4     5     6     7     8     9    10m=2:     3     5     7     9    11    13    15    17    19m=3:     5    13    29    61   125   253   509  1021  2045

ZED

(a) m nM ZERO(=) m 0(add1) n(a) m nN ZERO(=) n 0(a) (sub1) m 1(a) m nDEFAULT#true(a) (sub1) m (a) m (sub1) n(add1) n=========#true(003) "+" n 1(sub1) n=========#true(003) "-" n 1(=) n1 n2=========#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
Retrieved from "https://rosettacode.org/wiki/Ackermann_function?oldid=382956"
Categories:
Hidden category:
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information
[8]ページ先頭
©2009-2025 Movatter.jp