Ackermann function: Difference between revisions

{{trans|Python}}

 

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

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

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

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

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

;

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

 

jmp demo

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

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

 

bits 16

org 100h

 

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

\ Ackermann function, illustrating use of "memoization".

 

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

=={{header|ABAP}}==

 

REPORT zhuberv_ackermann.

 

WRITE: / lv_result.

</syntaxhighlight>

 

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

 

=={{header|ActionScript}}==

{

if (m == 0)

 

=={{header|Ada}}==

 

procedure Test_Ackermann is

 

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

</syntaxhighlight>

 

 

agda --compile Ackermann.agda

./Ackermann

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

{{works with|A60}}

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

ackermann:=if m=0 then n+1

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

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

{{Trans|ALGOL 60}}

integer procedure ackermann( integer value m,n ) ;

if m=0 then n+1

=={{header|APL}}==

{{works with|Dyalog APL}}

0=1⊃⍵:1+2⊃⍵

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

 

=={{header|AppleScript}}==

if m is equal to 0 then return n + 1

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

=={{header|Argile}}==

{{works with|Argile|1.0.0}}

 

for each (val nat n) from 0 to 6

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

A (m - 1) (A m (n - 1))</syntaxhighlight>

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

 

=={{header|Arturo}}==

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

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

]

]</syntaxhighlight>

{{out}}

<pre>ackermann 0 0 => 1

ackermann 0 1 => 2

 

=={{header|ATS}}==

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

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

 

=={{header|AutoHotkey}}==

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

Return A(m-1,1)

=={{header|AutoIt}}==

=== Classical version ===

If ($m = 0) Then

Return $n+1

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

 

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

 

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

stack[0,0] = 3 # M

stack[0,1] = 7 # N

return</syntaxhighlight>

{{out}}

 

for m = 0 to 3

for n = 0 to 4

end if

end function</syntaxhighlight>

{{out}}

0 1 2

0 2 3

 

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

END

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

= FNackermann(M% - 1, FNackermann(M%, N%-1))</syntaxhighlight>

 

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

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

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

@echo off

cmd/c ackermann.cmd %1 %2

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

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

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

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

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;

}</syntaxhighlight>

Example usage:

4

A 1‿4

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)

 

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

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

 

=={{header|Brat}}==

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

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

 

p ackermann 3, 4 #Prints 125</syntaxhighlight>

 

=={{header|C}}==

Straightforward implementation per Ackermann definition:

 

int ackermann(int m, int n)

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>

 

A couple of alternative approaches...

 

#include <conio.h>

 

A couple of more iterative techniques...

 

#include <conio.h>

 

===Basic Version===

class Program

