Ackermann function: Difference between revisions

{{trans|Python}}

 

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

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

print(ack2(0, 0))

print(ack2(3, 4))

 

{{out}}

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

To simplify, the program is recursive not reentrant.

&LAB XDECO &REG,&TARGET

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

STACKLEN EQU *-STACK

YREGS

{{out}}

<pre style="height:20ex">

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

;

 

outString

 

=={{header|8080 Assembly}}==

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

 

jmp demo

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

db '*****' ; Placeholder for number

pnum: db 9,'$'

 

{{out}}

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

 

bits 16

org 100h

db '*****' ; Placeholder for ASCII number

pnum: db 9,'$'

 

{{out}}

 

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

\ Ackermann function, illustrating use of "memoization".

 

4 1 ackOf

 

 

{{out|The output}}

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

{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}

/* ARM assembly AARCH64 Raspberry PI 3B or android 64 bits */

/* program ackermann64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

{{Output}}

<pre>

=={{header|ABAP}}==

 

REPORT zhuberv_ackermann.

 

lv_result = zcl_ackermann=>ackermann( m = pa_m n = pa_n ).

WRITE: / lv_result.

 

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

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

CARD ARRAY stack(MAXSIZE)

CARD stacksize=[0]

OD

OD

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Ackermann_function.png Screenshot from Atari 8-bit computer]

 

=={{header|ActionScript}}==

{

if (m == 0)

 

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

 

=={{header|Ada}}==

 

procedure Test_Ackermann is

New_Line;

end loop;

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

{{out}} the first 4x7 Ackermann's numbers:

 

=={{header|Agda}}==

module Ackermann where

 

ack zero n = n + 1

ack (suc m) zero = ack m 1

ack (suc m) (suc n) = ack m (ack (suc m) n)

 

 

agda --compile Ackermann.agda

./Ackermann

 

{{out}}

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

{{works with|A60}}

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

ackermann:=if m=0 then n+1

outstring(1,"\n")

end

{{out}}

<pre>

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

BEGIN

PROC ackermann = (INT m, n)INT:

OD

END # test ackermann #;

{{out}}

<pre>

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

{{Trans|ALGOL 60}}

integer procedure ackermann( integer value m,n ) ;

if m=0 then n+1

for n := 1 until 6 do writeon( ackermann( m, n ) );

end for_m

{{out}}

<pre>

=={{header|APL}}==

{{works with|Dyalog APL}}

0=1⊃⍵:1+2⊃⍵

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

∇(¯1+1⊃⍵),∇(1⊃⍵),¯1+2⊃⍵

 

=={{header|AppleScript}}==

if m is equal to 0 then return n + 1

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

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

 

=={{header|Argile}}==

{{works with|Argile|1.0.0}}

 

for each (val nat n) from 0 to 6

return (n+1) if m == 0

return (A (m - 1) 1) if n == 0

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

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

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

/* program ackermann.s */

/***************************************************/

.include "../affichage.inc"

{{Output}}

<pre>

 

=={{header|Arturo}}==

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

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

print ["ackermann" a b "=>" ackermann a b]

]

{{out}}

<pre>ackermann 0 0 => 1

ackermann 0 1 => 2

 

=={{header|ATS}}==

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

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

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

| (_, _) =>> ackermann (m-1, ackermann (m, n-1))

 

=={{header|AutoHotkey}}==

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

Return A(m-1,1)

 

; Example:

 

=={{header|AutoIt}}==

=== Classical version ===

If ($m = 0) Then

Return $n+1

EndIf

EndIf

 

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

 

Func Ackermann($m, $n)

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

Return $return

EndIf

 

=={{header|AWK}}==

{

if ( m == 0 ) {

}

}

 

=={{header|Babel}}==

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

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

if }

 

{{out}}

A(0 1 ) = 2

A(0 2 ) = 3

=={{header|BASIC}}==

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

110 FOR M = 0 TO 3

120 FOR N = 0 TO 4

250 M = M(SP) : N = N(SP) : IF SP = 0 THEN RETURN

260 FOR SP = SP - 1 TO 0 STEP -1 : IF R%(SP) THEN M = M(SP) : N = N(SP) : NEXT SP : SP = 0 : RETURN

 

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

stack[0,0] = 3 # M

stack[0,1] = 7 # N

stack[lev-1,2] = stack[lev,2]

lev = lev-1

{{out}}

 

for m = 0 to 3

for n = 0 to 4

endif

end if

{{out}}

0 1 2

0 2 3

 

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

END

IF M% = 0 THEN = N% + 1

IF N% = 0 THEN = FNackermann(M% - 1, 1)

 

==={{header|QuickBasic}}===

BASIC runs out of stack space very quickly.

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

 

FUNCTION ack (m!, n!)

ack = ack(m - 1, ack(m, n - 1))

END IF

 

=={{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.

@echo off

set depth=0

set t=%errorlevel%

set /a depth-=1

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

@echo off

cmd/c ackermann.cmd %1 %2

A few test runs:

<pre>D:\Documents and Settings\Bruce>ack 0 4

{{works with|OpenBSD bc}}

{{Works with|GNU bc}}

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

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

}

}

 

=={{header|BCPL}}==

 

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

writef("ack(%n, %n) = %n*n", m, n, ack(m,n))

