Ackermann function: Difference between revisions

Line 34:

<syntaxhighlight lang=11l>F ack2(m, n) -> Int

<syntaxhighlight lang="11l">F ack2(m, n) -> Int

R I m == 0 {(n + 1)

} E I m == 1 {(n + 2)

Line 57:

The OS/360 linkage is a bit tricky with the S/360 basic instruction set.

To simplify, the program is recursive not reentrant.

<syntaxhighlight lang=360asm>* Ackermann function 07/09/2015

<syntaxhighlight lang="360asm">* Ackermann function 07/09/2015

&LAB XDECO &REG,&TARGET

.*-----------------------------------------------------------------*

Line 199:

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

<syntaxhighlight lang=68000devpac>;

<syntaxhighlight lang="68000devpac">;

; Ackermann function for Motorola 68000 under AmigaOs 2+ by Thorham

;

Line 317:

and <code>n ∊ [0,9)</code>, on a real 8080 this takes a little over two minutes.

<syntaxhighlight lang=8080asm> org 100h

<syntaxhighlight lang="8080asm"> org 100h

jmp demo

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Line 410:

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

<syntaxhighlight lang=asm> cpu 8086

<syntaxhighlight lang="asm"> cpu 8086

bits 16

org 100h

Line 479:

=={{header|8th}}==

\ Ackermann function, illustrating use of "memoization".

Line 571:

=={{header|AArch64 Assembly}}==

{{works with|as|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 */

Line 739:

=={{header|ABAP}}==

REPORT zhuberv_ackermann.

Line 789:

=={{header|Action!}}==

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

<syntaxhighlight lang=~~Action~~!>DEFINE MAXSIZE="1000"

<syntaxhighlight lang="action!">DEFINE MAXSIZE="1000"

CARD ARRAY stack(MAXSIZE)

CARD stacksize=[0]

Line 872:

=={{header|ActionScript}}==

<syntaxhighlight lang=actionscript>public function ackermann(m:uint, n:uint):uint

<syntaxhighlight lang="actionscript">public function ackermann(m:uint, n:uint):uint

{

if (m == 0)

Line 887:

=={{header|Ada}}==

<syntaxhighlight lang=ada>with Ada.Text_IO; use Ada.Text_IO;

<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO;

procedure Test_Ackermann is

Line 918:

open import Data.Nat

open import Data.Nat.Show

Line 935:

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

agda --compile Ackermann.agda

./Ackermann

Line 947:

=={{header|ALGOL 60}}==

<syntaxhighlight lang=algol60>begin

<syntaxhighlight lang="algol60">begin

integer procedure ackermann(m,n);value m,n;integer m,n;

ackermann:=if m=0 then n+1

Line 972:

{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}

<syntaxhighlight lang=algol68>PROC test ackermann = VOID:

<syntaxhighlight lang="algol68">PROC test ackermann = VOID:

BEGIN

PROC ackermann = (INT m, n)INT:

Line 1,003:

=={{header|ALGOL W}}==

<syntaxhighlight lang=algolw>begin

<syntaxhighlight lang="algolw">begin

integer procedure ackermann( integer value m,n ) ;

if m=0 then n+1

Line 1,023:

=={{header|APL}}==

<syntaxhighlight lang=~~APL~~>ackermann←{

<syntaxhighlight lang="apl">ackermann←{

0=1⊃⍵:1+2⊃⍵

0=2⊃⍵:∇(¯1+1⊃⍵)1

Line 1,031:

=={{header|AppleScript}}==

<syntaxhighlight lang=~~AppleScript~~>on ackermann(m, n)

<syntaxhighlight lang="applescript">on ackermann(m, n)

if m is equal to 0 then return n + 1

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

Line 1,039:

=={{header|Argile}}==

<syntaxhighlight lang=~~Argile~~>use std

<syntaxhighlight lang="argile">use std

for each (val nat n) from 0 to 6

Line 1,051:

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi or android 32 bits with application Termux}}

/* ARM assembly Raspberry PI or android 32 bits */

/* program ackermann.s */

Line 1,218:

=={{header|Arturo}}==

<syntaxhighlight lang=rebol>ackermann: function [m,n][

<syntaxhighlight lang="rebol">ackermann: function [m,n][

(m=0)? -> n+1 [

(n=0)? -> ackermann m-1 1

Line 1,255:

=={{header|ATS}}==

<syntaxhighlight lang=~~ATS~~>fun ackermann

<syntaxhighlight lang="ats">fun ackermann

{m,n:nat} .<m,n>.

(m: int m, n: int n): Nat =

Line 1,265:

=={{header|AutoHotkey}}==

<syntaxhighlight lang=~~AutoHotkey~~>A(m, n) {

<syntaxhighlight lang="autohotkey">A(m, n) {

If (m > 0) && (n = 0)

Return A(m-1,1)

Line 1,279:

=={{header|AutoIt}}==

=== Classical version ===

<syntaxhighlight lang=autoit>Func Ackermann($m, $n)

<syntaxhighlight lang="autoit">Func Ackermann($m, $n)

If ($m = 0) Then

Return $n+1

Line 1,295:

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.

<syntaxhighlight lang=autoit>Global $ackermann[2047][2047] ; Set the size to whatever you want

<syntaxhighlight lang="autoit">Global $ackermann[2047][2047] ; Set the size to whatever you want

Func Ackermann($m, $n)

If ($ackermann[$m][$n] <> 0) Then

Line 1,315:

=={{header|AWK}}==

<syntaxhighlight lang=awk>function ackermann(m, n)

<syntaxhighlight lang="awk">function ackermann(m, n)

{

if ( m == 0 ) {

Line 1,335:

=={{header|Babel}}==

<syntaxhighlight lang=babel>main:

<syntaxhighlight lang="babel">main:

{((0 0) (0 1) (0 2)

(0 3) (0 4) (1 0)

Line 1,391:

=={{header|BASIC}}==

==={{header|Applesoft BASIC}}===

<syntaxhighlight lang=basic>100 DIM R%(2900),M(2900),N(2900)

<syntaxhighlight lang="basic">100 DIM R%(2900),M(2900),N(2900)

110 FOR M = 0 TO 3

120 FOR N = 0 TO 4

Line 1,417:

==={{header|BASIC256}}===

<syntaxhighlight lang=basic256>dim stack(5000, 3) # BASIC-256 lacks functions (as of ver. 0.9.6.66)

<syntaxhighlight lang="basic256">dim stack(5000, 3) # BASIC-256 lacks functions (as of ver. 0.9.6.66)

stack[0,0] = 3 # M

stack[0,1] = 7 # N

Line 1,455:

</pre>

<syntaxhighlight lang=basic256># BASIC256 since 0.9.9.1 supports functions

<syntaxhighlight lang="basic256"># BASIC256 since 0.9.9.1 supports functions

for m = 0 to 3

for n = 0 to 4

Line 1,499:

==={{header|BBC BASIC}}===

<syntaxhighlight lang=bbcbasic> PRINT FNackermann(3, 7)

<syntaxhighlight lang="bbcbasic"> PRINT FNackermann(3, 7)

END

Line 1,511:

BASIC runs out of stack space very quickly.

The call <tt>ack(3, 4)</tt> gives a stack error.

<syntaxhighlight lang=qbasic>DECLARE FUNCTION ack! (m!, n!)

<syntaxhighlight lang="qbasic">DECLARE FUNCTION ack! (m!, n!)

FUNCTION ack (m!, n!)

Line 1,526:

=={{header|Batch File}}==

Had trouble with this, so called in the gurus at [http://stackoverflow.com/questions/2680668/what-is-wrong-with-this-recursive-windows-cmd-script-it-wont-do-ackermann-prope StackOverflow]. Thanks to Patrick Cuff for pointing out where I was going wrong.

<syntaxhighlight lang=dos>::Ackermann.cmd

<syntaxhighlight lang="dos">::Ackermann.cmd

@echo off

set depth=0

Line 1,558:

if %depth%==0 ( exit %t% ) else ( exit /b %t% )</syntaxhighlight>

Because of the <code>exit</code> statements, running this bare closes one's shell, so this test routine handles the calling of Ackermann.cmd

<syntaxhighlight lang=dos>::Ack.cmd

<syntaxhighlight lang="dos">::Ack.cmd

@echo off

cmd/c ackermann.cmd %1 %2

Line 1,579:

<syntaxhighlight lang=bc>define ack(m, n) {

<syntaxhighlight lang="bc">define ack(m, n) {

if ( m == 0 ) return (n+1);

if ( n == 0 ) return (ack(m-1, 1));

Line 1,593:

=={{header|BCPL}}==

<syntaxhighlight lang=~~BCPL~~>GET "libhdr"

<syntaxhighlight lang="bcpl">GET "libhdr"

LET ack(m, n) = m=0 -> n+1,

Line 1,609:

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

Line 1,625:

Each block of <code>1FJ</code> or <code>1fFJ</code> in the code is a call of the Ackermann function itself.

<syntaxhighlight lang=beeswax>Ag~1?Lp1~2@g'p?g?Pf1FJ Ackermann function. if m=0 => run Ackermann function (m, n+1)

<syntaxhighlight lang="beeswax">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))

Line 1,631:

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

Line 1,651:

Since Befunge-93 doesn't have recursive capabilities we need to use an iterative algorithm.

<syntaxhighlight lang=befunge>&>&>vvg0>#0\#-:#1_1v

<syntaxhighlight lang="befunge">&>&>vvg0>#0\#-:#1_1v

@v:\<vp0 0:-1<\+<

^>00p>:#^_$1+\:#^_$.

Line 1,658:

===Befunge-98===

<syntaxhighlight lang=befunge>r[1&&{0

<syntaxhighlight lang="befunge">r[1&&{0

>v

j

Line 1,670:

=={{header|BQN}}==

<syntaxhighlight lang=~~BQN~~>A ← {

<syntaxhighlight lang="bqn">A ← {

A 0‿n: n+1;

A m‿0: A (m-1)‿1;

Line 1,676:

}</syntaxhighlight>

Example usage:

<lang> A 0‿3

<syntaxhighlight lang="text"> A 0‿3

4

A 1‿4

Line 1,690:

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)

<syntaxhighlight lang=bracmat>( Ack

<syntaxhighlight lang="bracmat">( Ack

= m n

. !arg:(?m,?n)

Line 1,705:

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

<syntaxhighlight lang=bracmat> ( A

<syntaxhighlight lang="bracmat"> ( A

= m n value key eq chain

, find insert future stack va val

Line 1,774:

</pre>

The last solution is a recursive solution that employs some extra formulas, inspired by the Common Lisp solution further down.

<syntaxhighlight lang=bracmat>( AckFormula

<syntaxhighlight lang="bracmat">( AckFormula

= m n

. !arg:(?m,?n)

Line 1,792:

=={{header|Brat}}==

<syntaxhighlight lang=brat>ackermann = { m, n |

<syntaxhighlight lang="brat">ackermann = { m, n |

when { m == 0 } { n + 1 }

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

Line 1,802:

=={{header|C}}==

Straightforward implementation per Ackermann definition:

<syntaxhighlight lang=C>#include <stdio.h>

<syntaxhighlight lang="c">#include <stdio.h>

int ackermann(int m, int n)

Line 1,842:

A(4, 1) = 65533</pre>

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

<syntaxhighlight lang=C>#include <stdio.h>

<syntaxhighlight lang="c">#include <stdio.h>

#include <stdlib.h>

#include <string.h>

Line 1,908:

A couple of alternative approaches...

<syntaxhighlight lang=C>/* Thejaka Maldeniya */

<syntaxhighlight lang="c">/* Thejaka Maldeniya */

#include <conio.h>

Line 2,010:

A couple of more iterative techniques...

<syntaxhighlight lang=C>/* Thejaka Maldeniya */

<syntaxhighlight lang="c">/* Thejaka Maldeniya */

#include <conio.h>

Line 2,163:

===Basic Version===

<syntaxhighlight lang=csharp>using System;

<syntaxhighlight lang="csharp">using System;

class Program

{

Line 2,220:

===Efficient Version===

using System;

using System.Numerics;

Line 2,354:

===Basic version===

<syntaxhighlight lang=cpp>#include <iostream>

<syntaxhighlight lang="cpp">#include <iostream>

unsigned int ackermann(unsigned int m, unsigned int n) {

Line 2,379:

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

g++ -std=c++11 -I /path/to/boost ackermann.cpp.

<syntaxhighlight lang=cpp>#include <iostream>

<syntaxhighlight lang="cpp">#include <iostream>

#include <sstream>

#include <string>

Line 2,483:

=={{header|Chapel}}==

<syntaxhighlight lang=chapel>proc A(m:int, n:int):int {

<syntaxhighlight lang="chapel">proc A(m:int, n:int):int {

if m == 0 then

return n + 1;

Line 2,493:

=={{header|Clay}}==

<syntaxhighlight lang=~~Clay~~>ackermann(m, n) {

<syntaxhighlight lang="clay">ackermann(m, n) {

if(m == 0)

return n + 1;

Line 2,504:

=={{header|CLIPS}}==

'''Functional solution'''

<syntaxhighlight lang=clips>(deffunction ackerman

<syntaxhighlight lang="clips">(deffunction ackerman

(?m ?n)

(if (= 0 ?m)

Line 2,525:

</pre>

'''Fact-based solution'''

<syntaxhighlight lang=clips>(deffacts solve-items

<syntaxhighlight lang="clips">(deffacts solve-items

(solve 0 4)

(solve 1 4)

Line 2,620:

=={{header|Clojure}}==

<syntaxhighlight lang=clojure>(defn ackermann [m n]

<syntaxhighlight lang="clojure">(defn ackermann [m n]

(cond (zero? m) (inc n)

(zero? n) (ackermann (dec m) 1)

Line 2,626:

=={{header|CLU}}==

<syntaxhighlight lang=clu>% Ackermann function

<syntaxhighlight lang="clu">% Ackermann function

ack = proc (m, n: int) returns (int)

if m=0 then return(n+1)

Line 2,652:

=={{header|COBOL}}==

<syntaxhighlight lang=cobol> IDENTIFICATION DIVISION.

<syntaxhighlight lang="cobol"> IDENTIFICATION DIVISION.

PROGRAM-ID. Ackermann.

Line 2,686:

=={{header|CoffeeScript}}==

<syntaxhighlight lang=coffeescript>ackermann = (m, n) ->

<syntaxhighlight lang="coffeescript">ackermann = (m, n) ->

if m is 0 then n + 1

else if m > 0 and n is 0 then ackermann m - 1, 1

Line 2,692:

=={{header|Comal}}==

<syntaxhighlight lang=comal>0010 //

<syntaxhighlight lang="comal">0010 //

0020 // Ackermann function

0030 //

Line 2,716:

=={{header|Common Lisp}}==

<syntaxhighlight lang=lisp>(defun ackermann (m n)

<syntaxhighlight lang="lisp">(defun ackermann (m n)

(cond ((zerop m) (1+ n))

((zerop n) (ackermann (1- m) 1))

(t (ackermann (1- m) (ackermann m (1- n))))))</syntaxhighlight>

More elaborately:

<syntaxhighlight lang=lisp>(defun ackermann (m n)

<syntaxhighlight lang="lisp">(defun ackermann (m n)

(case m ((0) (1+ n))

((1) (+ 2 n))

Line 2,744:

=={{header|Component Pascal}}==

BlackBox Component Builder

MODULE NpctAckerman;

Line 2,785:

=={{header|Coq}}==

<syntaxhighlight lang=coq>Require Import Arith.

<syntaxhighlight lang="coq">Require Import Arith.

Fixpoint A m := fix A_m n :=

match m with

Line 2,796:

end.</syntaxhighlight>

<syntaxhighlight lang=coq>Require Import Utf8.

<syntaxhighlight lang="coq">Require Import Utf8.

Section FOLD.

Line 2,813:

=={{header|Crystal}}==

<syntaxhighlight lang=ruby>def ack(m, n)

<syntaxhighlight lang="ruby">def ack(m, n)

if m == 0

n + 1

Line 2,839:

=={{header|D}}==

===Basic version===

<syntaxhighlight lang=d>ulong ackermann(in ulong m, in ulong n) pure nothrow @nogc {

<syntaxhighlight lang="d">ulong ackermann(in ulong m, in ulong n) pure nothrow @nogc {

if (m == 0)

return n + 1;

Line 2,853:

===More Efficient Version===

<syntaxhighlight lang=d>import std.stdio, std.bigint, std.conv;

<syntaxhighlight lang="d">import std.stdio, std.bigint, std.conv;

BigInt ipow(BigInt base, BigInt exp) pure nothrow {

Line 2,930:

=={{header|Dart}}==

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

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

<syntaxhighlight lang="dart">int A(int m, int n) => m==0 ? n+1 : n==0 ? A(m-1,1) : A(m-1,A(m,n-1));

main() {

Line 2,946:

=={{header|Dc}}==

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

<syntaxhighlight lang=dc>[ # todo: n 0 -- n+1 and break 2 levels

<syntaxhighlight lang="dc">[ # todo: n 0 -- n+1 and break 2 levels

+ 1 + # n+1

q

Line 2,975:

=={{header|Delphi}}==

<syntaxhighlight lang=delphi>function Ackermann(m,n:Int64):Int64;

<syntaxhighlight lang="delphi">function Ackermann(m,n:Int64):Int64;

begin

if m = 0 then

Line 2,986:

=={{header|Draco}}==

<syntaxhighlight lang=draco>/* Ackermann function */

<syntaxhighlight lang="draco">/* Ackermann function */

proc ack(word m, n) word:

if m=0 then n+1

Line 3,011:

=={{header|DWScript}}==

<syntaxhighlight lang=delphi>function Ackermann(m, n : Integer) : Integer;

<syntaxhighlight lang="delphi">function Ackermann(m, n : Integer) : Integer;

begin

if m = 0 then

Line 3,021:

=={{header|Dylan}}==

<syntaxhighlight lang=dylan>define method ack(m == 0, n :: <integer>)

<syntaxhighlight lang="dylan">define method ack(m == 0, n :: <integer>)

n + 1

end;

Line 3,029:

=={{header|E}}==

<syntaxhighlight lang=e>def A(m, n) {

<syntaxhighlight lang="e">def A(m, n) {

return if (m <=> 0) { n+1 } \

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

Line 3,036:

=={{header|EasyLang}}==

<lang>func ackerm m n . r .

<syntaxhighlight lang="text">func ackerm m n . r .

if m = 0

r = n + 1

Line 3,050:

=={{header|Egel}}==

def ackermann =

[ 0 N -> N + 1

Line 3,062:

[https://github.com/ljr1981/rosettacode_answers/blob/main/testing/rc_ackerman/rc_ackerman_test_set.e Test of Example code]

class

ACKERMAN_EXAMPLE

Line 3,089:

=={{header|Ela}}==

<syntaxhighlight lang=ela>ack 0 n = n+1

<syntaxhighlight lang="ela">ack 0 n = n+1

ack m 0 = ack (m - 1) 1

ack m n = ack (m - 1) <| ack m <| n - 1</syntaxhighlight>

Line 3,095:

=={{header|Elena}}==

ELENA 4.x :

<syntaxhighlight lang=elena>import extensions;

<syntaxhighlight lang="elena">import extensions;

ackermann(m,n)

Line 3,154:

=={{header|Elixir}}==

<syntaxhighlight lang=elixir>defmodule Ackermann do

<syntaxhighlight lang="elixir">defmodule Ackermann do

def ack(0, n), do: n + 1

def ack(m, 0), do: ack(m - 1, 1)

Line 3,173:

=={{header|Emacs Lisp}}==

<syntaxhighlight lang=lisp>(defun ackermann (m n)

<syntaxhighlight lang="lisp">(defun ackermann (m n)

(cond ((zerop m) (1+ n))

((zerop n) (ackermann (1- m) 1))

Line 3,181:

=={{header|Erlang}}==

-module(ackermann).

-export([ackermann/2]).

Line 3,197:

substituted with the new ERRE control statements.

PROGRAM ACKERMAN

Line 3,270:

=={{header|Euler Math Toolbox}}==

>M=zeros(1000,1000);

>function map A(m,n) ...

Line 3,291:

=={{header|Euphoria}}==

This is based on the [[VBScript]] example.

<syntaxhighlight lang=~~Euphoria~~>function ack(atom m, atom n)

<syntaxhighlight lang="euphoria">function ack(atom m, atom n)

if m = 0 then

return n + 1

Line 3,309:

=={{header|Ezhil}}==

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

Line 3,352:

=={{header|F_Sharp|F#}}==

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

<syntaxhighlight lang=fsharp>let rec ackermann m n =

<syntaxhighlight lang="fsharp">let rec ackermann m n =

match m, n with

| 0, n -> n + 1

Line 3,361:

printfn "%A" (ackermann (int fsi.CommandLineArgs.[1]) (int fsi.CommandLineArgs.[2]))</syntaxhighlight>

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

<syntaxhighlight lang=fsharp>let ackermann M N =

<syntaxhighlight lang="fsharp">let ackermann M N =

let rec acker (m, n, k) =

match m,n with

Line 3,370:

=={{header|Factor}}==

<syntaxhighlight lang=factor>USING: kernel math locals combinators ;

<syntaxhighlight lang="factor">USING: kernel math locals combinators ;

IN: ackermann

Line 3,381:

=={{header|Falcon}}==

<syntaxhighlight lang=falcon>function ackermann( m, n )

<syntaxhighlight lang="falcon">function ackermann( m, n )

if m == 0: return( n + 1 )

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

Line 3,404:

=={{header|FALSE}}==

<syntaxhighlight lang=false>[$$[%

<syntaxhighlight lang="false">[$$[%

\$$[%

1-\$@@a;! { i j -> A(i-1, A(i, j-1)) }

Line 3,418:

=={{header|Fantom}}==

<syntaxhighlight lang=fantom>class Main

<syntaxhighlight lang="fantom">class Main

{

// assuming m,n are positive

Line 3,476:

=={{header|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:

<syntaxhighlight lang=qbasic>#APPTYPE CONSOLE

<syntaxhighlight lang="qbasic">#APPTYPE CONSOLE

TestAckermann()

Line 3,497:

END FUNCTION

DYNC AckermannC(m AS INTEGER, n AS INTEGER) AS INTEGER</syntaxhighlight><syntaxhighlight lang=C>

DYNC AckermannC(m AS INTEGER, n AS INTEGER) AS INTEGER</syntaxhighlight><syntaxhighlight lang="c">

int Ackermann(int m, int n)

{

Line 3,508:

{

return Ackermann(m, n);

}</syntaxhighlight><syntaxhighlight lang=qbasic>

}</syntaxhighlight><syntaxhighlight lang="qbasic">

END DYNC

DYNASM AckermannA(m AS INTEGER, n AS INTEGER) AS INTEGER</syntaxhighlight><syntaxhighlight lang=asm>

DYNASM AckermannA(m AS INTEGER, n AS INTEGER) AS INTEGER</syntaxhighlight><syntaxhighlight lang="asm">

ENTER 0, 0

INVOKE Ackermann, m, n

Line 3,547:

LEAVE

RET 8

</syntaxhighlight><syntaxhighlight lang=qbasic>END DYNASM</syntaxhighlight>

</syntaxhighlight><syntaxhighlight lang="qbasic">END DYNASM</syntaxhighlight>

Line 3,560:

=={{header|Fermat}}==

<syntaxhighlight lang=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.;

<syntaxhighlight lang="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)</syntaxhighlight>

Line 3,568:

=={{header|Forth}}==

<syntaxhighlight lang=forth>: acker ( m n -- u )

<syntaxhighlight lang="forth">: acker ( m n -- u )

over 0= IF nip 1+ EXIT THEN

swap 1- swap ( m-1 n -- )

Line 3,577:

FORTH> 3 4 acker . 125 ok</pre>

An optimized version:

<syntaxhighlight lang=forth>: ackermann ( m n -- u )

<syntaxhighlight lang="forth">: ackermann ( m n -- u )

over ( case statement)

0 over = if drop nip 1+ else

Line 3,594:

=={{header|Fortran}}==

<syntaxhighlight lang=fortran>PROGRAM EXAMPLE

<syntaxhighlight lang="fortran">PROGRAM EXAMPLE

IMPLICIT NONE

Line 3,626:

=={{header|FreeBASIC}}==

<syntaxhighlight lang=freebasic>' version 28-10-2016

<syntaxhighlight lang="freebasic">' version 28-10-2016

' compile with: fbc -s console

' to do A(4, 2) the stack size needs to be increased

Line 3,675:

=={{header|FunL}}==

<syntaxhighlight lang=funl>def

<syntaxhighlight lang="funl">def

ackermann( 0, n ) = n + 1

ackermann( m, 0 ) = ackermann( m - 1, 1 )

Line 3,710:

=={{header|Futhark}}==

fun ackermann(m: int, n: int): int =

if m == 0 then n + 1

Line 3,718:

=={{header|FutureBasic}}==

include "NSLog.incl"

Line 3,800:

=={{header|Gambas}}==

<syntaxhighlight lang=gambas>Public Function Ackermann(m As Float, n As Float) As Float

<syntaxhighlight lang="gambas">Public Function Ackermann(m As Float, n As Float) As Float

If m = 0 Then

Return n + 1

Line 3,820:

=={{header|GAP}}==

<syntaxhighlight lang=gap>ack := function(m, n)

<syntaxhighlight lang="gap">ack := function(m, n)

if m = 0 then

return n + 1;

Line 3,833:

=={{header|Genyris}}==

<syntaxhighlight lang=genyris>def A (m n)

<syntaxhighlight lang="genyris">def A (m n)

cond

(equal? m 0)

Line 3,845:

=={{header|GML}}==

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

<syntaxhighlight lang=~~GML~~>///ackermann(m,n)

<syntaxhighlight lang="gml">///ackermann(m,n)

var m, n;

m = argument0;

Line 3,863:

=={{header|gnuplot}}==

<syntaxhighlight lang=gnuplot>A (m, n) = m == 0 ? n + 1 : n == 0 ? A (m - 1, 1) : A (m - 1, A (m, n - 1))

<syntaxhighlight lang="gnuplot">A (m, n) = m == 0 ? n + 1 : n == 0 ? A (m - 1, 1) : A (m - 1, A (m, n - 1))

print A (0, 4)

print A (1, 4)

Line 3,876:

=={{header|Go}}==

===Classic version===

<syntaxhighlight lang=go>func Ackermann(m, n uint) uint {

<syntaxhighlight lang="go">func Ackermann(m, n uint) uint {

switch 0 {

case m:

Line 3,886:

}</syntaxhighlight>

===Expanded version===

<syntaxhighlight lang=go>func Ackermann2(m, n uint) uint {

<syntaxhighlight lang="go">func Ackermann2(m, n uint) uint {

switch {

case m == 0:

Line 3,902:

}</syntaxhighlight>

===Expanded version with arbitrary precision===

<syntaxhighlight lang=go>package main

<syntaxhighlight lang="go">package main

import (

Line 4,005:

=={{header|Golfscript}}==

<syntaxhighlight lang=golfscript>{

<syntaxhighlight lang="golfscript">{

:_n; :_m;

_m 0= {_n 1+}

Line 4,015:

=={{header|Groovy}}==

<syntaxhighlight lang=groovy>def ack ( m, n ) {

<syntaxhighlight lang="groovy">def ack ( m, n ) {

assert m >= 0 && n >= 0 : 'both arguments must be non-negative'

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

}</syntaxhighlight>

Test program:

<syntaxhighlight lang=groovy>def ackMatrix = (0..3).collect { m -> (0..8).collect { n -> ack(m, n) } }

<syntaxhighlight lang="groovy">def ackMatrix = (0..3).collect { m -> (0..8).collect { n -> ack(m, n) } }

ackMatrix.each { it.each { elt -> printf "%7d", elt }; println() }</syntaxhighlight>

Line 4,030:

=={{header|Hare}}==

<syntaxhighlight lang=hare>use fmt;

<syntaxhighlight lang="hare">use fmt;

fn ackermann(m: u64, n: u64) u64 = {

Line 4,052:

=={{header|Haskell}}==

<syntaxhighlight lang=haskell>ack :: Int -> Int -> Int

<syntaxhighlight lang="haskell">ack :: Int -> Int -> Int

ack 0 n = succ n

ack m 0 = ack (pred m) 1

Line 4,064:

Generating a list instead:

<syntaxhighlight lang=haskell>import Data.List (mapAccumL)

<syntaxhighlight lang="haskell">import Data.List (mapAccumL)

-- everything here are [Int] or [[Int]], which would overflow

Line 4,076:

=={{header|Haxe}}==

<syntaxhighlight lang=haxe>class RosettaDemo

<syntaxhighlight lang="haxe">class RosettaDemo

{

static public function main()

Line 4,098:

=={{header|Hoon}}==

|= [m=@ud n=@ud]

?: =(m 0)

Line 4,111:

Taken from the public domain Icon Programming Library's [http://www.cs.arizona.edu/icon/library/procs/memrfncs.htm acker in memrfncs],

written by Ralph E. Griswold.

<syntaxhighlight lang=~~Icon~~>procedure acker(i, j)

<syntaxhighlight lang="icon">procedure acker(i, j)

static memory

Line 4,144:

=={{header|Idris}}==

<syntaxhighlight lang=idris>A : Nat -> Nat -> Nat

<syntaxhighlight lang="idris">A : Nat -> Nat -> Nat

A Z n = S n

A (S m) Z = A m (S Z)

Line 4,151:

=={{header|Ioke}}==

<syntaxhighlight lang=ioke>ackermann = method(m,n,

<syntaxhighlight lang="ioke">ackermann = method(m,n,

cond(

m zero?, n succ,

Line 4,160:

=={{header|J}}==

As posted at the [[j:Essays/Ackermann%27s%20Function|J wiki]]

<syntaxhighlight lang=j>ack=: c1`c1`c2`c3 @. (#.@,&*) M.

<syntaxhighlight lang="j">ack=: c1`c1`c2`c3 @. (#.@,&*) M.

c1=: >:@] NB. if 0=x, 1+y

c2=: <:@[ ack 1: NB. if 0=y, (x-1) ack 1

c3=: <:@[ ack [ ack <:@] NB. else, (x-1) ack x ack y-1</syntaxhighlight>

<syntaxhighlight lang=j> 0 ack 3

<syntaxhighlight lang="j"> 0 ack 3

4

1 ack 3

Line 4,178:

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.

<syntaxhighlight lang=j> 0 1 2 3 Ack 0 1 2 3 4 5 6 7

<syntaxhighlight lang="j"> 0 1 2 3 Ack 0 1 2 3 4 5 6 7

1 2 3 4 5 6 7 8

2 3 4 5 6 7 8 9

Line 4,199:

A structured derivation of Ack follows:

<syntaxhighlight lang=j> o=. @: NB. Composition of verbs (functions)

<syntaxhighlight lang="j"> o=. @: NB. Composition of verbs (functions)

x=. o[ NB. Composing the left noun (argument)

Line 4,229:

=={{header|Java}}==

[[Category:Arbitrary precision]]

<syntaxhighlight lang=java>import java.math.BigInteger;

<syntaxhighlight lang="java">import java.math.BigInteger;

public static BigInteger ack(BigInteger m, BigInteger n) {

Line 4,239:

<syntaxhighlight lang=java5>@FunctionalInterface

<syntaxhighlight lang="java5">@FunctionalInterface

public interface FunctionalField<FIELD extends Enum<?>> {

public Object untypedField(FIELD field);

Line 4,248:

}

}</syntaxhighlight>

<syntaxhighlight lang=java5>import java.util.function.BiFunction;

<syntaxhighlight lang="java5">import java.util.function.BiFunction;

import java.util.function.Function;

import java.util.function.Predicate;

Line 4,294:

}

}</syntaxhighlight>

<syntaxhighlight lang=java5>import java.math.BigInteger;

<syntaxhighlight lang="java5">import java.math.BigInteger;

import java.util.Stack;

import java.util.function.BinaryOperator;

Line 4,440:

}</syntaxhighlight>

<syntaxhighlight lang=java5>/*

<syntaxhighlight lang="java5">/*

* Source https://stackoverflow.com/a/51092690/5520417

*/

Line 4,834:

=={{header|JavaScript}}==

===ES5===

<syntaxhighlight lang=javascript>function ack(m, n) {

<syntaxhighlight lang="javascript">function ack(m, n) {

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

}</syntaxhighlight>

===Eliminating Tail Calls===

<syntaxhighlight lang=javascript>function ack(M,N) {

<syntaxhighlight lang="javascript">function ack(M,N) {

for (; M > 0; M--) {

N = N === 0 ? 1 : ack(M,N-1);

Line 4,845:

}</syntaxhighlight>

===Iterative, With Explicit Stack===

<syntaxhighlight lang=javascript>function stackermann(M, N) {

<syntaxhighlight lang="javascript">function stackermann(M, N) {

const stack = [];

for (;;) {

Line 4,866:

}</syntaxhighlight>

===Stackless Iterative===

<syntaxhighlight lang=javascript>#!/usr/bin/env nodejs

<syntaxhighlight lang="javascript">#!/usr/bin/env nodejs

function ack(M, N){

const next = new Float64Array(M + 1);

Line 4,901:

===ES6===

<syntaxhighlight lang=javascript>(() => {

<syntaxhighlight lang="javascript">(() => {

'use strict';

Line 4,943:

=={{header|Joy}}==

<syntaxhighlight lang=joy>DEFINE ack == [[[pop null] popd succ]

<syntaxhighlight lang="joy">DEFINE ack == [[[pop null] popd succ]

[[null] pop pred 1 ack]

[[dup pred swap] dip pred ack ack]]

cond.</syntaxhighlight>

another using a combinator:

<syntaxhighlight lang=joy>DEFINE ack == [[[pop null] [popd succ]]

<syntaxhighlight lang="joy">DEFINE ack == [[[pop null] [popd succ]]

[[null] [pop pred 1] []]

[[[dup pred swap] dip pred] [] []]]

Line 4,956:

===Without Memoization===

<syntaxhighlight lang=jq># input: [m,n]

<syntaxhighlight lang="jq"># input: [m,n]

def ack:

.[0] as $m | .[1] as $n

Line 4,964:

end ;</syntaxhighlight>

'''Example:'''

<syntaxhighlight lang=jq>range(0;5) as $i

<syntaxhighlight lang="jq">range(0;5) as $i

| range(0; if $i > 3 then 1 else 6 end) as $j

| "A(\($i),\($j)) = \( [$i,$j] | ack )"</syntaxhighlight>

<syntaxhighlight lang=sh># jq -n -r -f ackermann.jq

<syntaxhighlight lang="sh"># jq -n -r -f ackermann.jq

A(0,0) = 1

A(0,1) = 2

Line 4,995:

A(4,0) = 13</syntaxhighlight>

===With Memoization and Optimization===

<syntaxhighlight lang=jq># input: [m,n, cache]

<syntaxhighlight lang="jq"># input: [m,n, cache]

# output [value, updatedCache]

def ack:

Line 5,025:

def A(m;n): [m,n,{}] | ack | .[0];

</syntaxhighlight>

'''Example:'''<syntaxhighlight lang=jq>A(4,1)</syntaxhighlight>

'''Example:'''<syntaxhighlight lang="jq">A(4,1)</syntaxhighlight>

=={{header|Jsish}}==

From javascript entry.

<syntaxhighlight lang=javascript>/* Ackermann function, in Jsish */

<syntaxhighlight lang="javascript">/* Ackermann function, in Jsish */

function ack(m, n) {

Line 5,068:

=={{header|Julia}}==

<syntaxhighlight lang=julia>function ack(m,n)

<syntaxhighlight lang="julia">function ack(m,n)

if m == 0

return n + 1

Line 5,079:

'''One-liner:'''

<syntaxhighlight lang=julia>ack2(m::Integer, n::Integer) = m == 0 ? n + 1 : n == 0 ? ack2(m - 1, 1) : ack2(m - 1, ack2(m, n - 1))</syntaxhighlight>

<syntaxhighlight lang="julia">ack2(m::Integer, n::Integer) = m == 0 ? n + 1 : n == 0 ? ack2(m - 1, 1) : ack2(m - 1, ack2(m, n - 1))</syntaxhighlight>

'''Using memoization''', [https://github.com/simonster/Memoize.jl source]:

<syntaxhighlight lang=julia>using Memoize

<syntaxhighlight lang="julia">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))</syntaxhighlight>

Line 5,096:

=={{header|K}}==

See [https://github.com/kevinlawler/kona/wiki the K wiki]

<syntaxhighlight lang=k>ack:{:[0=x;y+1;0=y;_f[x-1;1];_f[x-1;_f[x;y-1]]]}

<syntaxhighlight lang="k">ack:{:[0=x;y+1;0=y;_f[x-1;1];_f[x-1;_f[x;y-1]]]}

ack[2;2]</syntaxhighlight>

=={{header|Kdf9 Usercode}}==

<syntaxhighlight lang=kdf9 usercode>V6; W0;

<syntaxhighlight lang="kdf9 usercode">V6; W0;

YS26000;

RESTART; J999; J999;

Line 5,152:

=={{header|Klingphix}}==

<lang>:ack

<syntaxhighlight lang="text">:ack

%n !n %m !m

Line 5,171:

=={{header|Klong}}==

ack::{:[0=x;y+1:|0=y;.f(x-1;1);.f(x-1;.f(x;y-1))]}

ack(2;2)</syntaxhighlight>

=={{header|Kotlin}}==

tailrec fun A(m: Long, n: Long): Long {

require(m >= 0L) { "m must not be negative" }

Line 5,213:

=={{header|Lambdatalk}}==

{def ack

{lambda {:m :n}

Line 5,239:

=={{header|Lasso}}==

<syntaxhighlight lang=lasso>#!/usr/bin/lasso9

<syntaxhighlight lang="lasso">#!/usr/bin/lasso9

define ackermann(m::integer, n::integer) => {

Line 5,273:

=={{header|LFE}}==

<syntaxhighlight lang=lisp>(defun ackermann

<syntaxhighlight lang="lisp">(defun ackermann

((0 n) (+ n 1))

((m 0) (ackermann (- m 1) 1))

Line 5,279:

=={{header|Liberty BASIC}}==

<syntaxhighlight lang=lb>Print Ackermann(1, 2)

<syntaxhighlight lang="lb">Print Ackermann(1, 2)

Function Ackermann(m, n)

Line 5,295:

=={{header|LiveCode}}==

<syntaxhighlight lang=~~LiveCode~~>function ackermann m,n

<syntaxhighlight lang="livecode">function ackermann m,n

switch

Case m = 0

Line 5,307:

=={{header|Logo}}==

<syntaxhighlight lang=logo>to ack :i :j

<syntaxhighlight lang="logo">to ack :i :j

if :i = 0 [output :j+1]

if :j = 0 [output ack :i-1 1]

Line 5,314:

=={{header|Logtalk}}==

<syntaxhighlight lang=logtalk>ack(0, N, V) :-

<syntaxhighlight lang="logtalk">ack(0, N, V) :-

!,

V is N + 1.

Line 5,329:

=={{header|LOLCODE}}==

<syntaxhighlight lang=~~LOLCODE~~>HAI 1.3

<syntaxhighlight lang="lolcode">HAI 1.3

HOW IZ I ackermann YR m AN YR n

Line 5,353:

=={{header|Lua}}==

<syntaxhighlight lang=lua>function ack(M,N)

<syntaxhighlight lang="lua">function ack(M,N)

if M == 0 then return N + 1 end

if N == 0 then return ack(M-1,1) end

Line 5,360:

=== Stackless iterative solution with multiple precision, fast ===

#!/usr/bin/env luajit

local gmp = require 'gmp' ('libgmp')

Line 5,415:

=={{header|Lucid}}==

<syntaxhighlight lang=lucid>ack(m,n)

<syntaxhighlight lang="lucid">ack(m,n)

where

ack(m,n) = if m eq 0 then n+1

Line 5,424:

=={{header|Luck}}==

<syntaxhighlight lang=luck>function ackermann(m: int, n: int): int = (

<syntaxhighlight lang="luck">function ackermann(m: int, n: int): int = (

if m==0 then n+1

else if n==0 then ackermann(m-1,1)

Line 5,431:

=={{header|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))))

Line 5,449:

=={{header|M4}}==

<syntaxhighlight lang=M4>define(`ack',`ifelse($1,0,`incr($2)',`ifelse($2,0,`ack(decr($1),1)',`ack(decr($1),ack($1,decr($2)))')')')dnl

<syntaxhighlight lang="m4">define(`ack',`ifelse($1,0,`incr($2)',`ifelse($2,0,`ack(decr($1),1)',`ack(decr($1),ack($1,decr($2)))')')')dnl

ack(3,3)</syntaxhighlight>

Line 5,467:

the arguments to the recursive function via the stack or the global variables. The following program demonstrates this.

<syntaxhighlight lang=~~MAD~~> NORMAL MODE IS INTEGER

<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER

DIMENSION LIST(3000)

SET LIST TO LIST

Line 5,551:

=={{header|Maple}}==

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

Ackermann := proc( m :: nonnegint, n :: nonnegint )

option remember; # optional automatic memoization

Line 5,563:

end proc:

</syntaxhighlight>

In Maple, the keyword <syntaxhighlight lang=~~Maple~~>thisproc</syntaxhighlight> 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.)

In Maple, the keyword <syntaxhighlight lang="maple">thisproc</syntaxhighlight> refers to the currently executing procedure (closure) and is used when writing recursive procedures. (You could also use the name of the procedure, Ackermann in this case, but then a concurrently executing task or thread could re-assign that name while the recursive procedure is executing, resulting in an incorrect result.)

To make this faster, you can use known expansions for small values of <math>m</math>. (See [[wp:Ackermann_function|Wikipedia:Ackermann function]])

Ackermann := proc( m :: nonnegint, n :: nonnegint )

option remember; # optional automatic memoization

Line 5,587:

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]

</syntaxhighlight>

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]

</syntaxhighlight>

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

> length( Ackermann( 4, 2 ) );

19729

Line 5,608:

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.

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

Line 5,623:

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Two possible implementations would be:

<syntaxhighlight lang=~~Mathematica~~>$RecursionLimit=Infinity

<syntaxhighlight lang="mathematica">$RecursionLimit=Infinity

Ackermann1[m_,n_]:=

If[m==0,n+1,

Line 5,636:

Note that the second implementation is quite a bit faster, as doing 'if' comparisons is slower than the built-in pattern matching algorithms.

Examples:

<syntaxhighlight lang=~~Mathematica~~>Flatten[#,1]&@Table[{"Ackermann2["<>ToString[i]<>","<>ToString[j]<>"] =",Ackermann2[i,j]},{i,3},{j,8}]//Grid</syntaxhighlight>

<syntaxhighlight lang="mathematica">Flatten[#,1]&@Table[{"Ackermann2["<>ToString[i]<>","<>ToString[j]<>"] =",Ackermann2[i,j]},{i,3},{j,8}]//Grid</syntaxhighlight>

gives back:

<syntaxhighlight lang=~~Mathematica~~>Ackermann2[1,1] = 3

<syntaxhighlight lang="mathematica">Ackermann2[1,1] = 3

Ackermann2[1,2] = 4

Ackermann2[1,3] = 5

Line 5,663:

Ackermann2[3,8] = 2045</syntaxhighlight>

If we would like to calculate Ackermann[4,1] or Ackermann[4,2] we have to optimize a little bit:

<syntaxhighlight lang=~~Mathematica~~>Clear[Ackermann3]

<syntaxhighlight lang="mathematica">Clear[Ackermann3]

$RecursionLimit=Infinity;

Ackermann3[0,n_]:=n+1;

Line 5,673:

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

Examples 2:

<syntaxhighlight lang=~~Mathematica~~>Ackermann3[4, 1]

<syntaxhighlight lang="mathematica">Ackermann3[4, 1]

Ackermann3[4, 2]</syntaxhighlight>

gives back:

<div style="width:full;overflow:scroll"><syntaxhighlight lang=~~Mathematica~~>65533

<div style="width:full;overflow:scroll"><syntaxhighlight lang="mathematica">65533

2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880........699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156733</syntaxhighlight></div>

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.

Line 5,682:

=={{header|MATLAB}}==

<syntaxhighlight lang=~~MATLAB~~>function A = ackermannFunction(m,n)

<syntaxhighlight lang="matlab">function A = ackermannFunction(m,n)

if m == 0

A = n+1;

Line 5,693:

=={{header|Maxima}}==

<syntaxhighlight lang=maxima>ackermann(m, n) := if integerp(m) and integerp(n) then ackermann[m, n] else 'ackermann(m, n)$

<syntaxhighlight lang="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

Line 5,711:

=={{header|MAXScript}}==

Use with caution. Will cause a stack overflow for m > 3.

<syntaxhighlight lang=maxscript>fn ackermann m n =

<syntaxhighlight lang="maxscript">fn ackermann m n =

(

if m == 0 then

Line 5,729:

=={{header|Mercury}}==

This is the Ackermann function with some (obvious) elements elided. The <code>ack/3</code> predicate is implemented in terms of the <code>ack/2</code> function. The <code>ack/2</code> function is implemented in terms of the <code>ack/3</code> predicate. This makes the code both more concise and easier to follow than would otherwise be the case. The <code>integer</code> type is used instead of <code>int</code> because the problem statement stipulates the use of bignum integers if possible.

<syntaxhighlight lang=mercury>:- func ack(integer, integer) = integer.

<syntaxhighlight lang="mercury">:- func ack(integer, integer) = integer.

ack(M, N) = R :- ack(M, N, R).

Line 5,742:

=={{header|min}}==

<syntaxhighlight lang=min>(

<syntaxhighlight lang="min">(

:n :m

(

Line 5,753:

=={{header|MiniScript}}==

<syntaxhighlight lang=~~MiniScript~~>ackermann = function(m, n)

<syntaxhighlight lang="miniscript">ackermann = function(m, n)

if m == 0 then return n+1

if n == 0 then return ackermann(m - 1, 1)

Line 5,766:

=={{header|МК-61/52}}==

<lang>П1 <-> П0 ПП 06 С/П ИП0 x=0 13 ИП1

<syntaxhighlight lang="text">П1 <-> П0 ПП 06 С/П ИП0 x=0 13 ИП1

1 + В/О ИП1 x=0 24 ИП0 1 П1 -

П0 ПП 06 В/О ИП0 П2 ИП1 1 - П1

Line 5,774:

ML/I loves recursion, but runs out of its default amount of storage with larger numbers than those tested here!

===Program===

<syntaxhighlight lang=ML/I>MCSKIP "WITH" NL

<syntaxhighlight lang="ml/i">MCSKIP "WITH" NL

"" Ackermann function

"" Will overflow when it reaches implementation-defined signed integer limit

Line 5,808:

a(4,0) => ACK(4,0)</syntaxhighlight>

<syntaxhighlight lang=ML/I>a(0,0) => 1

<syntaxhighlight lang="ml/i">a(0,0) => 1

a(0,1) => 2

a(0,2) => 3

Line 5,829:

=={{header|mLite}}==

<syntaxhighlight lang=haskell>fun ackermann( 0, n ) = n + 1

<syntaxhighlight lang="haskell">fun ackermann( 0, n ) = n + 1

| ( m, 0 ) = ackermann( m - 1, 1 )

| ( m, n ) = ackermann( m - 1, ackermann(m, n - 1) )</syntaxhighlight>

Test code providing tuples from (0,0) to (3,8)

<syntaxhighlight lang=haskell>fun jota x = map (fn x = x-1) ` iota x

<syntaxhighlight lang="haskell">fun jota x = map (fn x = x-1) ` iota x

fun test_tuples (x, y) = append_map (fn a = map (fn b = (b, a)) ` jota x) ` jota y

Line 5,842:

=={{header|Modula-2}}==

<syntaxhighlight lang=modula2>MODULE ackerman;

<syntaxhighlight lang="modula2">MODULE ackerman;

IMPORT ASCII, NumConv, InOut;

Line 5,883:

=={{header|Modula-3}}==

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

<syntaxhighlight lang=modula3>MODULE Ack EXPORTS Main;

<syntaxhighlight lang="modula3">MODULE Ack EXPORTS Main;

FROM IO IMPORT Put;

Line 5,914:

=={{header|MUMPS}}==

<syntaxhighlight lang=~~MUMPS~~>Ackermann(m,n) ;

<syntaxhighlight lang="mumps">Ackermann(m,n) ;

If m=0 Quit n+1

If m>0,n=0 Quit $$Ackermann(m-1,1)

Line 5,925:

=={{header|Neko}}==

<syntaxhighlight lang=~~ActionScript~~>/**

<syntaxhighlight lang="actionscript">/**

Ackermann recursion, in Neko

Tectonics:

Line 5,970:

=={{header|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;

Line 5,993:

</syntaxhighlight>

A terser version using implicit <code>match</code> (which doesn't use the alias <code>A</code> internally):

def ackermann(m, n) {

| (0, n) => n + 1

Line 6,002:

</syntaxhighlight>

Or, if we were set on using the <code>A</code> notation, we could do this:

def ackermann = {

def A(m, n) {

Line 6,015:

=={{header|NetRexx}}==

<syntaxhighlight lang=~~NetRexx~~>/* NetRexx */

<syntaxhighlight lang="netrexx">/* NetRexx */

options replace format comments java crossref symbols binary

Line 6,042:

=={{header|NewLISP}}==

#! /usr/local/bin/newlisp

Line 6,058:

=={{header|Nim}}==

<syntaxhighlight lang=nim>from strutils import parseInt

<syntaxhighlight lang="nim">from strutils import parseInt

proc ackermann(m, n: int64): int64 =

Line 6,089:

Source: [https://github.com/nitlang/nit/blob/master/examples/rosettacode/ackermann_function.nit the official Nit’s repository].

<syntaxhighlight lang=nit># Task: Ackermann function

<syntaxhighlight lang="nit"># Task: Ackermann function

#

# A simple straightforward recursive implementation.

Line 6,145:

=={{header|Oberon-2}}==

<syntaxhighlight lang=oberon2>MODULE ackerman;

<syntaxhighlight lang="oberon2">MODULE ackerman;

IMPORT Out;

Line 6,174:

=={{header|Objeck}}==

<syntaxhighlight lang=objeck>class Ackermann {

<syntaxhighlight lang="objeck">class Ackermann {

function : Main(args : String[]) ~ Nil {

for(m := 0; m <= 3; ++m;) {

Line 6,228:

=={{header|OCaml}}==

<syntaxhighlight lang=ocaml>let rec a m n =

<syntaxhighlight lang="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)))</syntaxhighlight>

or:

<syntaxhighlight lang=ocaml>let rec a = function

<syntaxhighlight lang="ocaml">let rec a = function

| 0, n -> (n+1)

| m, 0 -> a(m-1, 1)

| m, n -> a(m-1, a(m, n-1))</syntaxhighlight>

with memoization using an hash-table:

<syntaxhighlight lang=ocaml>let h = Hashtbl.create 4001

<syntaxhighlight lang="ocaml">let h = Hashtbl.create 4001

let a m n =

Line 6,247:

(res)</syntaxhighlight>

taking advantage of the memoization we start calling small values of '''m''' and '''n''' in order to reduce the recursion call stack:

<syntaxhighlight lang=ocaml>let a m n =

<syntaxhighlight lang="ocaml">let a m n =

for _m = 0 to m do

for _n = 0 to n do

Line 6,256:

=== Arbitrary precision ===

With arbitrary-precision integers ([http://caml.inria.fr/pub/docs/manual-ocaml/libref/Big_int.html Big_int module]):

<syntaxhighlight lang=ocaml>open Big_int

<syntaxhighlight lang="ocaml">open Big_int

let one = unit_big_int

let zero = zero_big_int

Line 6,271:

=== Tail-Recursive ===

Here is a [[:Category:Recursion|tail-recursive]] version:

<syntaxhighlight lang=ocaml>let rec find_option h v =

<syntaxhighlight lang="ocaml">let rec find_option h v =

try Some(Hashtbl.find h v)

with Not_found -> None

Line 6,302:

let a = a (Hashtbl.create 42 (* arbitrary *) ) [] [] ;;</syntaxhighlight>

This one uses the arbitrary precision, the tail-recursion, and the optimisation explain on the Wikipedia page about <tt>(m,n) = (3,_)</tt>.

<syntaxhighlight lang=ocaml>open Big_int

<syntaxhighlight lang="ocaml">open Big_int

let one = unit_big_int

let zero = zero_big_int

Line 6,383:

=={{header|Octave}}==

<syntaxhighlight lang=octave>function r = ackerman(m, n)

<syntaxhighlight lang="octave">function r = ackerman(m, n)

if ( m == 0 )

r = n + 1;

Line 6,398:

=={{header|Oforth}}==

<syntaxhighlight lang=~~Oforth~~>: A( m n -- p )

<syntaxhighlight lang="oforth">: A( m n -- p )

m ifZero: [ n 1+ return ]

m 1- n ifZero: [ 1 ] else: [ A( m, n 1- ) ] A

Line 6,404:

=={{header|Ol}}==

; simple version

(define (A m n)

Line 6,450:

=={{header|OOC}}==

ack: func (m: Int, n: Int) -> Int {

if (m == 0) {

Line 6,471:

=={{header|ooRexx}}==

loop m = 0 to 3

loop n = 0 to 6

Line 6,519:

=={{header|Order}}==

<syntaxhighlight lang=c>#include <order/interpreter.h>

<syntaxhighlight lang="c">#include <order/interpreter.h>

#define ORDER_PP_DEF_8ack ORDER_PP_FN( \

Line 6,531:

=={{header|Oz}}==

Oz has arbitrary precision integers.

<syntaxhighlight lang=oz>declare

<syntaxhighlight lang="oz">declare

fun {Ack M N}

Line 6,546:

=={{header|PARI/GP}}==

Naive implementation.

<syntaxhighlight lang=parigp>A(m,n)={

<syntaxhighlight lang="parigp">A(m,n)={

if(m,

if(n,

Line 6,559:

=={{header|Pascal}}==

<syntaxhighlight lang=pascal>Program Ackerman;

<syntaxhighlight lang="pascal">Program Ackerman;

function ackermann(m, n: Integer) : Integer;

Line 6,582:

=={{header|Perl}}==

We memoize calls to ''A'' to make ''A''(2, ''n'') and ''A''(3, ''n'') feasible for larger values of ''n''.

<syntaxhighlight lang=perl>{

<syntaxhighlight lang="perl">{

my @memo;

sub A {

Line 6,597:

An implementation using the conditional statements 'if', 'elsif' and 'else':

<syntaxhighlight lang=perl>sub A {

<syntaxhighlight lang="perl">sub A {

my ($m, $n) = @_;

if ($m == 0) { $n + 1 }

Line 6,605:

An implementation using ternary chaining:

<syntaxhighlight lang=perl>sub A {

<syntaxhighlight lang="perl">sub A {

my ($m, $n) = @_;

$m == 0 ? $n + 1 :

Line 6,613:

Adding memoization and extra terms:

<syntaxhighlight lang=perl>use Memoize; memoize('ack2');

<syntaxhighlight lang="perl">use Memoize; memoize('ack2');

use bigint try=>"GMP";

Line 6,635:

An optimized version, which uses <code>@_</code> as a stack,

instead of recursion. Very fast.

<syntaxhighlight lang=~~Perl~~>use strict;

<syntaxhighlight lang="perl">use strict;

use warnings;

use Math::BigInt;

Line 6,674:

=={{header|Phix}}==

=== native version ===

function ack(integer m, integer n)

if m=0 then

Line 6,725:

-- demo\rosetta\Ackermann.exw

include mpfr.e

Line 6,828:

=={{header|Phixmonti}}==

<syntaxhighlight lang=~~Phixmonti~~>def ack

<syntaxhighlight lang="phixmonti">def ack

var n var m

Line 6,845:

=={{header|PHP}}==

<syntaxhighlight lang=php>function ackermann( $m , $n )

<syntaxhighlight lang="php">function ackermann( $m , $n )

{

if ( $m==0 )

Line 6,862:

=={{header|Picat}}==

foreach(M in 0..3)

println([m=M,[a(M,N) : N in 0..16]])

Line 6,921:

=={{header|PicoLisp}}==

<syntaxhighlight lang=~~PicoLisp~~>(de ack (X Y)

<syntaxhighlight lang="picolisp">(de ack (X Y)

(cond

((=0 X) (inc Y))

Line 7,294:

=={{header|Pike}}==

<syntaxhighlight lang=pike>int main(){

<syntaxhighlight lang="pike">int main(){

write(ackermann(3,4) + "\n");

}

Line 7,309:

=={{header|PL/I}}==

<syntaxhighlight lang=PL/I>Ackerman: procedure (m, n) returns (fixed (30)) recursive;

<syntaxhighlight lang="pl/i">Ackerman: procedure (m, n) returns (fixed (30)) recursive;

declare (m, n) fixed (30);

if m = 0 then return (n+1);

Line 7,318:

=={{header|PL/SQL}}==

<syntaxhighlight lang=~~PLSQL~~>DECLARE

<syntaxhighlight lang="plsql">DECLARE

FUNCTION ackermann(pi_m IN NUMBER,

Line 7,373:

=={{header|PostScript}}==

<syntaxhighlight lang=postscript>/ackermann{

<syntaxhighlight lang="postscript">/ackermann{

/n exch def

/m exch def %PostScript takes arguments in the reverse order as specified in the function definition

Line 7,388:

}def</syntaxhighlight>

<syntaxhighlight lang=postscript>/A {

<syntaxhighlight lang="postscript">/A {

[/.m /.n] let

{

Line 7,398:

=={{header|Potion}}==

<syntaxhighlight lang=~~Potion~~>ack = (m, n):

<syntaxhighlight lang="potion">ack = (m, n):

if (m == 0): n + 1

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

Line 7,411:

=={{header|PowerBASIC}}==

<syntaxhighlight lang=powerbasic>FUNCTION PBMAIN () AS LONG

<syntaxhighlight lang="powerbasic">FUNCTION PBMAIN () AS LONG

DIM m AS QUAD, n AS QUAD

Line 7,432:

=={{header|PowerShell}}==

<syntaxhighlight lang=powershell>function ackermann ([long] $m, [long] $n) {

<syntaxhighlight lang="powershell">function ackermann ([long] $m, [long] $n) {

if ($m -eq 0) {

return $n + 1

Line 7,444:

}</syntaxhighlight>

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

<syntaxhighlight lang=powershell>foreach ($m in 0..3) {

<syntaxhighlight lang="powershell">foreach ($m in 0..3) {

foreach ($n in 0..6) {

Write-Host -NoNewline ("{0,5}" -f (ackermann $m $n))

Line 7,457:

===A More "PowerShelly" Way===

function Get-Ackermann ([int64]$m, [int64]$n)

{

Line 7,474:

</syntaxhighlight>

Save the result to an array (for possible future use?), then display it using the <code>Format-Wide</code> cmdlet:

$ackermann = 0..3 | ForEach-Object {$m = $_; 0..6 | ForEach-Object {Get-Ackermann $m $_}}

Line 7,488:

=={{header|Processing}}==

<syntaxhighlight lang=java>int ackermann(int m, int n) {

<syntaxhighlight lang="java">int ackermann(int m, int n) {

if (m == 0)

return n + 1;

Line 7,520:

m = 5 it throws 'maximum recursion depth exceeded'

<syntaxhighlight lang=python>from __future__ import print_function

<syntaxhighlight lang="python">from __future__ import print_function

def setup():

Line 7,541:

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

<syntaxhighlight lang=r>setup <- function() {

<syntaxhighlight lang="r">setup <- function() {

for (m in 0:3) {

for (n in 0:4) {

Line 7,568:

=={{header|Prolog}}==

<syntaxhighlight lang=prolog>:- table ack/3. % memoization reduces the execution time of ack(4,1,X) from several

<syntaxhighlight lang="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.

Line 7,575:

=={{header|Pure}}==

<syntaxhighlight lang=pure>A 0 n = n+1;

<syntaxhighlight lang="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;</syntaxhighlight>

=={{header|Pure Data}}==

#N canvas 741 265 450 436 10;

#X obj 83 111 t b l;

Line 7,628:

=={{header|PureBasic}}==

<syntaxhighlight lang=~~PureBasic~~>Procedure.q Ackermann(m, n)

<syntaxhighlight lang="purebasic">Procedure.q Ackermann(m, n)

If m = 0

ProcedureReturn n + 1

Line 7,641:

=={{header|Purity}}==

<syntaxhighlight lang=~~Purity~~>data Iter = f => FoldNat <const $f One, $f>

<syntaxhighlight lang="purity">data Iter = f => FoldNat <const $f One, $f>

data Ackermann = FoldNat <const Succ, Iter></syntaxhighlight>

Line 7,647:

===Python: Explicitly recursive===

<syntaxhighlight lang=python>def ack1(M, N):

<syntaxhighlight lang="python">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)))</syntaxhighlight>

Another version:

<syntaxhighlight lang=python>from functools import lru_cache

<syntaxhighlight lang="python">from functools import lru_cache

@lru_cache(None)

Line 7,662:

return ack2(M - 1, ack2(M, N - 1))</syntaxhighlight>

<syntaxhighlight lang=python>>>> import sys

<syntaxhighlight lang="python">>>> import sys

>>> sys.setrecursionlimit(3000)

>>> ack1(0,0)

Line 7,673:

125</syntaxhighlight>

From the Mathematica ack3 example:

<syntaxhighlight lang=python>def ack2(M, N):

<syntaxhighlight lang="python">def ack2(M, N):

return (N + 1) if M == 0 else (

(N + 2) if M == 1 else (

Line 7,684:

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.

<syntaxhighlight lang=python>from collections import deque

<syntaxhighlight lang="python">from collections import deque

def ack_ix(m, n):

Line 7,733:

=={{header|Quackery}}==

<syntaxhighlight lang=~~Quackery~~> forward is ackermann ( m n --> r )

<syntaxhighlight lang="quackery"> forward is ackermann ( m n --> r )

[ over 0 = iff

[ nip 1 + ] done

Line 7,747:

=={{header|R}}==

<syntaxhighlight lang=R>ackermann <- function(m, n) {

<syntaxhighlight lang="r">ackermann <- function(m, n) {

if ( m == 0 ) {

n+1

Line 7,756:

}

}</syntaxhighlight>

<syntaxhighlight lang=R>for ( i in 0:3 ) {

<syntaxhighlight lang="r">for ( i in 0:3 ) {

print(ackermann(i, 4))

}</syntaxhighlight>

=={{header|Racket}}==

#lang racket

(define (ackermann m n)

Line 7,773:

<syntaxhighlight lang=~~perl6~~>sub A(Int $m, Int $n) {

<syntaxhighlight lang="raku" line>sub A(Int $m, Int $n) {

if $m == 0 { $n + 1 }

elsif $n == 0 { A($m - 1, 1) }

Line 7,779:

}</syntaxhighlight>

An implementation using multiple dispatch:

<syntaxhighlight lang=~~perl6~~>multi sub A(0, Int $n) { $n + 1 }

<syntaxhighlight lang="raku" line>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)) }</syntaxhighlight>

Line 7,785:

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:

<syntaxhighlight lang=~~perl6~~>proto A(Int \𝑚, Int \𝑛) { (state @)[𝑚][𝑛] //= {*} }

<syntaxhighlight lang="raku" line>proto A(Int \𝑚, Int \𝑛) { (state @)[𝑚][𝑛] //= {*} }

multi A(0, Int \𝑛) { 𝑛 + 1 }

Line 7,812:

=={{header|ReScript}}==

<syntaxhighlight lang=~~ReScript~~>let _m = Sys.argv[2]

<syntaxhighlight lang="rescript">let _m = Sys.argv[2]

let _n = Sys.argv[3]

Line 7,839:

=={{header|REXX}}==

===no optimization===

<syntaxhighlight lang=rexx>/*REXX program calculates and displays some values for the Ackermann function. */

<syntaxhighlight lang="rexx">/*REXX program calculates and displays some values for the Ackermann function. */

/*╔════════════════════════════════════════════════════════════════════════╗

║ Note: the Ackermann function (as implemented here) utilizes deep ║

Line 7,944:

===optimized for m ≤ 2===

<syntaxhighlight lang=rexx>/*REXX program calculates and displays some values for the Ackermann function. */

<syntaxhighlight lang="rexx">/*REXX program calculates and displays some values for the Ackermann function. */

high=24

do j=0 to 3; say

Line 8,048:

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.

<syntaxhighlight lang=rexx>/*REXX program calculates and displays some values for the Ackermann function. */

<syntaxhighlight lang="rexx">/*REXX program calculates and displays some values for the Ackermann function. */

numeric digits 100 /*use up to 100 decimal digit integers.*/

/*╔═════════════════════════════════════════════════════════════╗

Line 8,171:

=={{header|Ring}}==

<syntaxhighlight lang=ring>for m = 0 to 3

<syntaxhighlight lang="ring">for m = 0 to 3

for n = 0 to 4

see "Ackermann(" + m + ", " + n + ") = " + Ackermann(m, n) + nl

Line 8,214:

=={{header|Risc-V}}==

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

<syntaxhighlight lang=~~Risc~~-V>ackermann: #x: a1, y: a2, return: a0

<syntaxhighlight lang="risc-v">ackermann: #x: a1, y: a2, return: a0

beqz a1, npe #case m = 0

beqz a2, mme #case m > 0 & n = 0

Line 8,245:

=={{header|Ruby}}==

<syntaxhighlight lang=ruby>def ack(m, n)

<syntaxhighlight lang="ruby">def ack(m, n)

if m == 0

n + 1

Line 8,255:

end</syntaxhighlight>

Example:

<syntaxhighlight lang=ruby>(0..3).each do |m|

<syntaxhighlight lang="ruby">(0..3).each do |m|

puts (0..6).map { |n| ack(m, n) }.join(' ')

end</syntaxhighlight>

Line 8,265:

=={{header|Run BASIC}}==

<syntaxhighlight lang=runbasic>print ackermann(1, 2)

<syntaxhighlight lang="runbasic">print ackermann(1, 2)

function ackermann(m, n)

Line 8,274:

=={{header|Rust}}==

<syntaxhighlight lang=rust>fn ack(m: isize, n: isize) -> isize {

<syntaxhighlight lang="rust">fn ack(m: isize, n: isize) -> isize {

if m == 0 {

n + 1

Line 8,292:

Or:

fn ack(m: u64, n: u64) -> u64 {

match (m, n) {

Line 8,303:

=={{header|Sather}}==

<syntaxhighlight lang=sather>class MAIN is

<syntaxhighlight lang="sather">class MAIN is

ackermann(m, n:INT):INT

Line 8,323:

end;</syntaxhighlight>

Instead of <code>INT</code>, the class <code>INTI</code> 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.

<syntaxhighlight lang=sather>class MAIN is

<syntaxhighlight lang="sather">class MAIN is

ackermann(m, n:INTI):INTI is

Line 8,345:

=={{header|Scala}}==

<syntaxhighlight lang=scala>def ack(m: BigInt, n: BigInt): BigInt = {

<syntaxhighlight lang="scala">def ack(m: BigInt, n: BigInt): BigInt = {

if (m==0) n+1

else if (n==0) ack(m-1, 1)

Line 8,356:

</pre>

Memoized version using a mutable hash map:

<syntaxhighlight lang=scala>val ackMap = new mutable.HashMap[(BigInt,BigInt),BigInt]

<syntaxhighlight lang="scala">val ackMap = new mutable.HashMap[(BigInt,BigInt),BigInt]

def ackMemo(m: BigInt, n: BigInt): BigInt = {

ackMap.getOrElseUpdate((m,n), ack(m,n))

Line 8,362:

=={{header|Scheme}}==

<syntaxhighlight lang=scheme>(define (A m n)

<syntaxhighlight lang="scheme">(define (A m n)

(cond

((= m 0) (+ n 1))

Line 8,370:

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

<syntaxhighlight lang=scheme>(define (A m n)

<syntaxhighlight lang="scheme">(define (A m n)

(letrec ((A-stream

(cons-stream

Line 8,401:

=={{header|Scilab}}==

<lang>clear

<syntaxhighlight lang="text">clear

function acker=ackermann(m,n)

global calls

Line 8,455:

=={{header|Seed7}}==

<syntaxhighlight lang=seed7>const func integer: ackermann (in integer: m, in integer: n) is func

<syntaxhighlight lang="seed7">const func integer: ackermann (in integer: m, in integer: n) is func

result

var integer: result is 0;

Line 8,470:

=={{header|SETL}}==

<syntaxhighlight lang=~~SETL~~>program ackermann;

<syntaxhighlight lang="setl">program ackermann;

(for m in [0..3])

Line 8,483:

=={{header|Shen}}==

<syntaxhighlight lang=shen>(define ack

<syntaxhighlight lang="shen">(define ack

0 N -> (+ N 1)

M 0 -> (ack (- M 1) 1)

Line 8,490:

=={{header|Sidef}}==

<syntaxhighlight lang=ruby>func A(m, n) {

<syntaxhighlight lang="ruby">func A(m, n) {

m == 0 ? (n + 1)

: (n == 0 ? (A(m - 1, 1))

Line 8,497:

Alternatively, using multiple dispatch:

<syntaxhighlight lang=ruby>func A((0), n) { n + 1 }

<syntaxhighlight lang="ruby">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)) }</syntaxhighlight>

Calling the function:

<syntaxhighlight lang=ruby>say A(3, 2); # prints: 29</syntaxhighlight>

<syntaxhighlight lang="ruby">say A(3, 2); # prints: 29</syntaxhighlight>

=={{header|Simula}}==

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

<syntaxhighlight lang=~~Simula~~> BEGIN

<syntaxhighlight lang="simula"> BEGIN

INTEGER procedure

Ackermann(g, p); SHORT INTEGER g, p;

Line 8,530:

=={{header|Slate}}==

<syntaxhighlight lang=slate>m@(Integer traits) ackermann: n@(Integer traits)

<syntaxhighlight lang="slate">m@(Integer traits) ackermann: n@(Integer traits)

[

m isZero

Line 8,541:

=={{header|Smalltalk}}==

<syntaxhighlight lang=smalltalk>|ackermann|

<syntaxhighlight lang="smalltalk">|ackermann|

ackermann := [ :n :m |

(n = 0) ifTrue: [ (m + 1) ]

Line 8,558:

=={{header|SmileBASIC}}==

<syntaxhighlight lang=smilebasic>DEF ACK(M,N)

<syntaxhighlight lang="smilebasic">DEF ACK(M,N)

IF M==0 THEN

RETURN N+1

Line 8,571:

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

<syntaxhighlight lang=~~SNOBOL4~~>define('ack(m,n)') :(ack_end)

<syntaxhighlight lang="snobol4">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)

Line 8,590:

=={{header|SNUSP}}==

<syntaxhighlight lang=snusp> /==!/==atoi=@@@-@-----#

<syntaxhighlight lang="snusp"> /==!/==atoi=@@@-@-----#

| | Ackermann function

| | /=========\!==\!====\ recursion:

Line 8,606:

=={{header|SPAD}}==

NNI ==> NonNegativeInteger

Line 8,636:

{{works with|Db2 LUW}} version 9.7 or higher.

With SQL PL:

--#SET TERMINATOR @

Line 8,719:

=={{header|Standard ML}}==

<syntaxhighlight lang=sml>fun a (0, n) = n+1

<syntaxhighlight lang="sml">fun a (0, n) = n+1

| a (m, 0) = a (m-1, 1)

| a (m, n) = a (m-1, a (m, n-1))</syntaxhighlight>

=={{header|Stata}}==

<syntaxhighlight lang=stata>mata

<syntaxhighlight lang="stata">mata

function ackermann(m,n) {

if (m==0) {

Line 8,743:

=={{header|Swift}}==

<syntaxhighlight lang=swift>func ackerman(m:Int, n:Int) -> Int {

<syntaxhighlight lang="swift">func ackerman(m:Int, n:Int) -> Int {

if m == 0 {

return n+1

Line 8,756:

===Simple===

<syntaxhighlight lang=tcl>proc ack {m n} {

<syntaxhighlight lang="tcl">proc ack {m n} {

if {$m == 0} {

expr {$n + 1}

Line 8,767:

===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):

<syntaxhighlight lang=tcl>proc ack {m n} {

<syntaxhighlight lang="tcl">proc ack {m n} {

if {$m == 0} {

expr {$n + 1}

Line 8,779:

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.

<syntaxhighlight lang=tcl>package require Tcl 8.6

<syntaxhighlight lang="tcl">package require Tcl 8.6

# A memoization engine, from http://wiki.tcl.tk/18152

Line 8,840:

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

<syntaxhighlight lang=ti83b>PROGRAM:ACKERMAN

<syntaxhighlight lang="ti83b">PROGRAM:ACKERMAN

:If not(M

:Then

Line 8,864:

Here is a handler function that makes the previous function easier to use. (You can name it whatever you want.)

<syntaxhighlight lang=ti83b>PROGRAM:AHANDLER

<syntaxhighlight lang="ti83b">PROGRAM:AHANDLER

:0→dim(L1

:Prompt M

Line 8,872:

=={{header|TI-89 BASIC}}==

<syntaxhighlight lang=ti89b>Define A(m,n) = when(m=0, n+1, when(n=0, A(m-1,1), A(m-1, A(m, n-1))))</syntaxhighlight>

<syntaxhighlight lang="ti89b">Define A(m,n) = when(m=0, n+1, when(n=0, A(m-1,1), A(m-1, A(m, n-1))))</syntaxhighlight>

=={{header|TorqueScript}}==

<syntaxhighlight lang=~~TorqueScript~~>function ackermann(%m,%n)

<syntaxhighlight lang="torquescript">function ackermann(%m,%n)

{

if(%m==0)

Line 8,886:

=={{header|TSE SAL}}==

<syntaxhighlight lang=~~TSESAL~~>// 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]

<syntaxhighlight lang="tsesal">// 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 )

Line 8,910:

with memoization.

<syntaxhighlight lang=txrlisp>(defmacro defmemofun (name (. args) . body)

<syntaxhighlight lang="txrlisp">(defmacro defmemofun (name (. args) . body)

(let ((hash (gensym "hash-"))

(argl (gensym "args-"))

Line 8,958:

=={{header|UNIX Shell}}==

<syntaxhighlight lang=bash>ack() {

<syntaxhighlight lang="bash">ack() {

local m=$1

local n=$2

Line 8,970:

}</syntaxhighlight>

Example:

<syntaxhighlight lang=bash>for ((m=0;m<=3;m++)); do

<syntaxhighlight lang="bash">for ((m=0;m<=3;m++)); do

for ((n=0;n<=6;n++)); do

ack $m $n

Line 8,985:

=={{header|Ursala}}==

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

<syntaxhighlight lang=~~Ursala~~>#import std

<syntaxhighlight lang="ursala">#import std

#import nat

Line 8,994:

^|R/~& ~&\1+ predecessor@l)</syntaxhighlight>

test program for the first 4 by 7 numbers:

<syntaxhighlight lang=~~Ursala~~>#cast %nLL

<syntaxhighlight lang="ursala">#cast %nLL

test = block7 ackermann*K0 iota~~/4 7</syntaxhighlight>

Line 9,007:

=={{header|V}}==

<syntaxhighlight lang=v>[ack

<syntaxhighlight lang="v">[ack

[ [pop zero?] [popd succ]

[zero?] [pop pred 1 ack]

Line 9,013:

] when].</syntaxhighlight>

using destructuring view

<syntaxhighlight lang=v>[ack

<syntaxhighlight lang="v">[ack

[ [pop zero?] [ [m n : [n succ]] view i]

[zero?] [ [m n : [m pred 1 ack]] view i]

Line 9,020:

=={{header|Vala}}==

<syntaxhighlight lang=vala>uint64 ackermann(uint64 m, uint64 n) {

<syntaxhighlight lang="vala">uint64 ackermann(uint64 m, uint64 n) {

if (m == 0) return n + 1;

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

Line 9,079:

=={{header|VBA}}==

<syntaxhighlight lang=vb>Private Function Ackermann_function(m As Variant, n As Variant) As Variant

<syntaxhighlight lang="vb">Private Function Ackermann_function(m As Variant, n As Variant) As Variant

Dim result As Variant

Debug.Assert m >= 0

Line 9,117:

Based on BASIC version. Uncomment all the lines referring to <code>depth</code> and see just how deep the recursion goes.

;Implementation

<syntaxhighlight lang=vb>option explicit

<syntaxhighlight lang="vb">option explicit

'~ dim depth

function ack(m, n)

Line 9,138:

end function</syntaxhighlight>

;Invocation

<syntaxhighlight lang=vb>wscript.echo ack( 1, 10 )

<syntaxhighlight lang="vb">wscript.echo ack( 1, 10 )

'~ depth = 0

wscript.echo ack( 2, 1 )

Line 9,153:

Option Explicit

Dim calls As Long

Line 9,228:

=={{header|Vlang}}==

<syntaxhighlight lang=go>fn ackermann(m int, n int ) int {

<syntaxhighlight lang="go">fn ackermann(m int, n int ) int {

if m == 0 {

return n + 1

Line 9,271:

=={{header|Wart}}==

<syntaxhighlight lang=wart>def (ackermann m n)

<syntaxhighlight lang="wart">def (ackermann m n)

(if m=0

n+1

Line 9,280:

=={{header|WDTE}}==

<syntaxhighlight lang=~~WDTE~~>let memo a m n => true {

<syntaxhighlight lang="wdte">let memo a m n => true {

== m 0 => + n 1;

== n 0 => a (- m 1) 1;

Line 9,287:

=={{header|Wren}}==

<syntaxhighlight lang=ecmascript>// To use recursion definition and declaration must be on separate lines

<syntaxhighlight lang="ecmascript">// To use recursion definition and declaration must be on separate lines

var Ackermann

Ackermann = Fn.new {|m, n|

Line 9,315:

section .text

Line 9,348:

=={{header|XLISP}}==

<syntaxhighlight lang=lisp>(defun ackermann (m n)

<syntaxhighlight lang="lisp">(defun ackermann (m n)

(cond

((= m 0) (+ n 1))

Line 9,354:

(t (ackermann (- m 1) (ackermann m (- n 1))))))</syntaxhighlight>

Test it:

<syntaxhighlight lang=lisp>(print (ackermann 3 9))</syntaxhighlight>

<syntaxhighlight lang="lisp">(print (ackermann 3 9))</syntaxhighlight>

Output (after a very perceptible pause):

That worked well. Test it again:

<syntaxhighlight lang=lisp>(print (ackermann 4 1))</syntaxhighlight>

<syntaxhighlight lang="lisp">(print (ackermann 4 1))</syntaxhighlight>

Output (after another pause):

<pre>Abort: control stack overflow

Line 9,364:

=={{header|XPL0}}==

<syntaxhighlight lang=~~XPL0~~>include c:\cxpl\codes;

<syntaxhighlight lang="xpl0">include c:\cxpl\codes;

func Ackermann(M, N);

Line 9,392:

The following named template calculates the Ackermann function:

<xsl:template name="ackermann">

<xsl:param name="m"/>

Line 9,425:

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

Line 9,474:

Which will transform this input

<?xml version="1.0" ?>

<?xml-stylesheet type="text/xsl" href="ackermann.xslt"?>

Line 9,666:

=={{header|Yabasic}}==

<syntaxhighlight lang=~~Yabasic~~>sub ack(M,N)

<syntaxhighlight lang="yabasic">sub ack(M,N)

if M = 0 return N + 1

if N = 0 return ack(M-1,1)

Line 9,677:

What smart code can get. Fast as lightning!

<syntaxhighlight lang=~~Yabasic~~>sub ack(m, n)

<syntaxhighlight lang="yabasic">sub ack(m, n)

if m=0 then

return n+1

Line 9,707:

=={{header|Yorick}}==

<syntaxhighlight lang=yorick>func ack(m, n) {

<syntaxhighlight lang="yorick">func ack(m, n) {

if(m == 0)

return n + 1;

Line 9,716:

}</syntaxhighlight>

Example invocation:

<syntaxhighlight lang=yorick>for(m = 0; m <= 3; m++) {

<syntaxhighlight lang="yorick">for(m = 0; m <= 3; m++) {

for(n = 0; n <= 6; n++)

write, format="%d ", ack(m, n);

Line 9,727:

5 13 29 61 125 253 509</pre>

⚫

=={{header|Z80 Assembly}}==

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

<syntaxhighlight lang=z80> OPT --syntax=abf : OUTPUT "ackerman.com"

<syntaxhighlight lang="z80"> OPT --syntax=abf : OUTPUT "ackerman.com"

ORG $100

jr demo_start

Line 9,852:

Line 9,849:

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

Compiled -> http://ideone.com/OlS7zL

<syntaxhighlight lang=zed>(A) m n

<syntaxhighlight lang="zed">(A) m n

comment:

(=) m 0

Line 9,883:

Line 9,880:

=={{header|Zig}}==

<syntaxhighlight lang=zig>pub fn ack(m: u64, n: u64) u64 {

<syntaxhighlight lang="zig">pub fn ack(m: u64, n: u64) u64 {

if (m == 0) return n + 1;

if (n == 0) return ack(m - 1, 1);

Line 9,908:

Line 9,905:

=={{header|ZX Spectrum Basic}}==

<syntaxhighlight lang=zxbasic>10 DIM s(2000,3)

<syntaxhighlight lang="zxbasic">10 DIM s(2000,3)

20 LET s(1,1)=3: REM M

30 LET s(1,2)=7: REM N

Line 9,929:

Line 9,926:

⚫