{

 

===Efficient Version===

using System;

using System.Numerics;

 

===Basic version===

 

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

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

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

#include <sstream>

#include <string>

 

=={{header|Chapel}}==

if m == 0 then

return n + 1;

 

=={{header|Clay}}==

if(m == 0)

return n + 1;

=={{header|CLIPS}}==

'''Functional solution'''

(?m ?n)

(if (= 0 ?m)

</pre>

'''Fact-based solution'''

(solve 0 4)

(solve 1 4)

 

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

 

=={{header|COBOL}}==

PROGRAM-ID. Ackermann.

 

 

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

 

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

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

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

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

More elaborately:

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

((1) (+ 2 n))

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

BlackBox Component Builder

MODULE NpctAckerman;

 

=={{header|Coq}}==

 

 

Section FOLD.

match n with

end.

End FOLD.

=={{header|Crystal}}==

{{trans|Ruby}}

if m == 0

n + 1

=={{header|D}}==

===Basic version===

if (m == 0)

return n + 1;

===More Efficient Version===

{{trans|Mathematica}}

 

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

=={{header|Dart}}==

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

 

main() {

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

 

=={{header|Delphi}}==

begin

if m = 0 then

 

=={{header|Draco}}==

proc ack(word m, n) word:

if m=0 then n+1

 

=={{header|DWScript}}==

begin

if m = 0 then

 

=={{header|Dylan}}==

n + 1

end;

 

=={{header|E}}==

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

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

 

=={{header|EasyLang}}==

.

 

=={{header|Egel}}==

def ackermann =

[ 0 N -> N + 1

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

 

class

ACKERMAN_EXAMPLE

 

=={{header|Ela}}==

ack m 0 = ack (m - 1) 1

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

 

=={{header|Elena}}==

 

ackermann(m,n)

{

}

 

public program()

{

 

}</syntaxhighlight>

{{out}}

 

=={{header|Elixir}}==

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

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

 

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

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

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

(t (ackermann (1- m)

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

 

=={{header|Erlang}}==

 

-module(ackermann).

-export([ackermann/2]).

substituted with the new ERRE control statements.

 

PROGRAM ACKERMAN

 

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

 

>M=zeros(1000,1000);

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

=={{header|Euphoria}}==

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

if m = 0 then

return n + 1

 

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

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.

let rec acker (m, n, k) =

match m,n with

 

=={{header|Factor}}==

IN: ackermann

 

 

=={{header|Falcon}}==

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

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

 

=={{header|FALSE}}==

\$$[%

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

 

=={{header|Fantom}}==

{

// assuming m,n are positive

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

A(3,8)</syntaxhighlight>

{{out}}

 

=={{header|Forth}}==

over 0= IF nip 1+ EXIT THEN

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

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

An optimized version:

over ( case statement)

0 over = if drop nip 1+ else

=={{header|Fortran}}==

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

IMPLICIT NONE

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

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

 

=={{header|FunL}}==

ackermann( 0, n ) = n + 1

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

=={{header|Futhark}}==

 

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

if m == 0 then n + 1

 

=={{header|FutureBasic}}==

include "NSLog.incl"

 

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

end fn = result

 

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

 

 

 

 

=={{header|Gambas}}==

If m = 0 Then

Return n + 1

 

=={{header|GAP}}==

if m = 0 then

return n + 1;

 

=={{header|Genyris}}==

cond

(equal? m 0)

=={{header|GML}}==

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

var m, n;

m = argument0;

 

=={{header|gnuplot}}==

print A (0, 4)

print A (1, 4)

=={{header|Go}}==

===Classic version===

switch 0 {

case m:

}</syntaxhighlight>

===Expanded version===

switch {

case m == 0:

}</syntaxhighlight>

===Expanded version with arbitrary precision===

 

import (

 

=={{header|Golfscript}}==

:_n; :_m;

_m 0= {_n 1+}

 

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

}</syntaxhighlight>

Test program:

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

{{out}}

 

=={{header|Hare}}==

 

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

 

=={{header|Haskell}}==

ack 0 n = succ n

ack m 0 = ack (pred m) 1

 

Generating a list instead:

 

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

 

=={{header|Haxe}}==

{

static public function main()

 

=={{header|Hoon}}==

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

?: =(m 0)

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

 

 

=={{header|Idris}}==

A Z n = S n

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

=={{header|Ioke}}==

{{trans|Clojure}}

cond(

m zero?, n succ,

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

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

{{out|Example use}}

4

1 ack 3

 

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

A structured derivation of Ack follows:

 

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

=={{header|Java}}==

[[Category:Arbitrary precision]]

 

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

 

{{works with|Java|8+}}

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

public Object untypedField(FIELD field);

}

}</syntaxhighlight>

import java.util.function.Function;

import java.util.function.Predicate;

}

}</syntaxhighlight>

import java.util.Stack;

import java.util.function.BinaryOperator;

}</syntaxhighlight>

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

}</syntaxhighlight>

===Eliminating Tail Calls===

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

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

}</syntaxhighlight>

===Iterative, With Explicit Stack===

const stack = [];

for (;;) {

}</syntaxhighlight>

===Stackless Iterative===

function ack(M, N){

const next = new Float64Array(M + 1);

 

===ES6===

'use strict';

 

 

=={{header|Joy}}==

 

=={{header|jq}}==

{{ works with|jq|1.4}}

===Without Memoization===

def ack:

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

end ;</syntaxhighlight>

'''Example:'''

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

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

{{out}}

A(0,0) = 1

A(0,1) = 2

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

===With Memoization and Optimization===

# output [value, updatedCache]

def ack:

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

</syntaxhighlight>

{{out}}

 

=={{header|Jsish}}==

From javascript entry.

 

function ack(m, n) {

 

=={{header|Julia}}==

if m == 0

return n + 1

 

'''One-liner:'''

 

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

@memoize ack3(m::Integer, n::Integer) = m == 0 ? n + 1 : n == 0 ? ack3(m - 1, 1) : ack3(m - 1, ack3(m, n - 1))</syntaxhighlight>

 

 

=={{header|K}}==

 

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

YS26000;

RESTART; J999; J999;

 

=={{header|Klingphix}}==

%n !n %m !m

 

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

 

=={{header|Lambdatalk}}==

{def ack

{lambda {:m :n}

 

=={{header|Lasso}}==

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

 

=={{header|LFE}}==

((0 n) (+ n 1))

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

 

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

 

Function Ackermann(m, n)

 

=={{header|LiveCode}}==

switch

Case m = 0

 

=={{header|Logo}}==

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

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

 

=={{header|Logtalk}}==

!,

V is N + 1.

=={{header|LOLCODE}}==

{{trans|C}}

 

HOW IZ I ackermann YR m AN YR n

 

=={{header|Lua}}==

if M == 0 then return N + 1 end

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

 

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

#!/usr/bin/env luajit

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

 

=={{header|Lucid}}==

where

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

 

=={{header|Luck}}==

if m==0 then n+1

else if n==0 then ackermann(m-1,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))))

 

=={{header|M4}}==

ack(3,3)</syntaxhighlight>

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

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

</syntaxhighlight>

 

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

 

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

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,

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,8] = 2045</syntaxhighlight>

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;

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

Examples 2:

Ackermann3[4, 2]</syntaxhighlight>

gives back:

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.

 

=={{header|MATLAB}}==

if m == 0

A = n+1;

 

=={{header|Maxima}}==

 

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

=={{header|MAXScript}}==

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

(

if m == 0 then

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

 

=={{header|min}}==

{{works with|min|0.19.3}}

:n :m

(

=={{header|MiniScript}}==

 

if m == 0 then return n+1

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

 

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

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

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

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(4,0) => ACK(4,0)</syntaxhighlight>

{{out}}

a(0,1) => 2

a(0,2) => 3

 

=={{header|mLite}}==

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

 

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

 

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

 

IMPORT ASCII, NumConv, InOut;

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

 

=={{header|MUMPS}}==

If m=0 Quit n+1

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

 

=={{header|Neko}}==

Ackermann recursion, in Neko

Tectonics:

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

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

</syntaxhighlight>

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

def ackermann = {

def A(m, n) {

 

=={{header|NetRexx}}==

options replace format comments java crossref symbols binary

 

 

=={{header|NewLISP}}==

#! /usr/local/bin/newlisp

 

 

=={{header|Nim}}==

 

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

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

 

#

# A simple straightforward recursive implementation.

 

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

 

IMPORT Out;

=={{header|Objeck}}==

{{trans|C#|C sharp}}

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

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

 

=={{header|OCaml}}==

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:

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

 

let a m n =

(res)</syntaxhighlight>

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

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

=== Tail-Recursive ===

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

try Some(Hashtbl.find h v)

with Not_found -> None

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

let one = unit_big_int

let zero = zero_big_int

 

=={{header|Octave}}==

if ( m == 0 )

r = n + 1;

 

=={{header|Oforth}}==

m ifZero: [ n 1+ return ]

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

 

=={{header|Ol}}==

; simple version

(define (A m n)

 

=={{header|OOC}}==

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

if (m == 0) {

 

=={{header|ooRexx}}==

loop m = 0 to 3

loop n = 0 to 6

 

=={{header|Order}}==

 

#define ORDER_PP_DEF_8ack ORDER_PP_FN( \

=={{header|Oz}}==

Oz has arbitrary precision integers.

 

fun {Ack M N}

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

Naive implementation.

if(m,

if(n,

 

=={{header|Pascal}}==

 

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

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

 

An implementation using ternary chaining:

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

$m == 0 ? $n + 1 :

 

Adding memoization and extra terms:

use bigint try=>"GMP";

 

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

instead of recursion. Very fast.

use warnings;

use Math::BigInt;

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

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

 

=={{header|Phixmonti}}==

var n var m

 

=={{header|PHP}}==

{

if ( $m==0 )

 

=={{header|Picat}}==

foreach(M in 0..3)

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

 

=={{header|PicoLisp}}==

(cond

((=0 X) (inc Y))

 

=={{header|Pike}}==

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

}

 

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

declare (m, n) fixed (30);

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

 

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

 

FUNCTION ackermann(pi_m IN NUMBER,

 

=={{header|PostScript}}==

/n exch def

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

}def</syntaxhighlight>

{{libheader|initlib}}

[/.m /.n] let

{

 

=={{header|Potion}}==

if (m == 0): n + 1

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

 

=={{header|PowerBASIC}}==

DIM m AS QUAD, n AS QUAD

 

=={{header|PowerShell}}==

{{trans|PHP}}

if ($m -eq 0) {

return $n + 1

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

foreach ($n in 0..6) {

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

 

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

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

{

</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 $_}}

 

 

=={{header|Processing}}==

if (m == 0)

return n + 1;

m = 5 it throws 'maximum recursion depth exceeded'

 

 

def setup():

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

 

for (m in 0:3) {

for (n in 0:4) {

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

ack(M, N, Ans) :- M>0, N>0, X is M-1, Y is N-1, ack(M, Y, Ans2), ack(X, Ans2, Ans).</syntaxhighlight>

 

=={{header|Pure}}==

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;

 

=={{header|PureBasic}}==

If m = 0

ProcedureReturn n + 1

 

=={{header|Purity}}==

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

 

===Python: Explicitly recursive===

{{works with|Python|2.5}}

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:

 

@lru_cache(None)

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

{{out|Example of use}}

>>> sys.setrecursionlimit(3000)

>>> ack1(0,0)

125</syntaxhighlight>

From the Mathematica ack3 example:

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

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

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

 

=={{header|Quackery}}==

[ over 0 = iff

[ nip 1 + ] done

 

=={{header|R}}==

if ( m == 0 ) {

n+1

}

}</syntaxhighlight>

print(ackermann(i, 4))

}</syntaxhighlight>

 

=={{header|Racket}}==

#lang racket

(define (ackermann m n)

{{works with|Rakudo|2018.03}}

 

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

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

}</syntaxhighlight>

An implementation using multiple dispatch:

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>

 

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 }

]

]</pre>

 

=={{header|ReScript}}==

let _n = Sys.argv[3]

 

=={{header|REXX}}==

===no optimization===

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

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

 

===optimized for m ≤ 2===

high=24

do j=0 to 3; say

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

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

=={{header|Ring}}==

{{trans|C#}}

for n = 0 to 4

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

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

jr t0, 0

</syntaxhighlight>

 

=={{header|Ruby}}==

{{trans|Ada}}

if m == 0

n + 1

end</syntaxhighlight>

Example:

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

end</syntaxhighlight>

 

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

function ackermann(m, n)

 

=={{header|Rust}}==

if m == 0 {

n + 1

Or:

 

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

match (m, n) {

 

=={{header|Sather}}==

 

ackermann(m, n:INT):INT

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.

 

ackermann(m, n:INTI):INTI is

=={{header|Scala}}==

 

if (m==0) n+1

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

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

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

 

=={{header|Scilab}}==

function acker=ackermann(m,n)

global calls

 

=={{header|Seed7}}==

result

var integer: result is 0;

end func;</syntaxhighlight>

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

 

=={{header|SETL}}==

 

(for m in [0..3])

 

=={{header|Shen}}==

0 N -> (+ N 1)

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

 

=={{header|Sidef}}==

m == 0 ? (n + 1)

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

 

Alternatively, using multiple dispatch:

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

func A(m, n) { A(m-1, A(m, n-1)) }</syntaxhighlight>

 

Calling the function:

 

=={{header|Simula}}==

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

INTEGER procedure

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

 

=={{header|Slate}}==

[

m isZero

 

=={{header|Smalltalk}}==

ackermann := [ :n :m |

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

 

=={{header|SmileBASIC}}==

IF M==0 THEN

RETURN N+1

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

 

=={{header|SNUSP}}==

| | Ackermann function

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

=={{header|SPAD}}==

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

NNI ==> NonNegativeInteger

 

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

With SQL PL:

--#SET TERMINATOR @

 

 

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

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

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

 

=={{header|Stata}}==

function ackermann(m,n) {

if (m==0) {

 

=={{header|Swift}}==

if m == 0 {

return n+1

===Simple===

{{trans|Ruby}}

if {$m == 0} {

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}

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

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

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

 

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

 

=={{header|TorqueScript}}==

{

if(%m==0)

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

}</syntaxhighlight>

 

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

INTEGER PROC FNMathGetAckermannRecursiveI( INTEGER mI, INTEGER nI )

IF ( mI == 0 )

with memoization.

 

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

(argl (gensym "args-"))

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

{{works with|Bash}}

local m=$1

local n=$2

}</syntaxhighlight>

Example:

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

ack $m $n

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

 

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

test program for the first 4 by 7 numbers:

 

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

=={{header|V}}==

{{trans|Joy}}

[ [pop zero?] [popd succ]

[zero?] [pop pred 1 ack]

] when].</syntaxhighlight>

using destructuring view

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

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

 

=={{header|Vala}}==

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

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

 

=={{header|VBA}}==

Dim result As Variant

Debug.Assert m >= 0

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

;Invocation

'~ depth = 0

wscript.echo ack( 2, 1 )

{{trans|Rexx}}

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

Option Explicit

Dim calls As Long

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

 

if m == 0 {

return n + 1

 

=={{header|Wart}}==

(if m=0

n+1

 

=={{header|WDTE}}==

== m 0 => + n 1;

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

 

=={{header|Wren}}==

var Ackermann

Ackermann = Fn.new {|m, n|

{{works with|nasm}}

{{works with|windows}}

section .text

 

 

=={{header|XLISP}}==

(cond

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

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

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

 

The following named template calculates the Ackermann function:

<xsl:template name="ackermann">

<xsl:param name="m"/>

 

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

 

Which will transform this input

<?xml version="1.0" ?>

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

 

=={{header|Yabasic}}==

if M = 0 return N + 1

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

What smart code can get. Fast as lightning!

{{trans|Phix}}

if m=0 then

return n+1

 

=={{header|Yorick}}==

if(m == 0)

return n + 1;

}</syntaxhighlight>

Example invocation:

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

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

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

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

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

comment:

(=) m 0

 

=={{header|Zig}}==

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

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

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

{{trans|BASIC256}}

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

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

{{out}}

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