RESULTIS 0

 

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

>I;

b < <

 

A functional and recursive realization of the version above. Functions are realized by direct calls of functions via jumps (instruction <code>J</code>) to the entry points of two distinct functions:

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

 

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

 

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

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.

{{trans|ERRE}}

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

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

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

 

===Befunge-98===

{{works with|CCBI|2.1}}

>v

j

^ v:\_$1+

\^v_$1\1-

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.

 

=={{header|BQN}}==

A 0‿n: n+1;

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

A m‿n: A (m-1)‿(A m‿(n-1))

Example usage:

4

A 1‿4

11

A 3‿4

 

=={{header|Bracmat}}==

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)

= m n

. !arg:(?m,?n)

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

 

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

= m n value key eq chain

, find insert future stack va val

& !value

)

{{out|Some results}}

<pre>

</pre>

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

= m n

. !arg:(?m,?n)

| AckFormula$(!m+-1,AckFormula$(!m,!n+-1))

)

{{Out|Some results}}

<pre>AckFormula$(4,1):65533

 

=={{header|Brat}}==

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

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

}

 

 

=={{header|C}}==

Straightforward implementation per Ackermann definition:

 

int ackermann(int m, int n)

 

return 0;

{{out}}

<pre>A(0, 0) = 1

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

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

#include <stdlib.h>

#include <string.h>

 

return 0;

{{out}}

<pre>A(0, 0) = 1

Whee. Well, with some extra work, we calculated <i>one more</i> n value, big deal, right?

But see, <code>A(4, 2) = A(3, A(4, 1)) = A(3, 65533) = A(2, A(3, 65532)) = ...</code> you can see how fast it blows up. In fact, no amount of caching will help you calculate large m values; on the machine I use A(4, 2) segfaults because the recursions run out of stack space--not a whole lot I can do about it. At least it runs out of stack space <i>quickly</i>, unlike the first solution...

 

=={{header|C sharp|C#}}==

 

===Basic Version===

class Program

{

}

}

{{out}}

<pre>

 

===Efficient Version===

using System;

using System.Numerics;

}

}

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.

 

 

===Basic version===

 

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

}

}

 

===Efficient version===

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

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

#include <sstream>

#include <string>

<< text.substr(0, 80) << "\n...\n"

<< text.substr(text.length() - 80) << "\n";

<pre>

<pre>

 

=={{header|Chapel}}==

if m == 0 then

return n + 1;

else

return A(m - 1, A(m, n - 1));

 

=={{header|Clay}}==

if(m == 0)

return n + 1;

 

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

 

=={{header|CLIPS}}==

'''Functional solution'''

(?m ?n)

(if (= 0 ?m)

)

)

{{out|Example usage}}

<pre>CLIPS> (ackerman 0 4)

</pre>

'''Fact-based solution'''

(solve 0 4)

(solve 1 4)

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

<pre>CLIPS> (reset)

 

=={{header|Clojure}}==

(cond (zero? m) (inc n)

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

 

=={{header|CLU}}==

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

if m=0 then return(n+1)

stream$putl(po, "")

end

{{out}}

<pre> 1 2 3 4 5 6 7 8 9

 

=={{header|COBOL}}==

PROGRAM-ID. Ackermann.

 

 

GOBACK

 

=={{header|CoffeeScript}}==

if m is 0 then n + 1

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

 

=={{header|Comal}}==

0020 // Ackermann function

0030 //

0150 PRINT

0160 ENDFOR m#

{{out}}

<pre>1 2 3 4 5

 

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

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

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

More elaborately:

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

((1) (+ 2 n))

(loop for m from 0 to 4 do

(loop for n from (- 5 m) to (- 6 m) do

{{out}}<pre>A(0, 5) = 6

A(0, 6) = 7

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

BlackBox Component Builder

MODULE NpctAckerman;

 

END NpctAckerman.

Execute: ^Q NpctAckerman.Do<br/>

<pre>

 

=={{header|Coq}}==

 

 

Section FOLD.

match n with

end.

End FOLD.

Definition ackermann : nat → nat → nat :=

fold (λ g, fold g (g (S O))) S.

 

=={{header|Crystal}}==

{{trans|Ruby}}

if m == 0

n + 1

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

end

 

{{out}}

=={{header|D}}==

===Basic version===

if (m == 0)

return n + 1;

void main() {

assert(ackermann(2, 4) == 11);

 

===More Efficient Version===

{{trans|Mathematica}}

 

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

writefln("ackermann(4, 2)) (%d digits):\n%s...\n%s",

a.length, a[0 .. 94], a[$ - 96 .. $]);

 

{{out}}

=={{header|Dart}}==

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

 

main() {

print(A(3,5));

print(A(4,0));

 

=={{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.

+ 1 + # n+1

q

] sA

 

{{out}}

<pre>

 

=={{header|Delphi}}==

begin

if m = 0 then

else

Result := Ackermann(m-1, Ackermann(m, n - 1));

 

=={{header|Draco}}==

proc ack(word m, n) word:

if m=0 then n+1

writeln()

od

{{out}}

<pre> 1 2 3 4 5 6 7 8 9

 

=={{header|DWScript}}==

begin

if m = 0 then

Result := Ackermann(m-1, 1)

else Result := Ackermann(m-1, Ackermann(m, n-1));

 

=={{header|Dylan}}==

n + 1

end;

define method ack(m :: <integer>, n :: <integer>)

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

 

=={{header|E}}==

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

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

else { A(m-1, A(m,n-1)) }

 

=={{header|EasyLang}}==

.

 

=={{header|Egel}}==

def ackermann =

[ 0 N -> N + 1

| M 0 -> ackermann (M - 1) 1

| M N -> ackermann (M - 1) (ackermann M (N - 1)) ]

 

=={{header|Eiffel}}==

 

class

 

 

ackerman (m, n: NATURAL): NATURAL

do

if m = 0 then

Result := n + 1

Result := ackerman (m - 1, 1)

Result := ackerman (m - 1, ackerman (m, n - 1))

end

end

end

 

=={{header|Ela}}==

ack m 0 = ack (m - 1) 1

 

=={{header|Elena}}==

 

ackermann(m,n)

{

}

 

public program()

{

 

{{out}}

<pre>

 

=={{header|Elixir}}==

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

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

Enum.each(0..3, fn m ->

IO.puts Enum.map_join(0..6, " ", fn n -> Ackermann.ack(m, n) end)

 

{{out}}

 

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

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

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

(t (ackermann (1- m)

 

=={{header|Erlang}}==

 

-module(ackermann).

-export([ackermann/2]).

ackermann(M, N) when M > 0 andalso N > 0 ->

ackermann(M-1, ackermann(M, N-1)).

 

=={{header|ERRE}}==

substituted with the new ERRE control statements.

 

PROGRAM ACKERMAN

 

END FOR

END PROGRAM

 

Prints a list of Ackermann function values: from A(0,0) to A(3,9). Uses a stack to avoid

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

 

>M=zeros(1000,1000);

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

3 5 7 9 11 13

5 13 29 61 125 253

 

=={{header|Euphoria}}==

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

if m = 0 then

return n + 1

end for

puts( 1, "\n" )

 

=={{header|Ezhil}}==

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

 

 

முடி

 

=={{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.

match m, n with

| 0, n -> n + 1

 

do

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

let rec acker (m, n, k) =

match m,n with

| m, 0 -> acker ((m - 1), 1, k)

| m, n -> acker (m, (n - 1), (fun x -> acker ((m - 1), x, k)))

 

=={{header|Factor}}==

IN: ackermann

 

{ [ n 0 = ] [ m 1 - 1 ackermann ] }

[ m 1 - m n 1 - ackermann ackermann ]

 

=={{header|Falcon}}==

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

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

end

>

The above will output the below.

Formating options to make this pretty are available,

 

=={{header|FALSE}}==

\$$[%

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

]?]a: { j i }

 

 

=={{header|Fantom}}==

{

// assuming m,n are positive

}

}

{{out}}

<pre>

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

 

TestAckermann()

END FUNCTION

 

int Ackermann(int m, int n)

{

{

return Ackermann(m, n);

END DYNC

 

ENTER 0, 0

INVOKE Ackermann, m, n

LEAVE

RET 8

 

{{out}}

 

=={{header|Fermat}}==

{{out}}

<pre>

 

=={{header|Forth}}==

over 0= IF nip 1+ EXIT THEN

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

dup 0= IF 1+ recurse EXIT THEN

{{out|Example of use}}

<pre>FORTH> 0 0 acker . 1 ok

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

An optimized version:

over ( case statement)

0 over = if drop nip 1+ else

then

then then then then

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

IMPLICIT NONE

END FUNCTION Ackermann

 

 

=={{header|Free Pascal}}==

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

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

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre> 0 1 2 3 4 5 6 7 8 9 10 11

 

=={{header|FunL}}==

ackermann( 0, n ) = n + 1

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

 

for m <- 0..3, n <- 0..4

 

{{out}}

=={{header|Futhark}}==

 

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

if m == 0 then n + 1

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

else ackermann(m - 1, ackermann(m, n-1))

 

=={{header|FutureBasic}}==

include "NSLog.incl"

 

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

end fn = result

 

 

HandleEvents

 

Output:

=={{header|Fōrmulæ}}==

 

 

 

 

=={{header|Gambas}}==

If m = 0 Then

Return n + 1

Next

Next

 

=={{header|GAP}}==

if m = 0 then

return n + 1;

return fail;

fi;

 

=={{header|Genyris}}==

cond

(equal? m 0)

else

A (- m 1)

 

=={{header|GML}}==

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

var m, n;

m = argument0;

{

return (ackermann(m-1,ackermann(m,n-1,2),1))

 

=={{header|gnuplot}}==

print A (0, 4)

print A (1, 4)

print A (2, 4)

{{out}}

5

=={{header|Go}}==

===Classic version===

switch 0 {

case m:

}

return Ackermann(m - 1, Ackermann(m, n - 1))

===Expanded version===

switch {

case m == 0:

}

return Ackermann2(m - 1, Ackermann2(m, n - 1))

===Expanded version with arbitrary precision===

 

import (

)

}

{{out}}

<pre>

 

=={{header|Golfscript}}==

:_n; :_m;

_m 0= {_n 1+}

if}

if

 

=={{header|Groovy}}==

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

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

Test program:

{{out}}

<pre> 1 2 3 4 5 6 7 8 9

5 13 29 61 125 253 509 1021 2045</pre>

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

 

=={{header|Haskell}}==

ack 0 n = succ n

ack m 0 = ack (pred m) 1

 

main :: IO ()

{{out}}

<pre>1

 

Generating a list instead:

 

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

f a b = (aa, head aa) where aa = drop b a

 

 

=={{header|Haxe}}==

{

static public function main()

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

}

 

=={{header|Hoon}}==

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

?: =(m 0)

$(n 1, m (dec m))

$(m (dec m), n $(n (dec n)))

 

=={{header|Icon}} and {{header|Unicon}}==

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.

static memory

 

write()

}

{{out}}

<pre>

 

=={{header|Idris}}==

A Z n = S n

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

 

=={{header|Ioke}}==

{{trans|Clojure}}

cond(

m zero?, n succ,

n zero?, ackermann(m pred, 1),

ackermann(m pred, ackermann(m, n pred)))

 

=={{header|J}}==

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

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

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

{{out|Example use}}

4

1 ack 3

9

3 ack 3

J's stack was too small for me to compute <tt>4 ack 1</tt>.

===Alternative Primitive Recursive Version===

 

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.

{{out|Example use}}

1 2 3 4 5 6 7 8

2 3 4 5 6 7 8 9

5 Ack 0

65533

 

A structured derivation of Ack follows:

 

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

(Ack=. (3 -~ [ Buck 3 + ])f.) NB. Ackermann function-level code

 

=={{header|Java}}==

[[Category:Arbitrary precision]]

 

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

: ack(m.subtract(BigInteger.ONE),

n.equals(BigInteger.ZERO) ? BigInteger.ONE : ack(m, n.subtract(BigInteger.ONE)));

 

{{works with|Java|8+}}

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

public Object untypedField(FIELD field);

return (VALUE) untypedField(field);

}

import java.util.function.Function;

import java.util.function.Predicate;

}

}

import java.util.Stack;

import java.util.function.BinaryOperator;

}

}

{{Iterative version}}

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

*/

}

 

 

=={{header|JavaScript}}==

===ES5===

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

===Eliminating Tail Calls===

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

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

}

return N+1;

===Iterative, With Explicit Stack===

const stack = [];

for (;;) {

}

}

===Stackless Iterative===

function ack(M, N){

const next = new Float64Array(M + 1);

}

var args = process.argv;

 

{{out}}

 

===ES6===

'use strict';

 

// MAIN ---

return main();

{{Out}}

<pre>[4,5,9,61]</pre>

 

=={{header|Joy}}==

 

=={{header|jq}}==

{{ works with|jq|1.4}}

===Without Memoization===

def ack:

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

elif $n == 0 then [$m-1, 1] | ack

else [$m-1, ([$m, $n-1 ] | ack)] | ack

'''Example:'''

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

{{out}}

A(0,0) = 1

A(0,1) = 2

A(3,4) = 125

A(3,5) = 253

===With Memoization and Optimization===

# output [value, updatedCache]

def ack:

 

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

{{out}}

 

=={{header|Jsish}}==

From javascript entry.

 

function ack(m, n) {

ack(3,5) ==> 253

=!EXPECTEND!=

 

{{out}}

 

=={{header|Julia}}==

if m == 0

return n + 1

return ack(m-1,ack(m,n-1))

end

 

'''One-liner:'''

 

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

 

'''Benchmarking''':

 

=={{header|K}}==

 

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

YS26000;

RESTART; J999; J999;

J99; (tail recursion for A[m-1, A[m, n-1]]);

 

 

=={{header|Klingphix}}==

%n !n %m !m

msec print

 

 

=={{header|Klong}}==

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

 

=={{header|Kotlin}}==

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

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

.forEach(::println)

}

{{out}}

<pre>

 

=={{header|Lambdatalk}}==

{def ack

{lambda {:m :n}

{ack 4 1} // too much

-> ???

 

=={{header|Lasso}}==

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

y in generateSeries(0,8,2)

do stdoutnl(#x+', '#y+': ' + ackermann(#x, #y))

{{out}}

<pre>1, 0: 2

 

=={{header|LFE}}==

((0 n) (+ n 1))

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

 

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

 

Function Ackermann(m, n)

Ackermann = Ackermann((m - 1), Ackermann(m, (n - 1)))

End Select

 

=={{header|LiveCode}}==

switch

Case m = 0

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

end switch

 

=={{header|Logo}}==

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

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

output ack :i-1 ack :i :j-1

 

=={{header|Logtalk}}==

!,

V is N + 1.

N2 is N - 1,

ack(M, N2, V2),

 

=={{header|LOLCODE}}==

{{trans|C}}

 

HOW IZ I ackermann YR m AN YR n

IM OUTTA YR outer

 

 

=={{header|Lua}}==

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

 

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

#!/usr/bin/env luajit

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

printf("%Zd\n", ack(tonumber(arg[1]), arg[2] and tonumber(arg[2]) or 0))

end

 

{{out}}

 

=={{header|Lucid}}==

where

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

else ack(m-1, ack(m, n-1)) fi

fi;

 

=={{header|Luck}}==

if m==0 then n+1

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

else ackermann(m-1,ackermann(m,n-1))

 

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

}

Checkit

 

=={{header|M4}}==

{{out}}

<pre>61 </pre>

 

=={{header|MAD}}==

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

 

DIMENSION LIST(3000)

SET LIST TO LIST

VECTOR VALUES ACKF = $4HACK(,I1,1H,,I1,4H) = ,I4*$

END OF PROGRAM

 

{{out}}

ACK(3,7) = 1021

ACK(3,8) = 2045</pre>

 

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

end if

end proc:

 

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

end if

end proc:

This makes it possible to compute <code>Ackermann( 4, 1 )</code> and <code>Ackermann( 4, 2 )</code> essentially instantly, though <code>Ackermann( 4, 3 )</code> 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.

 

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

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

Two possible implementations would be:

Ackermann1[m_,n_]:=

If[m==0,n+1,

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

Ackermann2[m_,0]:=Ackermann1[m-1,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:

gives back:

Ackermann2[1,2] = 4

Ackermann2[1,3] = 5

Ackermann2[3,6] = 509

Ackermann2[3,7] = 1021

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

$RecursionLimit=Infinity;

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

Ackermann3[3,n_]:=5+8 (2^n-1);

Ackermann3[m_,0]:=Ackermann3[m-1,1];

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

Examples 2:

gives back:

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.

 

=={{header|MATLAB}}==

if m == 0

A = n+1;

A = ackermannFunction( m-1,ackermannFunction(m,n-1) );

end

 

=={{header|Maxima}}==

 

ackermann[m, n] := if m = 0 then n + 1

ackermann(4, n) - (tetration(2, n + 3) - 3);

subst(n = 2, %);

 

=={{header|MAXScript}}==

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

(

if m == 0 then

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

)

 

=={{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.

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

 

; M = integer(0) -> R = N + integer(1)

; N = integer(0) -> ack(M - integer(1), integer(1), R)

 

=={{header|min}}==

{{works with|min|0.19.3}}

:n :m

(

((true) (m 1 - m n 1 - ackermann ackermann))

) case

 

=={{header|MiniScript}}==

 

if m == 0 then return n+1

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

print "(" + m + ", " + n + "): " + ackermann(m, n)

end for

 

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

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

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

 

=={{header|ML/I}}==

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

===Program===

"" Ackermann function

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

a(3,1) => ACK(3,1)

a(3,2) => ACK(3,2)

{{out}}

a(0,1) => 2

a(0,2) => 3

a(3,1) => 13

a(3,2) => 29

 

=={{header|mLite}}==

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

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

 

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

 

Result

<pre>[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]</pre>

 

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

 

IMPORT ASCII, NumConv, InOut;

END;

InOut.WriteLn

{{out}}<pre>jan@Beryllium:~/modula/rosetta$ ackerman

1 2 3 4 5 6 7

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

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

 

FROM IO IMPORT Put;

Put("\n");

END;

{{out}}

<pre>1 2 3 4 5 6 7

 

=={{header|MUMPS}}==

If m=0 Quit n+1

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

Write $$Ackermann(1,8) ; 10

Write $$Ackermann(2,8) ; 19

 

=={{header|Neko}}==

Ackermann recursion, in Neko

Tectonics:

$print("Ackermann(", arg1, ",", arg2, "): ", ack(arg1,arg2), "\n")

catch problem

 

{{out}}

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

}

}

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

| _ => throw Exception("invalid inputs");

}

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

def ackermann = {

def A(m, n) {

A

}

 

=={{header|NetRexx}}==

options replace format comments java crossref symbols binary

 

end

return rval

 

=={{header|NewLISP}}==

#! /usr/local/bin/newlisp

 

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

(true (ackermann (- m 1) (ackermann m (dec n))))))

 

<pre>

 

=={{header|Nim}}==

 

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

let second = getNumber()

echo "Result: ", $ackermann(first, second)

 

=={{header|Nit}}==

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

 

#

# A simple straightforward recursive implementation.

end

print ""

 

Output:

 

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

 

IMPORT Out;

END;

Out.Ln

 

=={{header|Objeck}}==

{{trans|C#|C sharp}}

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

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

return -1;

}

<pre>

Ackermann(0, 0) = 1

 

=={{header|OCaml}}==

if m=0 then (n+1) else

if n=0 then (a (m-1) 1) else

or:

| 0, n -> (n+1)

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

with memoization using an hash-table:

 

let a m n =

let res = a (m, n) in

Hashtbl.add h (m, n) res;

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

for _m = 0 to m do

for _n = 0 to n do

done;

done;

=== Arbitrary precision ===

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

let one = unit_big_int

let zero = zero_big_int

if eq m zero then (succ n) else

if eq n zero then (a (pred m) one) else

compile with:

ocamlopt -o acker nums.cmxa acker.ml

=== Tail-Recursive ===

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

try Some(Hashtbl.find h v)

with Not_found -> None

a bounds caller todo m (n-1)

 

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

let one = unit_big_int

let zero = zero_big_int

(string_of_big_int n)

(string_of_big_int r);

 

=={{header|Octave}}==

if ( m == 0 )

r = n + 1;

for i = 0:3

disp(ackerman(i, 4));

 

=={{header|Oforth}}==

m ifZero: [ n 1+ return ]

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

 

=={{header|OOC}}==

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

if (m == 0) {

}

}

 

=={{header|ooRexx}}==

loop m = 0 to 3

loop n = 0 to 6

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

else return ackermann(m - 1, ackermann(m, n - 1))

{{out}}

<pre>

 

=={{header|Order}}==

 

#define ORDER_PP_DEF_8ack ORDER_PP_FN( \

(8else, 8ack(8dec(8X), 8ack(8X, 8dec(8Y)))))))

 

 

=={{header|Oz}}==

Oz has arbitrary precision integers.

 

fun {Ack M N}

in

 

 

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

Naive implementation.

if(m,

if(n,

n+1

)

 

=={{header|Pascal}}==

 

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

for m := 0 to 3 do

WriteLn('A(', m, ',', n, ') = ', ackermann(m,n));

 

=={{header|Perl}}==

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

my @memo;

sub A {

);

}

 

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

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:

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 bigint try=>"GMP";

 

print "ack2(3,4) is ", ack2(3,4), "\n";

print "ack2(4,1) is ", ack2(4,1), "\n";

{{output}}

<pre>ack2(3,4) is 125

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

instead of recursion. Very fast.

use warnings;

use Math::BigInt;

print "ack(4,2) has ", length(ack(4,2)), " digits\n";

 

 

=={{header|Phix}}==

=== native version ===

<span style="color: #008080;">function</span> <span style="color: #000000;">ack</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

{{trans|Go}}

{{libheader|Phix/mpfr}}

<span style="color: #000080;font-style:italic;">-- demo\rosetta\Ackermann.exw</span>

<span style="color: #008080;">include</span> <span style="color: #7060A8;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>

<span style="color: #000000;">ackermann_tests</span><span style="color: #0000FF;">()</span>

{{out}}

<pre>

 

=={{header|Phixmonti}}==

var n var m

enddef

 

 

=={{header|PHP}}==

{

if ( $m==0 )

 

echo ackermann( 3, 4 );

 

=={{header|Picat}}==

foreach(M in 0..3)

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

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

 

{{out}}

 

=={{header|PicoLisp}}==

(cond

((=0 X) (inc Y))

((=0 Y) (ack (dec X) 1))

 

=={{header|Piet}}==

 

=={{header|Pike}}==

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

}

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

}

 

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

declare (m, n) fixed (30);

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

else if m > 0 & n > 0 then return (Ackerman(m-1, Ackerman(m, n-1)));

return (0);

 

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

 

FUNCTION ackermann(pi_m IN NUMBER,

END LOOP;

END;

{{out}}

<pre>

 

=={{header|PostScript}}==

/n exch def

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

m 1 sub m n 1 sub ackermann ackermann

}if

{{libheader|initlib}}

[/.m /.n] let

{

{.m 0 gt .n 0 gt and} {.m pred .m .n pred A A} is?

} cond

 

=={{header|Potion}}==

if (m == 0): n + 1

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

ack(m, n) print

" " print.

 

=={{header|PowerBASIC}}==

DIM m AS QUAD, n AS QUAD

 

FUNCTION = Ackermann(m - 1, Ackermann(m, n - 1))

END IF

 

=={{header|PowerShell}}==

{{trans|PHP}}

if ($m -eq 0) {

return $n + 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 ($n in 0..6) {

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

}

Write-Host

{{out}}

<pre> 1 2 3 4 5 6 7

 

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

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

{

return (Get-Ackermann ($m - 1) (Get-Ackermann $m ($n - 1)))

}

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

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

 

$ackermann | Format-Wide {"{0,3}" -f $_} -Column 7 -Force

{{Out}}

<pre>

 

=={{header|Processing}}==

if (m == 0)

return n + 1;

println();

}

 

{{Out}}

m = 5 it throws 'maximum recursion depth exceeded'

 

 

def setup():

return ackermann(m - 1, 1)

else:

 

==={{header|Processing.R}}===

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

 

for (m in 0:3) {

for (n in 0:4) {

ackermann(m-1, ackermann(m, n-1))

}

 

{{out}}

=={{header|Prolog}}==

{{works with|SWI Prolog}}

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

 

=={{header|Pure}}==

A m 0 = A (m-1) 1 if m > 0;

 

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

#N canvas 741 265 450 436 10;

#X obj 83 111 t b l;

#X connect 15 0 10 0;

#X connect 16 0 10 0;

 

=={{header|PureBasic}}==

If m = 0

ProcedureReturn n + 1

EndProcedure

 

 

=={{header|Purity}}==

 

=={{header|Python}}==

===Python: Explicitly recursive===

{{works with|Python|2.5}}

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

Another version:

 

@lru_cache(None)

return ack2(M - 1, 1)

else:

{{out|Example of use}}

>>> sys.setrecursionlimit(3000)

>>> ack1(0,0)

1

>>> ack2(3,4)

From the Mathematica ack3 example:

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 (

Results confirm those of Mathematica for ack(4,1) and ack(4,2)

 

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.

 

 

def ack_ix(m, n):

stack.extend([m-1, m, n-1])

 

 

{{out}}

 

=={{header|Quackery}}==

[ over 0 = iff

[ nip 1 + ] done

ackermann ackermann ] resolves ackermann ( m n --> r )

 

'''Output:'''

<pre>8189</pre>

 

=={{header|R}}==

if ( m == 0 ) {

n+1

ackermann(m-1, ackermann(m, n-1))

}

print(ackermann(i, 4))

 

=={{header|Racket}}==

#lang racket

(define (ackermann m n)

[(zero? n) (ackermann (sub1 m) 1)]

[else (ackermann (sub1 m) (ackermann m (sub1 n)))]))

 

=={{header|Raku}}==

{{works with|Rakudo|2018.03}}

 

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(Int $m, 0 ) { A($m - 1, 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:

 

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

# Testing:

say A(4,1);

{{out}}

<pre>65533

]

]</pre>

 

=={{header|ReScript}}==

let _n = Sys.argv[3]

 

 

Js.log("ackermann(" ++ _m ++ ", " ++ _n ++ ") = "

 

{{out}}

=={{header|REXX}}==

===no optimization===

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

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

if m==0 then return n+1

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

{{out|output|text=&nbsp; when using the internal default input:}}

<pre style="height:60ex">

 

===optimized for m ≤ 2===

high=24

do j=0 to 3; say

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

if m==2 then return n + 3 + n

{{out|output|text=&nbsp; when using the internal default input:}}

<pre style="height:60ex">

<br><br>If the &nbsp; '''numeric digits 100''' &nbsp; were to be increased to &nbsp; '''20000''', &nbsp; then the value of &nbsp; '''Ackermann(4,2)''' &nbsp;

<br>(the last line of output) &nbsp; would be presented with the full &nbsp; '''19,729''' &nbsp; decimal digits.

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

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

end

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

Output note: &nbsp; <u>none</u> of the numbers shown below use recursion to compute.

 

=={{header|Ring}}==

{{trans|C#}}

for n = 0 to 4

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

ok

ok

{{out}}

<pre>Ackermann(0, 0) = 1

Ackermann(3, 4) = 125</pre>

 

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

beqz a1, npe #case m = 0

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

addi sp, sp, 4

jr t0, 0

 

=={{header|Ruby}}==

{{trans|Ada}}

if m == 0

n + 1

ack(m-1, ack(m, n-1))

end

Example:

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

{{out}}

<pre> 1 2 3 4 5 6 7

 

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

function ackermann(m, n)

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

 

=={{header|Rust}}==

if m == 0 {

n + 1

println!("{}", a); // 125

}

 

Or:

 

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

match (m, n) {

}

}

 

=={{header|Sather}}==

 

ackermann(m, n:INT):INT

end;

end;

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.

 

ackermann(m, n:INTI):INTI is

end;

end;

 

=={{header|Scala}}==

 

if (m==0) n+1

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

else ack(m-1, ack(m, n-1))

{{out|Example}}

<pre>

</pre>

Memoized version using a mutable hash map:

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

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

 

=={{header|Scheme}}==

(cond

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

((= n 0) (A (- m 1) 1))

 

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

 

(letrec ((A-stream

(cons-stream

(cond ((= b 0) 1)

((= n 1) (expt a b))

 

=={{header|Scilab}}==

function acker=ackermann(m,n)

global calls

printacker(i,j)

end

{{out}}

<pre style="height:20ex">ackermann(0,0)=1 calls=1

 

=={{header|Seed7}}==

result

var integer: result is 0;

result := ackermann(pred(m), ackermann(m, pred(n)));

end if;

Original source: [http://seed7.sourceforge.net/algorith/math.htm#ackermann]

 

=={{header|SETL}}==

 

(for m in [0..3])

end proc;

 

 

=={{header|Shen}}==

0 N -> (+ N 1)

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

M N -> (ack (- M 1)

 

=={{header|Sidef}}==

m == 0 ? (n + 1)

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

: (A(m - 1, A(m, n - 1))));

 

Alternatively, using multiple dispatch:

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

 

Calling the function:

 

=={{header|Simula}}==

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

INTEGER procedure

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

outint(Ackermann(g, p), 0); outimage

END

{{Output}}

<pre>Ackermann(4, 0) = 13

 

=={{header|Slate}}==

[

m isZero

ifTrue: [m - 1 ackermann: n]

ifFalse: [m - 1 ackermann: (m ackermann: n - 1)]]

 

=={{header|Smalltalk}}==

ackermann := [ :n :m |

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

 

(ackermann value: 0 value: 0) displayNl.

 

=={{header|SmileBASIC}}==

IF M==0 THEN

RETURN N+1

RETURN ACK(M-1,ACK(M,N-1))

ENDIF

 

=={{header|SNOBOL4}}==

{{works with|Macro Spitbol}}

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

ack ack = eq(m,0) n + 1 :s(return)

ack = eq(n,0) ack(m - 1,1) :s(return)

output = str; str = ''

n = 0; m = lt(m,3) m + 1 :s(L1)

{{out}}

<pre>1 2 3 4 5 6 7

 

=={{header|SNUSP}}==

| | Ackermann function

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

? ? | \<<<+>+>>-/

\>>+<<-/!==========/

One could employ [[:Category:Recursion|tail recursion]] elimination by replacing "@/#" with "/" in two places above.

 

=={{header|SPAD}}==

{{works with|FriCAS, OpenAxiom, Axiom}}

NNI ==> NonNegativeInteger

 

-- Example

matrix [[A(i,j) for i in 0..3] for j in 0..3]

 

{{out}}

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

With SQL PL:

--#SET TERMINATOR @

 

END WHILE;

END @

Output:

<pre>

 

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

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

 

=={{header|Stata}}==

function ackermann(m,n) {

if (m==0) {

11

125

 

=={{header|Swift}}==

if m == 0 {

return n+1

return ackerman(m-1, ackerman(m, n-1))

}

 

=={{header|Tcl}}==

===Simple===

{{trans|Ruby}}

if {$m == 0} {

expr {$n + 1}

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

if {$m == 0} {

expr {$n + 1}

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

 

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

# Some small tweaks...

interp recursionlimit {} 100000

But even with all this, you still run into problems calculating <math>\mathit{ack}(4,3)</math> as that's kind-of large…

 

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

 

:If not(M

:Then

:prgmACKERMAN

:End

 

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

 

:0→dim(L1

:Prompt M

:Prompt N

:prgmACKERMAN

 

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

 

=={{header|TorqueScript}}==

{

if(%m==0)

if(%m>0&&%n>0)

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

 

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

INTEGER PROC FNMathGetAckermannRecursiveI( INTEGER mI, INTEGER nI )

IF ( mI == 0 )

IF ( 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. 9

 

=={{header|TXR}}==

with memoization.

 

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

(argl (gensym "args-"))

(each ((i (range 0 3)))

(each ((j (range 0 4)))

 

{{out}}

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

{{works with|Bash}}

local m=$1

local n=$2

ack $((m-1)) $(ack $m $((n-1)))

fi

Example:

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

ack $m $n

done

echo

{{out}}

<pre>1 2 3 4 5 6 7

3 5 7 9 11 13 15

5 13 29 61 125 253 509</pre>

 

=={{header|Ursala}}==

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

#import nat

 

~&al^?\successor@ar ~&ar?(

^R/~&f ^/predecessor@al ^|R/~& ^|/~& predecessor,

test program for the first 4 by 7 numbers:

 

{{out}}

<pre>

=={{header|V}}==

{{trans|Joy}}

[ [pop zero?] [popd succ]

[zero?] [pop pred 1 ack]

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

using destructuring view

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

 

=={{header|Vala}}==

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

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

}

}

 

{{out}}

 

=={{header|VBA}}==

Dim result As Variant

Debug.Assert m >= 0

Debug.Print

Next i

<pre> n= 0 1 2 3 4 5 6 7

m=0 1 2 3 4 5 6 7 8

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

;Implementation

'~ dim depth

function ack(m, n)

end if

;Invocation

'~ depth = 0

wscript.echo ack( 2, 1 )

'~ depth = 0

{{out}}

<pre>

{{trans|Rexx}}

{{works with|Visual Basic|VB6 Standard}}

Option Explicit

Dim calls As Long

End If

End If

{{Out}}

<pre style="height:20ex">ackermann( 0 , 0 )= 1 calls= 1

ackermann( 4 , 1 )= out of stack space</pre>

 

if m == 0 {

return n + 1

}

}

 

{{out}}

 

=={{header|Wart}}==

(if m=0

n+1

(ackermann m-1 1)

:else

 

=={{header|WDTE}}==

== m 0 => + n 1;

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

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

 

=={{header|Wren}}==

var Ackermann

Ackermann = Fn.new {|m, n|

var p2 = pair[1]

System.print("A[%(p1), %(p2)] = %(Ackermann.call(p1, p2))")

 

{{out}}

{{works with|nasm}}

{{works with|windows}}

section .text

 

call ack1 ;return ack(M-1,1)

ret

 

=={{header|XLISP}}==

(cond

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

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

Test it:

Output (after a very perceptible pause):

<pre>4093</pre>

That worked well. Test it again:

Output (after another pause):

<pre>Abort: control stack overflow

 

=={{header|XPL0}}==

 

func Ackermann(M, N);

CrLf(0);

];

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

{{out}}

 

The following named template calculates the Ackermann function:

<xsl:template name="ackermann">

<xsl:param name="m"/>

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

</xsl:stylesheet>

 

Which will transform this input

<?xml version="1.0" ?>

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

</args>

</arguments>

 

into this output

 

=={{header|Yabasic}}==

if M = 0 return N + 1

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

 

print ack(3, 4)

 

What smart code can get. Fast as lightning!

{{trans|Phix}}

if m=0 then

return n+1

end sub

 

=={{header|Yorick}}==

if(m == 0)

return n + 1;

else

return ack(m - 1, ack(m, n - 1));

Example invocation:

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

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

write, "";

{{out}}

<pre>1 2 3 4 5 6 7

5 13 29 61 125 253 509</pre>

 

 

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

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

ORG $100

jr demo_start

 

txt_m_is: db "m=$"

{{out}}

<pre>

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

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

comment:

(=) m 0

comment:

#true

 

=={{header|Zig}}==

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

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

try stdout.print("\n", .{});

}

{{out}}

<pre> 1 2 3 4 5 6 7 8 9

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

{{trans|BASIC256}}

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

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

190 LET s(lev-1,3)=s(lev,3)

200 LET lev=lev-1

{{out}}

<pre>A(3,7) = 1021</pre>