Ackermann function: Difference between revisions
added RPL
(added RPL) |
|||
(44 intermediate revisions by 25 users not shown) | |||
Line 34:
{{trans|Python}}
<
R I m == 0 {(n + 1)
} E I m == 1 {(n + 2)
Line 44:
print(ack2(0, 0))
print(ack2(3, 4))
print(ack2(4, 1))</
{{out}}
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.
<
&LAB XDECO ®,&TARGET
.*-----------------------------------------------------------------*
Line 155:
STACKLEN EQU *-STACK
YREGS
END ACKERMAN</
{{out}}
<pre style="height:20ex">
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).
<
; Ackermann function for Motorola 68000 under AmigaOs 2+ by Thorham
;
Line 310:
outString
dc.b "ackermann (%ld,%ld) is: %ld",10,0</
=={{header|8080 Assembly}}==
Line 317:
and <code>n ∊ [0,9)</code>, on a real 8080 this takes a little over two minutes.
<
jmp demo
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Line 397:
db '*****' ; Placeholder for number
pnum: db 9,'$'
nl: db 13,10,'$'</
{{out}}
Line 410:
This code does 16-bit math just like the 8080 version.
<
bits 16
org 100h
Line 469:
db '*****' ; Placeholder for ASCII number
pnum: db 9,'$'
nl: db 13,10,'$'</
{{out}}
Line 479:
=={{header|8th}}==
<syntaxhighlight lang="forth">
\ Ackermann function, illustrating use of "memoization".
Line 554:
4 1 ackOf
bye</
{{out|The output}}
Line 571:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B or android 64 bits */
/* program ackermann64.s */
Line 693:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
{{Output}}
<pre>
Line 739:
=={{header|ABAP}}==
<syntaxhighlight lang="abap">
REPORT zhuberv_ackermann.
Line 785:
lv_result = zcl_ackermann=>ackermann( m = pa_m n = pa_n ).
WRITE: / lv_result.
</syntaxhighlight>
=={{header|ABC}}==
<syntaxhighlight lang="ABC">HOW TO RETURN m ack n:
SELECT:
m=0: RETURN n+1
m>0 AND n=0: RETURN (m-1) ack 1
m>0 AND n>0: RETURN (m-1) ack (m ack (n-1))
FOR m IN {0..3}:
FOR n IN {0..8}:
WRITE (m ack n)>>6
WRITE /</syntaxhighlight>
{{out}}
<pre> 1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 10
3 5 7 9 11 13 15 17 19
5 13 29 61 125 253 509 1021 2045</pre>
=={{header|Acornsoft Lisp}}==
{{trans|Common Lisp}}
<syntaxhighlight lang="lisp">
(defun ack (m n)
(cond ((zerop m) (add1 n))
((zerop n) (ack (sub1 m) 1))
(t (ack (sub1 m) (ack m (sub1 n))))))
</syntaxhighlight>
{{Out}}
<pre>
Evaluate : (ack 3 5)
Value is : 253
</pre>
=={{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]
Line 845 ⟶ 880:
OD
OD
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Ackermann_function.png Screenshot from Atari 8-bit computer]
Line 872 ⟶ 907:
=={{header|ActionScript}}==
<
{
if (m == 0)
Line 884 ⟶ 919:
return ackermann(m - 1, ackermann(m, n - 1));
}</
=={{header|Ada}}==
<
procedure Test_Ackermann is
Line 907 ⟶ 942:
New_Line;
end loop;
end Test_Ackermann;</
The implementation does not care about arbitrary precision numbers because the Ackermann function does not only grow, but also slow quickly, when computed recursively.
{{out}} the first 4x7 Ackermann's numbers:
Line 916 ⟶ 951:
=={{header|Agda}}==
{{works with|Agda|2.
{{libheader|agda-stdlib
<
module Ackermann where
open import Data.Nat using (ℕ ; zero ; suc ; _+_)
ack : ℕ → ℕ → ℕ
ack zero n = n + 1
ack (suc m) zero = ack m 1
ack (suc m) (suc n) = ack m (ack (suc m) n)
open import Agda.Builtin.IO using (IO)
open import Agda.Builtin.Unit using (⊤)
open import Agda.Builtin.String using (String)
open import Data.Nat.Show using (show)
postulate putStrLn : String → IO ⊤
{-# FOREIGN GHC import qualified Data.Text as T #-}
{-# COMPILE GHC putStrLn = putStrLn . T.unpack #-}
main : IO ⊤
main = putStrLn (show (ack 3 9))
-- Output:
-- 4093
</syntaxhighlight>
The Unicode characters can be entered in Emacs Agda as follows:
* ℕ : \bN
* → : \to
* ⊤ : \top
Running in Bash:
<
agda --compile Ackermann.agda
./Ackermann
</syntaxhighlight>
{{out}}
Line 947 ⟶ 1,000:
=={{header|ALGOL 60}}==
{{works with|A60}}
<
integer procedure ackermann(m,n);value m,n;integer m,n;
ackermann:=if m=0 then n+1
Line 958 ⟶ 1,011:
outstring(1,"\n")
end
end </
{{out}}
<pre>
Line 972 ⟶ 1,025:
{{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:
Line 992 ⟶ 1,045:
OD
END # test ackermann #;
test ackermann</
{{out}}
<pre>
Line 1,003 ⟶ 1,056:
=={{header|ALGOL W}}==
{{Trans|ALGOL 60}}
<
integer procedure ackermann( integer value m,n ) ;
if m=0 then n+1
Line 1,012 ⟶ 1,065:
for n := 1 until 6 do writeon( ackermann( m, n ) );
end for_m
end.</
{{out}}
<pre>
Line 1,023 ⟶ 1,076:
=={{header|APL}}==
{{works with|Dyalog APL}}
<
0=1⊃⍵:1+2⊃⍵
0=2⊃⍵:∇(¯1+1⊃⍵)1
∇(¯1+1⊃⍵),∇(1⊃⍵),¯1+2⊃⍵
}</
=={{header|AppleScript}}==
<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)
return ackermann(m - 1, ackermann(m, n - 1))
end ackermann</
=={{header|Argile}}==
{{works with|Argile|1.0.0}}
<
for each (val nat n) from 0 to 6
Line 1,048 ⟶ 1,100:
return (n+1) if m == 0
return (A (m - 1) 1) if n == 0
A (m - 1) (A m (n - 1))</
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI or android 32 bits */
/* program ackermann.s */
Line 1,171 ⟶ 1,224:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
{{Output}}
<pre>
Line 1,217 ⟶ 1,270:
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">ackermann: function [m,n][
(m=0)? -> n+1 [
(n=0)? -> ackermann m-1 1
Line 1,229 ⟶ 1,281:
print ["ackermann" a b "=>" ackermann a b]
]
]</
{{out}}
<pre>ackermann 0 0 => 1
ackermann 0 1 => 2
Line 1,255 ⟶ 1,305:
=={{header|ATS}}==
<
{m,n:nat} .<m,n>.
(m: int m, n: int n): Nat =
Line 1,262 ⟶ 1,312:
| (_, 0) =>> ackermann (m-1, 1)
| (_, _) =>> ackermann (m-1, ackermann (m, n-1))
// end of [ackermann]</
=={{header|AutoHotkey}}==
<
If (m > 0) && (n = 0)
Return A(m-1,1)
Line 1,275 ⟶ 1,325:
; Example:
MsgBox, % "A(1,2) = " A(1,2)</
=={{header|AutoIt}}==
=== Classical version ===
<
If ($m = 0) Then
Return $n+1
Line 1,289 ⟶ 1,339:
EndIf
EndIf
EndFunc</
=== Classical + cache implementation ===
Line 1,295 ⟶ 1,345:
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
Line 1,312 ⟶ 1,362:
Return $return
EndIf
EndFunc ;==>Ackermann</
=={{header|AWK}}==
<
{
if ( m == 0 ) {
Line 1,332 ⟶ 1,382:
}
}
}</
=={{header|Babel}}==
<
{((0 0) (0 1) (0 2)
(0 3) (0 4) (1 0)
Line 1,366 ⟶ 1,416:
if }
zero?!: { 0 = }</syntaxhighlight>
{{out}}
<pre>A(0 0 ) = 1
A(0 1 ) = 2
A(0 2 ) = 3
Line 1,391 ⟶ 1,439:
=={{header|BASIC}}==
==={{header|Applesoft BASIC}}===
{{works with|Chipmunk Basic}}
<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,414 ⟶ 1,463:
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
270 M = M - 1 : N = ACK : R%(SP) = 1 : SP = SP + 1 : GOTO 200</
==={{header|BASIC256}}===
<
stack[0,0] = 3 # M
stack[0,1] = 7 # N
Line 1,449 ⟶ 1,498:
stack[lev-1,2] = stack[lev,2]
lev = lev-1
return</
{{out}}
<pre> A(3,7) = 1021</pre>
<
for m = 0 to 3
for n = 0 to 4
Line 1,473 ⟶ 1,520:
endif
end if
end function</
{{out}}
<pre>0 0 1
0 1 2
0 2 3
Line 1,499 ⟶ 1,544:
==={{header|BBC BASIC}}===
<
END
Line 1,505 ⟶ 1,550:
IF M% = 0 THEN = N% + 1
IF N% = 0 THEN = FNackermann(M% - 1, 1)
= FNackermann(M% - 1, FNackermann(M%, N%-1))</
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
<syntaxhighlight lang="qbasic">100 for m = 0 to 4
110 print using "###";m;
120 for n = 0 to 6
130 if m = 4 and n = 1 then goto 160
140 print using "######";ack(m,n);
150 next n
160 print
170 next m
180 end
190 sub ack(m,n)
200 if m = 0 then ack = n+1
210 if m > 0 and n = 0 then ack = ack(m-1,1)
220 if m > 0 and n > 0 then ack = ack(m-1,ack(m,n-1))
230 end sub</syntaxhighlight>
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">FUNCTION ack(m, n)
IF m = 0 THEN LET ack = n+1
IF m > 0 AND n = 0 THEN LET ack = ack(m-1, 1)
IF m > 0 AND n > 0 THEN LET ack = ack(m-1, ack(m, n-1))
END FUNCTION
FOR m = 0 TO 4
PRINT USING "###": m;
FOR n = 0 TO 8
! A(4, 1) OR higher will RUN OUT of stack memory (default 1M)
! change n = 1 TO n = 2 TO calculate A(4, 2), increase stack!
IF m = 4 AND n = 1 THEN EXIT FOR
PRINT USING "######": ack(m, n);
NEXT n
PRINT
NEXT m
END</syntaxhighlight>
==={{header|QuickBasic}}===
Line 1,511 ⟶ 1,593:
BASIC runs out of stack space very quickly.
The call <tt>ack(3, 4)</tt> gives a stack error.
<
FUNCTION ack (m!, n!)
Line 1,522 ⟶ 1,604:
ack = ack(m - 1, ack(m, n - 1))
END IF
END FUNCTION</
=={{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
Line 1,556 ⟶ 1,638:
set t=%errorlevel%
set /a depth-=1
if %depth%==0 ( exit %t% ) else ( exit /b %t% )</
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
echo Ackermann(%1, %2)=%errorlevel%</
A few test runs:
<pre>D:\Documents and Settings\Bruce>ack 0 4
Line 1,579 ⟶ 1,661:
{{works with|OpenBSD bc}}
{{Works with|GNU bc}}
<
if ( m == 0 ) return (n+1);
if ( n == 0 ) return (ack(m-1, 1));
Line 1,590 ⟶ 1,672:
}
}
quit</
=={{header|BCPL}}==
<
LET ack(m, n) = m=0 -> n+1,
Line 1,603 ⟶ 1,685:
writef("ack(%n, %n) = %n*n", m, n, ack(m,n))
RESULTIS 0
}</
=={{header|beeswax}}==
Line 1,609 ⟶ 1,691:
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,615 ⟶ 1,697:
>I;
b < <
</syntaxhighlight>
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:
Line 1,625 ⟶ 1,707:
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))
_ii1FJ input function. Input m,n, then execute Ackermann(m,n)</
Highly optimized and fast version, returns A(4,1)/A(5,0) almost instantaneously:
<
>Mf@Ph?@g@2h@Mf@Php if m>4 and n>0 => replace m,n with m-1,m,n-1
>~4~L#1~2hg'd?1f@hgM?f2h p if m>4 and n=0 => replace m,n with m-1,1
Line 1,642 ⟶ 1,724:
z b < < <
d <
</syntaxhighlight>
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.
Line 1,651 ⟶ 1,733:
{{trans|ERRE}}
Since Befunge-93 doesn't have recursive capabilities we need to use an iterative algorithm.
<
@v:\<vp0 0:-1<\+<
^>00p>:#^_$1+\:#^_$.
</syntaxhighlight>
===Befunge-98===
{{works with|CCBI|2.1}}
<
>v
j
Line 1,665 ⟶ 1,747:
^ v:\_$1+
\^v_$1\1-
u^>1-0fp:1-\0fg101-</
The program reads two integers (first m, then n) from command line, idles around funge space, then outputs the result of the Ackerman function.
Since the latter is calculated truly recursively, the execution time becomes unwieldy for most m>3.
=={{header|Binary Lambda Calculus}}==
The Ackermann function on Church numerals (arbitrary precision), as shown in https://github.com/tromp/AIT/blob/master/fast_growing_and_conjectures/ackermann.lam is the 63 bit BLC
program
<pre>010000010110000001010111110101100010110000000011100101111011010</pre>
=={{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:
<syntaxhighlight lang="text"> A 0‿3
4
A 1‿4
Line 1,683 ⟶ 1,772:
11
A 3‿4
125</
=={{header|Bracmat}}==
Line 1,690 ⟶ 1,779:
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)
Line 1,697 ⟶ 1,786:
| 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".
Line 1,705 ⟶ 1,794:
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
Line 1,765 ⟶ 1,854:
& !value
)
& new$hash:?cache</
{{out|Some results}}
<pre>
Line 1,774 ⟶ 1,863:
</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)
Line 1,784 ⟶ 1,873:
| AckFormula$(!m+-1,AckFormula$(!m,!n+-1))
)
)</
{{Out|Some results}}
<pre>AckFormula$(4,1):65533
Line 1,792 ⟶ 1,881:
=={{header|Brat}}==
<
when { m == 0 } { n + 1 }
{ m > 0 && n == 0 } { ackermann(m - 1, 1) }
Line 1,798 ⟶ 1,887:
}
p ackermann 3, 4 #Prints 125</
=={{header|Bruijn}}==
<syntaxhighlight lang="bruijn">:import std/Combinator .
:import std/Number/Unary U
:import std/Math .
# unary ackermann
ackermann-unary [0 [[U.inc 0 1 (+1u)]] U.inc]
:test (ackermann-unary (+0u) (+0u)) ((+1u))
:test (ackermann-unary (+3u) (+4u)) ((+125u))
# ternary ackermann (lower space complexity)
ackermann-ternary y [[[=?1 ++0 (=?0 (2 --1 (+1)) (2 --1 (2 1 --0)))]]]
:test ((ackermann-ternary (+0) (+0)) =? (+1)) ([[1]])
:test ((ackermann-ternary (+3) (+4)) =? (+125)) ([[1]])</syntaxhighlight>
=={{header|C}}==
Straightforward implementation per Ackermann definition:
<
int ackermann(int m, int n)
Line 1,819 ⟶ 1,925:
return 0;
}</
{{out}}
<pre>A(0, 0) = 1
Line 1,842 ⟶ 1,948:
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>
Line 1,882 ⟶ 1,988:
return 0;
}</
{{out}}
<pre>A(0, 0) = 1
Line 1,908 ⟶ 2,014:
A couple of alternative approaches...
<
#include <conio.h>
Line 2,007 ⟶ 2,113:
//getch();
return 0;
}</
A couple of more iterative techniques...
<
#include <conio.h>
Line 2,156 ⟶ 2,262:
//getch();
return 0;
}</
A few further tweaks/optimizations may be possible.
Line 2,163 ⟶ 2,269:
===Basic Version===
<
class Program
{
Line 2,194 ⟶ 2,300:
}
}
}</
{{out}}
<pre>
Line 2,220 ⟶ 2,326:
===Efficient Version===
<
using System;
using System.Numerics;
Line 2,348 ⟶ 2,454:
}
}
</syntaxhighlight>
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.
Line 2,354 ⟶ 2,460:
===Basic version===
<
unsigned int ackermann(unsigned int m, unsigned int n) {
Line 2,373 ⟶ 2,479:
}
}
</syntaxhighlight>
===Efficient version===
Line 2,379 ⟶ 2,485:
C++11 with boost's big integer type. Compile with:
g++ -std=c++11 -I /path/to/boost ackermann.cpp.
<
#include <sstream>
#include <string>
Line 2,432 ⟶ 2,538:
<< text.substr(0, 80) << "\n...\n"
<< text.substr(text.length() - 80) << "\n";
}</
<pre>
<pre>
Line 2,483 ⟶ 2,589:
=={{header|Chapel}}==
<
if m == 0 then
return n + 1;
Line 2,490 ⟶ 2,596:
else
return A(m - 1, A(m, n - 1));
}</
=={{header|Clay}}==
<
if(m == 0)
return n + 1;
Line 2,500 ⟶ 2,606:
return ackermann(m - 1, ackermann(m, n - 1));
}</
=={{header|CLIPS}}==
'''Functional solution'''
<
(?m ?n)
(if (= 0 ?m)
Line 2,513 ⟶ 2,619:
)
)
)</
{{out|Example usage}}
<pre>CLIPS> (ackerman 0 4)
Line 2,525 ⟶ 2,631:
</pre>
'''Fact-based solution'''
<
(solve 0 4)
(solve 1 4)
Line 2,592 ⟶ 2,698:
(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)
Line 2,620 ⟶ 2,726:
=={{header|Clojure}}==
<
(cond (zero? m) (inc n)
(zero? n) (ackermann (dec m) 1)
:else (ackermann (dec m) (ackermann m (dec n)))))</
=={{header|CLU}}==
<
ack = proc (m, n: int) returns (int)
if m=0 then return(n+1)
Line 2,644 ⟶ 2,750:
stream$putl(po, "")
end
end start_up </
{{out}}
<pre> 1 2 3 4 5 6 7 8 9
Line 2,652 ⟶ 2,758:
=={{header|COBOL}}==
<
PROGRAM-ID. Ackermann.
Line 2,683 ⟶ 2,789:
GOBACK
.</
=={{header|CoffeeScript}}==
<
if m is 0 then n + 1
else if m > 0 and n is 0 then ackermann m - 1, 1
else ackermann m - 1, ackermann m, n - 1</
=={{header|Comal}}==
<
0020 // Ackermann function
0030 //
Line 2,708 ⟶ 2,814:
0150 PRINT
0160 ENDFOR m#
0170 END</
{{out}}
<pre>1 2 3 4 5
Line 2,716 ⟶ 2,822:
=={{header|Common Lisp}}==
<
(cond ((zerop m) (1+ n))
((zerop n) (ackermann (1- m) 1))
(t (ackermann (1- m) (ackermann m (1- n))))))</
More elaborately:
<
(case m ((0) (1+ n))
((1) (+ 2 n))
Line 2,730 ⟶ 2,836:
(loop for m from 0 to 4 do
(loop for n from (- 5 m) to (- 6 m) do
(format t "A(~d, ~d) = ~d~%" m n (ackermann m n))))</
{{out}}<pre>A(0, 5) = 6
A(0, 6) = 7
Line 2,744 ⟶ 2,850:
=={{header|Component Pascal}}==
BlackBox Component Builder
<
MODULE NpctAckerman;
Line 2,774 ⟶ 2,880:
END NpctAckerman.
</syntaxhighlight>
Execute: ^Q NpctAckerman.Do<br/>
<pre>
Line 2,785 ⟶ 2,891:
=={{header|Coq}}==
===Standard===
<syntaxhighlight lang="coq">
Fixpoint ack (m : nat) : nat -> nat :=
fix ack_m
| S
| S pn => ack pm (ack_m pn)
end
end.
(*
Example:
A(3, 2) = 29
*)
Eval compute in ack 3 2.
</syntaxhighlight>
{{out}}
<pre>
= 29
: nat
</pre>
===Using fold===
<syntaxhighlight lang="coq">
Require Import Utf8.
Section FOLD.
Context {A : Type} (f : A → A) (a : A).
Fixpoint fold (n : nat) : A :=
match n with
| O => a
| S
end.
End FOLD.
Line 2,809 ⟶ 2,934:
Definition ackermann : nat → nat → nat :=
fold (λ g, fold g (g (S O))) S.
</syntaxhighlight>
=={{header|Crystal}}==
{{trans|Ruby}}
<
if m == 0
n + 1
Line 2,827 ⟶ 2,952:
puts (0..6).map { |n| ack(m, n) }.join(' ')
end
</syntaxhighlight>
{{out}}
Line 2,839 ⟶ 2,964:
=={{header|D}}==
===Basic version===
<
if (m == 0)
return n + 1;
Line 2,849 ⟶ 2,974:
void main() {
assert(ackermann(2, 4) == 11);
}</
===More Efficient Version===
{{trans|Mathematica}}
<
BigInt ipow(BigInt base, BigInt exp) pure nothrow {
Line 2,896 ⟶ 3,021:
writefln("ackermann(4, 2)) (%d digits):\n%s...\n%s",
a.length, a[0 .. 94], a[$ - 96 .. $]);
}</
{{out}}
Line 2,930 ⟶ 3,055:
=={{header|Dart}}==
no caching, the implementation takes ages even for A(4,1)
<
main() {
Line 2,942 ⟶ 3,067:
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
Line 2,968 ⟶ 3,093:
] sA
3 9 lA x f</
{{out}}
<pre>
Line 2,975 ⟶ 3,100:
=={{header|Delphi}}==
<
begin
if m = 0 then
Line 2,983 ⟶ 3,108:
else
Result := Ackermann(m-1, Ackermann(m, n - 1));
end;</
=={{header|Draco}}==
<
proc ack(word m, n) word:
if m=0 then n+1
Line 3,003 ⟶ 3,128:
writeln()
od
corp</
{{out}}
<pre> 1 2 3 4 5 6 7 8 9
Line 3,011 ⟶ 3,136:
=={{header|DWScript}}==
<
begin
if m = 0 then
Line 3,018 ⟶ 3,143:
Result := Ackermann(m-1, 1)
else Result := Ackermann(m-1, Ackermann(m, n-1));
end;</
=={{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)
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}}==
<syntaxhighlight lang="text">
func
if
elif
return ackerm (m - 1) 1
else
.
.
</syntaxhighlight>
=={{header|Egel}}==
<syntaxhighlight lang="egel">
def ackermann =
[ 0 N -> N + 1
| M 0 -> ackermann (M - 1) 1
| M N -> ackermann (M - 1) (ackermann M (N - 1)) ]
</syntaxhighlight>
=={{header|Eiffel}}==
[https://github.com/ljr1981/rosettacode_answers/blob/main/src/ackerman_example/ackerman_example.e Example code]
[https://github.com/ljr1981/rosettacode_answers/blob/main/testing/rc_ackerman/rc_ackerman_test_set.e Test of Example code]
<syntaxhighlight lang="eiffel">
class
ACKERMAN_EXAMPLE
feature -- Basic Operations
ackerman (m, n: NATURAL): NATURAL
-- Recursively compute the n-th term of a series.
require
non_negative_m: m >= 0
non_negative_n: n >= 0
do
if m = 0 then
Result := n + 1
elseif m > 0 and n = 0 then
Result := ackerman (m - 1, 1)
elseif m > 0 and n > 0 then
Result := ackerman (m - 1, ackerman (m, n - 1))
else
check invalid_arg_state: False end
end
end
end
</syntaxhighlight>
=={{header|Ela}}==
<
ack m 0 = ack (m - 1) 1
ack m n = ack (m - 1) <| ack m <| n - 1</
=={{header|Elena}}==
ELENA
<
ackermann(m,n)
{
}
public program()
{
}</
{{out}}
<pre>
Line 3,176 ⟶ 3,279:
=={{header|Elixir}}==
<
def ack(0, n), do: n + 1
def ack(m, 0), do: ack(m - 1, 1)
Line 3,184 ⟶ 3,287:
Enum.each(0..3, fn m ->
IO.puts Enum.map_join(0..6, " ", fn n -> Ackermann.ack(m, n) end)
end)</
{{out}}
Line 3,195 ⟶ 3,298:
=={{header|Emacs Lisp}}==
<
(cond ((zerop m) (1+ n))
((zerop n) (ackermann (1- m) 1))
(t (ackermann (1- m)
(ackermann m (1- n))))))</
=={{header|EMal}}==
<syntaxhighlight lang="emal">
fun ackermann = int by int m, int n
return when(m == 0,
n + 1,
when(n == 0,
ackermann(m - 1, 1),
ackermann(m - 1, ackermann(m, n - 1))))
end
for int m = 0; m <= 3; ++m
for int n = 0; n <= 6; ++n
writeLine("Ackermann(" + m + ", " + n + ") = " + ackermann(m, n))
end
end
</syntaxhighlight>
{{out}}
<pre>
Ackermann(0, 0) = 1
Ackermann(0, 1) = 2
Ackermann(0, 2) = 3
Ackermann(0, 3) = 4
Ackermann(0, 4) = 5
Ackermann(0, 5) = 6
Ackermann(0, 6) = 7
Ackermann(1, 0) = 2
Ackermann(1, 1) = 3
Ackermann(1, 2) = 4
Ackermann(1, 3) = 5
Ackermann(1, 4) = 6
Ackermann(1, 5) = 7
Ackermann(1, 6) = 8
Ackermann(2, 0) = 3
Ackermann(2, 1) = 5
Ackermann(2, 2) = 7
Ackermann(2, 3) = 9
Ackermann(2, 4) = 11
Ackermann(2, 5) = 13
Ackermann(2, 6) = 15
Ackermann(3, 0) = 5
Ackermann(3, 1) = 13
Ackermann(3, 2) = 29
Ackermann(3, 3) = 61
Ackermann(3, 4) = 125
Ackermann(3, 5) = 253
Ackermann(3, 6) = 509
</pre>
=={{header|Erlang}}==
<
-module(ackermann).
-export([ackermann/2]).
Line 3,213 ⟶ 3,363:
ackermann(M, N) when M > 0 andalso N > 0 ->
ackermann(M-1, ackermann(M, N-1)).
</syntaxhighlight>
=={{header|ERRE}}==
Line 3,219 ⟶ 3,369:
substituted with the new ERRE control statements.
<
PROGRAM ACKERMAN
Line 3,274 ⟶ 3,424:
END FOR
END PROGRAM
</syntaxhighlight>
Prints a list of Ackermann function values: from A(0,0) to A(3,9). Uses a stack to avoid
Line 3,292 ⟶ 3,442:
=={{header|Euler Math Toolbox}}==
<syntaxhighlight lang="euler math toolbox">
>M=zeros(1000,1000);
>function map A(m,n) ...
Line 3,309 ⟶ 3,459:
3 5 7 9 11 13
5 13 29 61 125 253
</syntaxhighlight>
=={{header|Euphoria}}==
This is based on the [[VBScript]] example.
<
if m = 0 then
return n + 1
Line 3,328 ⟶ 3,478:
end for
puts( 1, "\n" )
end for</
=={{header|Ezhil}}==
<syntaxhighlight lang="ezhil">
நிரல்பாகம் அகெர்மன்(முதலெண், இரண்டாமெண்)
Line 3,370 ⟶ 3,520:
முடி
</syntaxhighlight>
=={{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
Line 3,381 ⟶ 3,531:
do
printfn "%A" (ackermann (int fsi.CommandLineArgs.[1]) (int fsi.CommandLineArgs.[2]))</
Transforming this into continuation passing style avoids limited stack space by permitting tail-recursion.
<
let rec acker (m, n, k) =
match m,n with
Line 3,389 ⟶ 3,539:
| m, 0 -> acker ((m - 1), 1, k)
| m, n -> acker (m, (n - 1), (fun x -> acker ((m - 1), x, k)))
acker (M, N, (fun x -> x))</
=={{header|Factor}}==
<
IN: ackermann
Line 3,400 ⟶ 3,550:
{ [ n 0 = ] [ m 1 - 1 ackermann ] }
[ m 1 - m n 1 - ackermann ackermann ]
} cond ;</
=={{header|Falcon}}==
<
if m == 0: return( n + 1 )
if n == 0: return( ackermann( m - 1, 1 ) )
Line 3,414 ⟶ 3,564:
end
>
end</
The above will output the below.
Formating options to make this pretty are available,
Line 3,426 ⟶ 3,576:
=={{header|FALSE}}==
<
\$$[%
1-\$@@a;! { i j -> A(i-1, A(i, j-1)) }
Line 3,437 ⟶ 3,587:
]?]a: { j i }
3 3 a;! . { 61 }</
=={{header|Fantom}}==
<
{
// assuming m,n are positive
Line 3,463 ⟶ 3,613:
}
}
}</
{{out}}
<pre>
Line 3,498 ⟶ 3,648:
=={{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()
Line 3,519 ⟶ 3,669:
END FUNCTION
DYNC AckermannC(m AS INTEGER, n AS INTEGER) AS INTEGER</
int Ackermann(int m, int n)
{
Line 3,530 ⟶ 3,680:
{
return Ackermann(m, n);
}</
END DYNC
DYNASM AckermannA(m AS INTEGER, n AS INTEGER) AS INTEGER</
ENTER 0, 0
INVOKE Ackermann, m, n
Line 3,569 ⟶ 3,719:
LEAVE
RET 8
</
{{out}}
Line 3,582 ⟶ 3,732:
=={{header|Fermat}}==
<
A(3,8)</
{{out}}
<pre>
Line 3,590 ⟶ 3,740:
=={{header|Forth}}==
<
over 0= IF nip 1+ EXIT THEN
swap 1- swap ( m-1 n -- )
dup 0= IF 1+ recurse EXIT THEN
1- over 1+ swap recurse recurse ;</
{{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
Line 3,612 ⟶ 3,762:
then
then then then then
;</
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
IMPLICIT NONE
Line 3,642 ⟶ 3,792:
END FUNCTION Ackermann
END PROGRAM EXAMPLE</
=={{header|Free Pascal}}==
Line 3,648 ⟶ 3,798:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
' to do A(4, 2) the stack size needs to be increased
Line 3,688 ⟶ 3,838:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre> 0 1 2 3 4 5 6 7 8 9 10 11
Line 3,697 ⟶ 3,847:
=={{header|FunL}}==
<
ackermann( 0, n ) = n + 1
ackermann( m, 0 ) = ackermann( m - 1, 1 )
Line 3,703 ⟶ 3,853:
for m <- 0..3, n <- 0..4
printf( 'Ackermann( %d, %d ) = %d\n', m, n, ackermann(m, n) )</
{{out}}
Line 3,732 ⟶ 3,882:
=={{header|Futhark}}==
<syntaxhighlight lang="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))
</syntaxhighlight>
=={{header|FutureBasic}}==
<
include "NSLog.incl"
local fn Ackerman( m as NSInteger, n as NSInteger ) as NSInteger
NSInteger result
select
case m == 0 : result = ( n + 1 )
case n == 0 : result = fn Ackerman( ( m - 1 ), 1 )
case else : result = fn Ackerman( ( m - 1 ), fn Ackerman( m, ( n - 1 ) ) )
end select
end fn = result
Line 3,767 ⟶ 3,917:
HandleEvents
</syntaxhighlight>
Output:
Line 3,815 ⟶ 3,965:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Ackermann_function}}
'''Solution'''
[[File:Fōrmulæ - Ackermann function 01.png]]
'''Test case'''
[[File:Fōrmulæ - Ackermann function 02.png]]
[[File:Fōrmulæ - Ackermann function 03.png]]
=={{header|Gambas}}==
<
If m = 0 Then
Return n + 1
Line 3,839 ⟶ 3,995:
Next
Next
End</
=={{header|GAP}}==
<
if m = 0 then
return n + 1;
Line 3,852 ⟶ 4,008:
return fail;
fi;
end;</
=={{header|Genyris}}==
<
cond
(equal? m 0)
Line 3,863 ⟶ 4,019:
else
A (- m 1)
A m (- n 1)</
=={{header|GML}}==
Define a script resource named ackermann and paste this code inside:
<
var m, n;
m = argument0;
Line 3,882 ⟶ 4,038:
{
return (ackermann(m-1,ackermann(m,n-1,2),1))
}</
=={{header|gnuplot}}==
<
print A (0, 4)
print A (1, 4)
print A (2, 4)
print A (3, 4)</
{{out}}
5
Line 3,898 ⟶ 4,054:
=={{header|Go}}==
===Classic version===
<
switch 0 {
case m:
Line 3,906 ⟶ 4,062:
}
return Ackermann(m - 1, Ackermann(m, n - 1))
}</
===Expanded version===
<
switch {
case m == 0:
Line 3,922 ⟶ 4,078:
}
return Ackermann2(m - 1, Ackermann2(m, n - 1))
}</
===Expanded version with arbitrary precision===
<
import (
Line 4,013 ⟶ 4,169:
)
}
}</
{{out}}
<pre>
Line 4,027 ⟶ 4,183:
=={{header|Golfscript}}==
<
:_n; :_m;
_m 0= {_n 1+}
Line 4,034 ⟶ 4,190:
if}
if
}:ack;</
=={{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:
<
ackMatrix.each { it.each { elt -> printf "%7d", elt }; println() }</
{{out}}
<pre> 1 2 3 4 5 6 7 8 9
Line 4,052 ⟶ 4,208:
=={{header|Hare}}==
<
fn ackermann(m: u64, n: u64) u64 = {
Line 4,071 ⟶ 4,227:
fmt::println()!;
};
};</
=={{header|Haskell}}==
<
ack 0 n = succ n
ack m 0 = ack (pred m) 1
Line 4,080 ⟶ 4,236:
main :: IO ()
main = mapM_ print $ uncurry ack <$> [(0, 0), (3, 4)]</
{{out}}
<pre>1
Line 4,086 ⟶ 4,242:
Generating a list instead:
<
-- everything here are [Int] or [[Int]], which would overflow
Line 4,095 ⟶ 4,251:
f a b = (aa, head aa) where aa = drop b a
main = mapM_ print $ map (\n -> take (6 - n) $ ackermann !! n) [0..5]</
=={{header|Haxe}}==
<
{
static public function main()
Line 4,117 ⟶ 4,273:
return ackermann(m-1, ackermann(m, n-1));
}
}</
=={{header|Hoon}}==
<syntaxhighlight lang="hoon">
|= [m=@ud n=@ud]
?: =(m 0)
Line 4,127 ⟶ 4,283:
$(n 1, m (dec m))
$(m (dec m), n $(n (dec n)))
</syntaxhighlight>
=={{header|Icon}} and {{header|Unicon}}==
Line 4,133 ⟶ 4,289:
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
Line 4,157 ⟶ 4,313:
write()
}
end</
{{out}}
<pre>
Line 4,166 ⟶ 4,322:
=={{header|Idris}}==
<
A Z n = S n
A (S m) Z = A m (S Z)
A (S m) (S n) = A m (A (S m) n)</
=={{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
c3=: <:@[ ack [ ack <:@] NB. else, (x-1) ack x ack y-1</
{{out|Example use}}
<
4
1 ack 3
Line 4,194 ⟶ 4,350:
9
3 ack 3
61</
J's stack was too small for me to compute <tt>4 ack 1</tt>.
===Alternative Primitive Recursive Version===
Line 4,200 ⟶ 4,356:
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
Line 4,217 ⟶ 4,373:
5 Ack 0
65533
</syntaxhighlight>
A structured derivation of Ack follows:
<
x=. o[ NB. Composing the left noun (argument)
Line 4,247 ⟶ 4,403:
(Ack=. (3 -~ [ Buck 3 + ])f.) NB. Ackermann function-level code
3 -~ [ ({&(2 4$'>: 2x&+') ::(,&'&1'&'2x&*'@:(-&2))"0@:[ 128!:2 ]) 3 + ]</
=={{header|Java}}==
[[Category:Arbitrary precision]]
<
public static BigInteger ack(BigInteger m, BigInteger n) {
Line 4,258 ⟶ 4,414:
: 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);
Line 4,269 ⟶ 4,425:
return (VALUE) untypedField(field);
}
}</
<
import java.util.function.Function;
import java.util.function.Predicate;
Line 4,315 ⟶ 4,471:
}
}
}</
<
import java.util.Stack;
import java.util.function.BinaryOperator;
Line 4,460 ⟶ 4,616:
}
}
}</
{{Iterative version}}
<
* Source https://stackoverflow.com/a/51092690/5520417
*/
Line 4,852 ⟶ 5,008:
}
</syntaxhighlight>
=={{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 (;;) {
Line 4,886 ⟶ 5,042:
}
}
}</
===Stackless Iterative===
<
function ack(M, N){
const next = new Float64Array(M + 1);
Line 4,913 ⟶ 5,069:
}
var args = process.argv;
console.log(ack(parseInt(args[2]), parseInt(args[3])));</
{{out}}
Line 4,923 ⟶ 5,079:
===ES6===
<
'use strict';
Line 4,960 ⟶ 5,116:
// MAIN ---
return main();
})();</
{{Out}}
<pre>[4,5,9,61]</pre>
=={{header|Joy}}==
<syntaxhighlight lang="joy">DEFINE ack == [[[pop null] popd succ]
[[dup pred
cond.</syntaxhighlight>
another using a combinator:
<syntaxhighlight lang="joy">DEFINE ack == [[[pop null] [popd succ]]
condnestrec.</syntaxhighlight>
=={{header|jq}}==
{{ works with|jq|1.4}}
'''Also works with gojq, the Go implementation of jq.'''
Except for a minor tweak to the line using string interpolation, the following have also been tested using jaq, the Rust implementation of jq, as of April 13, 2023.
For infinite-precision integer arithmetic, use gojq or fq.
===Without Memoization===
<
def ack:
.[0] as $m | .[1] as $n
Line 4,986 ⟶ 5,145:
elif $n == 0 then [$m-1, 1] | ack
else [$m-1, ([$m, $n-1 ] | ack)] | ack
end ;</
'''Example:'''
<
| range(0; if $i > 3 then 1 else 6 end) as $j
| "A(\($i),\($j)) = \( [$i,$j] | ack )"</
{{out}}
<
A(0,0) = 1
A(0,1) = 2
Line 5,017 ⟶ 5,176:
A(3,4) = 125
A(3,5) = 253
A(4,0) = 13</
===With Memoization and Optimization===
<
# output [value, updatedCache]
def ack:
Line 5,048 ⟶ 5,207:
def A(m;n): [m,n,{}] | ack | .[0];
</syntaxhighlight>
'''Examples:'''
<syntaxhighlight lang="jq">A(4;1)</syntaxhighlight>
{{out}}
<syntaxhighlight lang
Using gojq:
<syntaxhighlight lang="jq">A(4;2), A(3;1000000) | tostring | length</syntaxhighlight>
{{out}}
<syntaxhighlight lang="sh">
19729
301031
</syntaxhighlight>
=={{header|Jsish}}==
From javascript entry.
<
function ack(m, n) {
Line 5,080 ⟶ 5,248:
ack(3,5) ==> 253
=!EXPECTEND!=
*/</
{{out}}
Line 5,092 ⟶ 5,260:
=={{header|Julia}}==
<
if m == 0
return n + 1
Line 5,100 ⟶ 5,268:
return ack(m-1,ack(m,n-1))
end
end</
'''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))</
'''Benchmarking''':
Line 5,119 ⟶ 5,287:
=={{header|K}}==
{{works with|Kona}}
<
ack[2;2]
7
ack[2;7]
17</syntaxhighlight>
=={{header|Kdf9 Usercode}}==
<
YS26000;
RESTART; J999; J999;
Line 5,173 ⟶ 5,344:
J99; (tail recursion for A[m-1, A[m, n-1]]);
FINISH;</
=={{header|Klingphix}}==
<syntaxhighlight lang="text">:ack
%n !n %m !m
Line 5,192 ⟶ 5,363:
msec print
" " input</
=={{header|Klong}}==
<syntaxhighlight lang="k">
ack::{:[0=x;y+1:|0=y;.f(x-1;1);.f(x-1;.f(x;y-1))]}
ack(2;2)</
=={{header|Kotlin}}==
<
tailrec fun A(m: Long, n: Long): Long {
require(m >= 0L) { "m must not be negative" }
Line 5,226 ⟶ 5,397:
.forEach(::println)
}
</syntaxhighlight>
{{out}}
<pre>
Line 5,237 ⟶ 5,408:
=={{header|Lambdatalk}}==
<syntaxhighlight lang="scheme">
{def ack
{lambda {:m :n}
Line 5,260 ⟶ 5,431:
{ack 4 1} // too much
-> ???
</syntaxhighlight>
=={{header|Lasso}}==
<
define ackermann(m::integer, n::integer) => {
Line 5,278 ⟶ 5,449:
y in generateSeries(0,8,2)
do stdoutnl(#x+', '#y+': ' + ackermann(#x, #y))
</syntaxhighlight>
{{out}}
<pre>1, 0: 2
Line 5,297 ⟶ 5,468:
=={{header|LFE}}==
<
((0 n) (+ n 1))
((m 0) (ackermann (- m 1) 1))
((m n) (ackermann (- m 1) (ackermann m (- n 1)))))</
=={{header|Liberty BASIC}}==
<
Function Ackermann(m, n)
Line 5,316 ⟶ 5,487:
Ackermann = Ackermann((m - 1), Ackermann(m, (n - 1)))
End Select
End Function</
=={{header|LiveCode}}==
<
switch
Case m = 0
Line 5,328 ⟶ 5,499:
return ackermann((m - 1), ackermann(m, (n - 1)))
end switch
end ackermann</
=={{header|Logo}}==
<
if :i = 0 [output :j+1]
if :j = 0 [output ack :i-1 1]
output ack :i-1 ack :i :j-1
end</
=={{header|Logtalk}}==
<
!,
V is N + 1.
Line 5,349 ⟶ 5,520:
N2 is N - 1,
ack(M, N2, V2),
ack(M2, V2, V).</
=={{header|LOLCODE}}==
{{trans|C}}
<
HOW IZ I ackermann YR m AN YR n
Line 5,374 ⟶ 5,545:
IM OUTTA YR outer
KTHXBYE</
=={{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))
end</
=== Stackless iterative solution with multiple precision, fast ===
<
#!/usr/bin/env luajit
local gmp = require 'gmp' ('libgmp')
Line 5,423 ⟶ 5,594:
printf("%Zd\n", ack(tonumber(arg[1]), arg[2] and tonumber(arg[2]) or 0))
end
</syntaxhighlight>
{{out}}
Line 5,439 ⟶ 5,610:
=={{header|Lucid}}==
<
where
ack(m,n) = if m eq 0 then n+1
Line 5,445 ⟶ 5,616:
else ack(m-1, ack(m, n-1)) fi
fi;
end</
=={{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}}==
<syntaxhighlight lang="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,470 ⟶ 5,641:
}
Checkit
</syntaxhighlight>
=={{header|M4}}==
<
ack(3,3)</
{{out}}
<pre>61 </pre>
=={{header|MACRO-11}}==
<syntaxhighlight lang="macro11"> .TITLE ACKRMN
.MCALL .TTYOUT,.EXIT
ACKRMN::JMP MKTBL
; R0 = ACK(R0,R1)
ACK: MOV SP,R2 ; KEEP OLD STACK PTR
MOV #ASTK,SP ; USE PRIVATE STACK
JSR PC,1$
MOV R2,SP ; RESTORE STACK PTR
RTS PC
1$: TST R0
BNE 2$
INC R1
MOV R1,R0
RTS PC
2$: TST R1
BNE 3$
DEC R0
INC R1
BR 1$
3$: MOV R0,-(SP)
DEC R1
JSR PC,1$
MOV R0,R1
MOV (SP)+,R0
DEC R0
BR 1$
.BLKB 4000 ; BIG STACK
ASTK = .
; PRINT TABLE
MMAX = 4
NMAX = 7
MKTBL: CLR R3
1$: CLR R4
2$: MOV R3,R0
MOV R4,R1
JSR PC,ACK
JSR PC,PR0
INC R4
CMP R4,#NMAX
BLT 2$
MOV #15,R0
.TTYOUT
MOV #12,R0
.TTYOUT
INC R3
CMP R3,#MMAX
BLT 1$
.EXIT
; PRINT NUMBER IN R0 AS DECIMAL
PR0: MOV #4$,R1
1$: MOV #-1,R2
2$: INC R2
SUB #12,R0
BCC 2$
ADD #72,R0
MOVB R0,-(R1)
MOV R2,R0
BNE 1$
3$: MOVB (R1)+,R0
.TTYOUT
BNE 3$
RTS PC
.ASCII /...../
4$: .BYTE 11,0
.END ACKRMN</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5 6 7
2 3 4 5 6 7 8
3 5 7 9 11 13 15
5 13 29 61 125 253 509</pre>
=={{header|MAD}}==
Line 5,491 ⟶ 5,737:
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
Line 5,529 ⟶ 5,775:
VECTOR VALUES ACKF = $4HACK(,I1,1H,,I1,4H) = ,I4*$
END OF PROGRAM
</syntaxhighlight>
{{out}}
Line 5,569 ⟶ 5,815:
ACK(3,7) = 1021
ACK(3,8) = 2045</pre>
=={{header|Maple}}==
Strictly by the definition given above, we can code this as follows.
<syntaxhighlight lang="maple">
Ackermann := proc( m :: nonnegint, n :: nonnegint )
option remember; # optional automatic memoization
Line 5,586 ⟶ 5,829:
end if
end proc:
</syntaxhighlight>
In Maple, the keyword <syntaxhighlight lang
To make this faster, you can use known expansions for small values of <math>m</math>. (See [[wp:Ackermann_function|Wikipedia:Ackermann function]])
<syntaxhighlight lang="maple">
Ackermann := proc( m :: nonnegint, n :: nonnegint )
option remember; # optional automatic memoization
Line 5,607 ⟶ 5,850:
end if
end proc:
</syntaxhighlight>
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
<syntaxhighlight lang="maple">
> 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
<syntaxhighlight lang="maple">
> 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
<syntaxhighlight lang="maple">
> length( Ackermann( 4, 2 ) );
19729
</syntaxhighlight>
digits.
Line 5,632 ⟶ 5,875:
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<sub>a</sub>.
Line 5,647 ⟶ 5,890:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
Two possible implementations would be:
<
Ackermann1[m_,n_]:=
If[m==0,n+1,
Line 5,657 ⟶ 5,900:
Ackermann2[0,n_]:=n+1;
Ackermann2[m_,0]:=Ackermann1[m-1,1];
Ackermann2[m_,n_]:=Ackermann1[m-1,Ackermann1[m,n-1]]</
Note that the second implementation is quite a bit faster, as doing 'if' comparisons is slower than the built-in pattern matching algorithms.
Examples:
<
gives back:
<
Ackermann2[1,2] = 4
Ackermann2[1,3] = 5
Line 5,685 ⟶ 5,928:
Ackermann2[3,6] = 509
Ackermann2[3,7] = 1021
Ackermann2[3,8] = 2045</
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;
Line 5,694 ⟶ 5,937:
Ackermann3[3,n_]:=5+8 (2^n-1);
Ackermann3[m_,0]:=Ackermann3[m-1,1];
Ackermann3[m_,n_]:=Ackermann3[m-1,Ackermann3[m,n-1]]</
Now computing Ackermann[4,1] and Ackermann[4,2] can be done quickly (<0.01 sec):
Examples 2:
<
Ackermann3[4, 2]</
gives back:
<div style="width:full;overflow:scroll"><
2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880........699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156733</
Ackermann[4,2] has 19729 digits, several thousands of digits omitted in the result above for obvious reasons. Ackermann[5,0] can be computed also quite fast, and is equal to 65533.
Summarizing Ackermann[0,n_], Ackermann[1,n_], Ackermann[2,n_], and Ackermann[3,n_] can all be calculated for n>>1000. Ackermann[4,0], Ackermann[4,1], Ackermann[4,2] and Ackermann[5,0] are only possible now. Maybe in the future we can calculate higher Ackermann numbers efficiently and fast. Although showing the results will always be a problem.
=={{header|MATLAB}}==
<
if m == 0
A = n+1;
Line 5,714 ⟶ 5,957:
A = ackermannFunction( m-1,ackermannFunction(m,n-1) );
end
end</
=={{header|Maxima}}==
<
ackermann[m, n] := if m = 0 then n + 1
Line 5,731 ⟶ 5,974:
ackermann(4, n) - (tetration(2, n + 3) - 3);
subst(n = 2, %);
ev(%, nouns);</
=={{header|MAXScript}}==
Use with caution. Will cause a stack overflow for m > 3.
<
(
if m == 0 then
Line 5,749 ⟶ 5,992:
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).
Line 5,762 ⟶ 6,005:
; M = integer(0) -> R = N + integer(1)
; N = integer(0) -> ack(M - integer(1), integer(1), R)
; ack(M - integer(1), ack(M, N - integer(1)), R) ).</
=={{header|min}}==
{{works with|min|0.19.3}}
<
:n :m
(
Line 5,773 ⟶ 6,016:
((true) (m 1 - m n 1 - ackermann ackermann))
) case
) :ackermann</
=={{header|MiniScript}}==
<
if m == 0 then return n+1
if n == 0 then return ackermann(m - 1, 1)
Line 5,787 ⟶ 6,030:
print "(" + m + ", " + n + "): " + ackermann(m, n)
end for
end for</
=={{header|МК-61/52}}==
<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
ПП 06 П1 ИП2 1 - П0 ПП 06 В/О</
=={{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
Line 5,830 ⟶ 6,073:
a(3,1) => ACK(3,1)
a(3,2) => ACK(3,2)
a(4,0) => ACK(4,0)</
{{out}}
<
a(0,1) => 2
a(0,2) => 3
Line 5,850 ⟶ 6,093:
a(3,1) => 13
a(3,2) => 29
a(4,0) => 13</
=={{header|mLite}}==
<
| ( m, 0 ) = ackermann( m - 1, 1 )
| ( m, n ) = ackermann( m - 1, ackermann(m, n - 1) )</
Test code providing tuples from (0,0) to (3,8)
<
fun test_tuples (x, y) = append_map (fn a = map (fn b = (b, a)) ` jota x) ` jota y
map ackermann (test_tuples(4,9))</
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;
Line 5,898 ⟶ 6,141:
END;
InOut.WriteLn
END ackerman.</
{{out}}<pre>jan@Beryllium:~/modula/rosetta$ ackerman
1 2 3 4 5 6 7
Line 5,907 ⟶ 6,150:
=={{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;
Line 5,930 ⟶ 6,173:
Put("\n");
END;
END Ack.</
{{out}}
<pre>1 2 3 4 5 6 7
Line 5,938 ⟶ 6,181:
=={{header|MUMPS}}==
<
If m=0 Quit n+1
If m>0,n=0 Quit $$Ackermann(m-1,1)
Line 5,946 ⟶ 6,189:
Write $$Ackermann(1,8) ; 10
Write $$Ackermann(2,8) ; 19
Write $$Ackermann(3,5) ; 253</
=={{header|Neko}}==
<syntaxhighlight lang="actionscript">/**
Ackermann recursion, in Neko
Tectonics:
Line 5,971 ⟶ 6,214:
$print("Ackermann(", arg1, ",", arg2, "): ", ack(arg1,arg2), "\n")
catch problem
$print("Ackermann(", arg1, ",", arg2, "): ", problem, "\n")</
{{out}}
Line 5,994 ⟶ 6,237:
=={{header|Nemerle}}==
In Nemerle, we can state the Ackermann function as a lambda. By using pattern-matching, our definition strongly resembles the mathematical notation.
<syntaxhighlight lang="nemerle">
using System;
using Nemerle.IO;
Line 6,015 ⟶ 6,258:
}
}
</syntaxhighlight>
A terser version using implicit <code>match</code> (which doesn't use the alias <code>A</code> internally):
<syntaxhighlight lang="nemerle">
def ackermann(m, n) {
| (0, n) => n + 1
Line 6,024 ⟶ 6,267:
| _ => throw Exception("invalid inputs");
}
</syntaxhighlight>
Or, if we were set on using the <code>A</code> notation, we could do this:
<syntaxhighlight lang="nemerle">
def ackermann = {
def A(m, n) {
Line 6,036 ⟶ 6,279:
A
}
</syntaxhighlight>
=={{header|NetRexx}}==
<
options replace format comments java crossref symbols binary
Line 6,063 ⟶ 6,306:
end
return rval
</syntaxhighlight>
=={{header|NewLISP}}==
<
#! /usr/local/bin/newlisp
Line 6,073 ⟶ 6,316:
((zero? n) (ackermann (dec m) 1))
(true (ackermann (- m 1) (ackermann m (dec n))))))
</syntaxhighlight>
<pre>
Line 6,082 ⟶ 6,325:
=={{header|Nim}}==
<
proc ackermann(m, n: int64): int64 =
Line 6,107 ⟶ 6,350:
let second = getNumber()
echo "Result: ", $ackermann(first, second)
</syntaxhighlight>
=={{header|Nit}}==
Line 6,113 ⟶ 6,356:
Source: [https://github.com/nitlang/nit/blob/master/examples/rosettacode/ackermann_function.nit the official Nit’s repository].
<
#
# A simple straightforward recursive implementation.
Line 6,130 ⟶ 6,373:
end
print ""
end</
Output:
Line 6,169 ⟶ 6,412:
=={{header|Oberon-2}}==
<
IMPORT Out;
Line 6,194 ⟶ 6,437:
END;
Out.Ln
END ackerman.</
=={{header|Objeck}}==
{{trans|C#|C sharp}}
<
function : Main(args : String[]) ~ Nil {
for(m := 0; m <= 3; ++m;) {
Line 6,227 ⟶ 6,470:
return -1;
}
}</
<pre>
Ackermann(0, 0) = 1
Line 6,252 ⟶ 6,495:
=={{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)))</
or:
<
| 0, n -> (n+1)
| m, 0 -> a(m-1, 1)
| m, n -> a(m-1, a(m, n-1))</
with memoization using an hash-table:
<
let a m n =
Line 6,269 ⟶ 6,512:
let res = a (m, n) in
Hashtbl.add h (m, n) res;
(res)</
taking advantage of the memoization we start calling small values of '''m''' and '''n''' in order to reduce the recursion call stack:
<
for _m = 0 to m do
for _n = 0 to n do
Line 6,277 ⟶ 6,520:
done;
done;
(a m n)</
=== 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
Line 6,290 ⟶ 6,533:
if eq m zero then (succ n) else
if eq n zero then (a (pred m) one) else
(a (pred m) (a m (pred n)))</
compile with:
ocamlopt -o acker nums.cmxa acker.ml
=== Tail-Recursive ===
Here is a [[:Category:Recursion|tail-recursive]] version:
<
try Some(Hashtbl.find h v)
with Not_found -> None
Line 6,324 ⟶ 6,567:
a bounds caller todo m (n-1)
let a = a (Hashtbl.create 42 (* arbitrary *) ) [] [] ;;</
This one uses the arbitrary precision, the tail-recursion, and the optimisation explain on the Wikipedia page about <tt>(m,n) = (3,_)</tt>.
<
let one = unit_big_int
let zero = zero_big_int
Line 6,404 ⟶ 6,647:
(string_of_big_int n)
(string_of_big_int r);
;;</
=={{header|Octave}}==
<
if ( m == 0 )
r = n + 1;
Line 6,419 ⟶ 6,662:
for i = 0:3
disp(ackerman(i, 4));
endfor</
=={{header|Oforth}}==
<
m ifZero: [ n 1+ return ]
m 1- n ifZero: [ 1 ] else: [ A( m, n 1- ) ] A
;</
=={{header|Ol}}==
<syntaxhighlight lang="scheme">
; simple version
(define (A m n)
(cond
((= m 0) (+ n 1))
((= n 0) (A (- m 1) 1))
(else (A (- m 1) (A m (- n 1))))))
(print "simple version (A 3 6): " (A 3 6))
; smart (lazy) version
(define (ints-from n)
(cons* n (delay (ints-from (+ n 1)))))
(define (knuth-up-arrow a n b)
(let loop ((n n) (b b))
(cond ((= b 0) 1)
((= n 1) (expt a b))
(else (loop (- n 1) (loop n (- b 1)))))))
(define (A+ m n)
(define (A-stream)
(cons*
(ints-from 1) ;; m = 0
(ints-from 2) ;; m = 1
;; m = 2
(lmap (lambda (n)
(+ (* 2 (+ n 1)) 1))
(ints-from 0))
;; m = 3
(lmap (lambda (n)
(- (knuth-up-arrow 2 (- m 2) (+ n 3)) 3))
(ints-from 0))
;; m = 4...
(delay (ldrop (A-stream) 3))))
(llref (llref (A-stream) m) n))
(print "extended version (A 3 6): " (A+ 3 6))
</syntaxhighlight>
{{Out}}
<pre>
simple version (A 3 6): 509
extended version (A 3 6): 509
</pre>
=={{header|OOC}}==
<
ack: func (m: Int, n: Int) -> Int {
if (m == 0) {
Line 6,446 ⟶ 6,735:
}
}
</syntaxhighlight>
=={{header|ooRexx}}==
<syntaxhighlight lang="oorexx">
loop m = 0 to 3
loop n = 0 to 6
Line 6,463 ⟶ 6,752:
else if n = 0 then return ackermann(m - 1, 1)
else return ackermann(m - 1, ackermann(m, n - 1))
</syntaxhighlight>
{{out}}
<pre>
Line 6,497 ⟶ 6,786:
=={{header|Order}}==
<
#define ORDER_PP_DEF_8ack ORDER_PP_FN( \
Line 6,505 ⟶ 6,794:
(8else, 8ack(8dec(8X), 8ack(8X, 8dec(8Y)))))))
ORDER_PP(8to_lit(8ack(3, 4))) // 125</
=={{header|Oz}}==
Oz has arbitrary precision integers.
<
fun {Ack M N}
Line 6,520 ⟶ 6,809:
in
{Show {Ack 3 7}}</
=={{header|PARI/GP}}==
Naive implementation.
<
if(m,
if(n,
Line 6,534 ⟶ 6,823:
n+1
)
};</
=={{header|Pascal}}==
<
function ackermann(m, n: Integer) : Integer;
Line 6,556 ⟶ 6,845:
for m := 0 to 3 do
WriteLn('A(', m, ',', n, ') = ', ackermann(m,n));
end.</
=={{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 {
Line 6,572 ⟶ 6,861:
);
}
}</
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";
Line 6,605 ⟶ 6,894:
print "ack2(3,4) is ", ack2(3,4), "\n";
print "ack2(4,1) is ", ack2(4,1), "\n";
print "ack2(4,2) has ", length(ack2(4,2)), " digits\n";</
{{output}}
<pre>ack2(3,4) is 125
Line 6,613 ⟶ 6,902:
An optimized version, which uses <code>@_</code> as a stack,
instead of recursion. Very fast.
<
use warnings;
use Math::BigInt;
Line 6,648 ⟶ 6,937:
print "ack(4,2) has ", length(ack(4,2)), " digits\n";
</syntaxhighlight>
=={{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>
Line 6,687 ⟶ 6,976:
<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>
Line 6,703 ⟶ 6,992:
{{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>
Line 6,786 ⟶ 7,075:
<span style="color: #000000;">ackermann_tests</span><span style="color: #0000FF;">()</span>
<!--</
{{out}}
<pre>
Line 6,806 ⟶ 7,095:
=={{header|Phixmonti}}==
<
var n var m
Line 6,820 ⟶ 7,109:
enddef
3 6 ack print nl</
=={{header|PHP}}==
<
{
if ( $m==0 )
Line 6,837 ⟶ 7,126:
echo ackermann( 3, 4 );
// prints 125</
=={{header|Picat}}==
<
foreach(M in 0..3)
println([m=M,[a(M,N) : N in 0..16]])
Line 6,878 ⟶ 7,167:
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))).
</syntaxhighlight>
{{out}}
Line 6,899 ⟶ 7,188:
=={{header|PicoLisp}}==
<
(cond
((=0 X) (inc Y))
((=0 Y) (ack (dec X) 1))
(T (ack (dec X) (ack X (dec Y)))) ) )</
=={{header|Piet}}==
Line 7,272 ⟶ 7,561:
=={{header|Pike}}==
<
write(ackermann(3,4) + "\n");
}
Line 7,284 ⟶ 7,573:
return ackermann(m-1, ackermann(m, n-1));
}
}</
=={{header|PL/I}}==
<
declare (m, n) fixed (30);
if m = 0 then return (n+1);
Line 7,293 ⟶ 7,582:
else if m > 0 & n > 0 then return (Ackerman(m-1, Ackerman(m, n-1)));
return (0);
end Ackerman;</
=={{header|PL/SQL}}==
<
FUNCTION ackermann(pi_m IN NUMBER,
Line 7,317 ⟶ 7,606:
END LOOP;
END;
</syntaxhighlight>
{{out}}
<pre>
Line 7,351 ⟶ 7,640:
=={{header|PostScript}}==
<
/n exch def
/m exch def %PostScript takes arguments in the reverse order as specified in the function definition
Line 7,364 ⟶ 7,653:
m 1 sub m n 1 sub ackermann ackermann
}if
}def</
{{libheader|initlib}}
<
[/.m /.n] let
{
Line 7,373 ⟶ 7,662:
{.m 0 gt .n 0 gt and} {.m pred .m .n pred A A} is?
} cond
end}.</
=={{header|Potion}}==
<
if (m == 0): n + 1
. elsif (n == 0): ack(m - 1, 1)
Line 7,386 ⟶ 7,675:
ack(m, n) print
" " print.
"\n" print.</
=={{header|PowerBASIC}}==
<
DIM m AS QUAD, n AS QUAD
Line 7,406 ⟶ 7,695:
FUNCTION = Ackermann(m - 1, Ackermann(m, n - 1))
END IF
END FUNCTION</
=={{header|PowerShell}}==
{{trans|PHP}}
<
if ($m -eq 0) {
return $n + 1
Line 7,420 ⟶ 7,709:
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
Line 7,435 ⟶ 7,724:
===A More "PowerShelly" Way===
<syntaxhighlight lang="powershell">
function Get-Ackermann ([int64]$m, [int64]$n)
{
Line 7,450 ⟶ 7,739:
return (Get-Ackermann ($m - 1) (Get-Ackermann $m ($n - 1)))
}
</syntaxhighlight>
Save the result to an array (for possible future use?), then display it using the <code>Format-Wide</code> cmdlet:
<syntaxhighlight lang="powershell">
$ackermann = 0..3 | ForEach-Object {$m = $_; 0..6 | ForEach-Object {Get-Ackermann $m $_}}
$ackermann | Format-Wide {"{0,3}" -f $_} -Column 7 -Force
</syntaxhighlight>
{{Out}}
<pre>
Line 7,466 ⟶ 7,755:
=={{header|Processing}}==
<
if (m == 0)
return n + 1;
Line 7,484 ⟶ 7,773:
println();
}
}</
{{Out}}
Line 7,498 ⟶ 7,787:
m = 5 it throws 'maximum recursion depth exceeded'
<
def setup():
Line 7,513 ⟶ 7,802:
return ackermann(m - 1, 1)
else:
return ackermann(m - 1, ackermann(m, n - 1))</
==={{header|Processing.R}}===
Line 7,519 ⟶ 7,808:
Processing.R may exceed its stack depth at ~n==6 and returns null.
<
for (m in 0:3) {
for (n in 0:4) {
Line 7,536 ⟶ 7,825:
ackermann(m-1, ackermann(m, n-1))
}
}</
{{out}}
Line 7,546 ⟶ 7,835:
=={{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).</
"Pure" Prolog Version (Uses Peano arithmetic instead of is/2):
<syntaxhighlight lang="prolog">ack(0,N,s(N)).
ack(s(M),0,P):- ack(M,s(0),P).
ack(s(M),s(N),P):- ack(s(M),N,S), ack(M,S,P).
% Peano's first axiom in Prolog is that s(0) AND s(s(N)):- s(N)
% Thanks to this we don't need explicit N > 0 checks.
% Nor explicit arithmetic operations like X is M-1.
% Recursion and unification naturally decrement s(N) to N.
% But: Prolog clauses are relations and cannot be replaced by their result, like functions.
% Because of this we do need an extra argument to hold the output of the function.
% And we also need an additional call to the function in the last clause.
% Example input/output:
% ?- ack(s(0),s(s(0)),P).
% P = s(s(s(s(0)))) ;
% false.
</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;</
=={{header|Pure Data}}==
<syntaxhighlight lang="pure data">
#N canvas 741 265 450 436 10;
#X obj 83 111 t b l;
Line 7,603 ⟶ 7,911:
#X connect 15 0 10 0;
#X connect 16 0 10 0;
#X connect 17 0 0 0;</
=={{header|PureBasic}}==
<
If m = 0
ProcedureReturn n + 1
Line 7,616 ⟶ 7,924:
EndProcedure
Debug Ackermann(3,4)</
=={{header|Purity}}==
<
data Ackermann = FoldNat <const Succ, Iter></
=={{header|Python}}==
===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)))</
Another version:
<
@lru_cache(None)
Line 7,638 ⟶ 7,946:
return ack2(M - 1, 1)
else:
return ack2(M - 1, ack2(M, N - 1))</
{{out|Example of use}}
<
>>> sys.setrecursionlimit(3000)
>>> ack1(0,0)
Line 7,649 ⟶ 7,957:
1
>>> ack2(3,4)
125</
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 (
ack2(M-1, 1) if N == 0 else ack2(M-1, ack2(M, N-1))))))</
Results confirm those of Mathematica for ack(4,1) and ack(4,2)
Line 7,662 ⟶ 7,970:
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):
Line 7,686 ⟶ 7,994:
stack.extend([m-1, m, n-1])
return stack[0]</
{{out}}
Line 7,711 ⟶ 8,019:
=={{header|Quackery}}==
<
[ over 0 = iff
[ nip 1 + ] done
Line 7,720 ⟶ 8,028:
ackermann ackermann ] resolves ackermann ( m n --> r )
3 10 ackermann echo</
'''Output:'''
<pre>8189</pre>
=={{header|R}}==
<
if ( m == 0 ) {
n+1
Line 7,733 ⟶ 8,041:
ackermann(m-1, ackermann(m, n-1))
}
}</
<
print(ackermann(i, 4))
}</
=={{header|Racket}}==
<
#lang racket
(define (ackermann m n)
Line 7,745 ⟶ 8,053:
[(zero? n) (ackermann (sub1 m) 1)]
[else (ackermann (sub1 m) (ackermann m (sub1 n)))]))
</syntaxhighlight>
=={{header|Raku}}==
Line 7,751 ⟶ 8,059:
{{works with|Rakudo|2018.03}}
<syntaxhighlight lang="raku"
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:
<syntaxhighlight lang="raku"
multi sub A(Int $m, 0 ) { A($m - 1, 1) }
multi sub A(Int $m, Int $n) { A($m - 1, A($m, $n - 1)) }</
Note that in either case, Int is defined to be arbitrary precision in Raku.
Here's a caching version of that, written in the sigilless style, with liberal use of Unicode, and the extra optimizing terms to make A(4,2) possible:
<syntaxhighlight lang="raku"
multi A(0, Int \𝑛) { 𝑛 + 1 }
Line 7,775 ⟶ 8,083:
# Testing:
say A(4,1);
say .chars, " digits starting with ", .substr(0,50), "..." given A(4,2);</
{{out}}
<pre>65533
Line 7,788 ⟶ 8,096:
]
]</pre>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Prout 'A(3,9) = ' <A 3 9>>;
};
A {
0 s.N = <+ s.N 1>;
s.M 0 = <A <- s.M 1> 1>;
s.M s.N = <A <- s.M 1> <A s.M <- s.N 1>>>;
};</syntaxhighlight>
{{out}}
<pre>A(3,9) = 4093</pre>
=={{header|ReScript}}==
<
let _n = Sys.argv[3]
Line 7,804 ⟶ 8,125:
Js.log("ackermann(" ++ _m ++ ", " ++ _n ++ ") = "
++ string_of_int(a(m, n)))</
{{out}}
Line 7,817 ⟶ 8,138:
=={{header|REXX}}==
===no optimization===
<
/*╔════════════════════════════════════════════════════════════════════════╗
║ Note: the Ackermann function (as implemented here) utilizes deep ║
Line 7,841 ⟶ 8,162:
if m==0 then return n+1
if n==0 then return ackermann(m-1, 1)
return ackermann(m-1, ackermann(m, n-1) )</
{{out|output|text= when using the internal default input:}}
<pre style="height:60ex">
Line 7,922 ⟶ 8,243:
===optimized for m ≤ 2===
<
high=24
do j=0 to 3; say
Line 7,942 ⟶ 8,263:
if n==0 then return ackermann(m-1, 1)
if m==2 then return n + 3 + n
return ackermann(m-1, ackermann(m, n-1) )</
{{out|output|text= when using the internal default input:}}
<pre style="height:60ex">
Line 8,026 ⟶ 8,347:
<br><br>If the '''numeric digits 100''' were to be increased to '''20000''', then the value of '''Ackermann(4,2)'''
<br>(the last line of output) would be presented with the full '''19,729''' decimal digits.
<
numeric digits 100 /*use up to 100 decimal digit integers.*/
/*╔═════════════════════════════════════════════════════════════╗
Line 8,061 ⟶ 8,382:
end
if n==0 then return ackermann(m-1, 1)
return ackermann(m-1, ackermann(m, n-1) )</
Output note: <u>none</u> of the numbers shown below use recursion to compute.
Line 8,149 ⟶ 8,470:
=={{header|Ring}}==
{{trans|C#}}
<
for n = 0 to 4
see "Ackermann(" + m + ", " + n + ") = " + Ackermann(m, n) + nl
Line 8,167 ⟶ 8,488:
ok
ok
Raise("Incorrect Numerical input !!!") </
{{out}}
<pre>Ackermann(0, 0) = 1
Line 8,190 ⟶ 8,511:
Ackermann(3, 4) = 125</pre>
=={{header|
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
Line 8,219 ⟶ 8,540:
addi sp, sp, 4
jr t0, 0
</syntaxhighlight>
=={{header|RPL}}==
{{works with|RPL|HP49-C}}
« '''CASE'''
OVER NOT '''THEN''' NIP 1 + '''END'''
DUP NOT '''THEN''' DROP 1 - 1 <span style="color:blue">ACKER</span> '''END'''
OVER 1 - ROT ROT 1 - <span style="color:blue">ACKER</span> <span style="color:blue">ACKER</span>
'''END'''
» '<span style="color:blue">ACKER</span>' STO
3 4 <span style="color:blue">ACKER</span>
{{out}}
<pre>
1: 125
</pre>
Runs in 7 min 13 secs on a HP-50g. Speed could be increased by replacing every <code>1</code> by <code>1.</code>, which would force calculations to be made with floating-point numbers, but we would then lose the arbitrary precision.
=={{header|Ruby}}==
{{trans|Ada}}
<
if m == 0
n + 1
Line 8,231 ⟶ 8,568:
ack(m-1, ack(m, n-1))
end
end</
Example:
<
puts (0..6).map { |n| ack(m, n) }.join(' ')
end</
{{out}}
<pre> 1 2 3 4 5 6 7
Line 8,243 ⟶ 8,580:
=={{header|Run BASIC}}==
<
function ackermann(m, n)
Line 8,249 ⟶ 8,586:
if (m > 0) and (n = 0) then ackermann = ackermann((m - 1), 1)
if (m > 0) and (n > 0) then ackermann = ackermann((m - 1), ackermann(m, (n - 1)))
end function</
=={{header|Rust}}==
<
if m == 0 {
n + 1
Line 8,266 ⟶ 8,603:
println!("{}", a); // 125
}
</syntaxhighlight>
Or:
<
fn ack(m: u64, n: u64) -> u64 {
match (m, n) {
Line 8,278 ⟶ 8,615:
}
}
</syntaxhighlight>
=={{header|Sather}}==
<
ackermann(m, n:INT):INT
Line 8,299 ⟶ 8,636:
end;
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
Line 8,319 ⟶ 8,656:
end;
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>
Line 8,334 ⟶ 8,671:
</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))
(else (A (- m 1) (A m (- 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
Line 8,376 ⟶ 8,713:
(cond ((= b 0) 1)
((= n 1) (expt a b))
(else (loop (-1+ n) (loop n (-1+ b)))))))</
=={{header|Scilab}}==
<syntaxhighlight lang="text">clear
function acker=ackermann(m,n)
global calls
Line 8,401 ⟶ 8,738:
printacker(i,j)
end
end</
{{out}}
<pre style="height:20ex">ackermann(0,0)=1 calls=1
Line 8,433 ⟶ 8,770:
=={{header|Seed7}}==
===Basic version===
<syntaxhighlight lang="seed7">const func integer: ackermann (in integer: m, in integer: n) is func
result
var integer: result is 0;
Line 8,444 ⟶ 8,782:
result := ackermann(pred(m), ackermann(m, pred(n)));
end if;
end func;</
Original source: [http://seed7.sourceforge.net/algorith/math.htm#ackermann]
===Improved version===
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i";
include "bigint.s7i";
const func bigInteger: ackermann (in bigInteger: m, in bigInteger: n) is func
result
var bigInteger: ackermann is 0_;
begin
case m of
when {0_}: ackermann := succ(n);
when {1_}: ackermann := n + 2_;
when {2_}: ackermann := 3_ + 2_ * n;
when {3_}: ackermann := 5_ + 8_ * pred(2_ ** ord(n));
otherwise:
if n = 0_ then
ackermann := ackermann(pred(m), 1_);
else
ackermann := ackermann(pred(m), ackermann(m, pred(n)));
end if;
end case;
end func;
const proc: main is func
local
var bigInteger: m is 0_;
var bigInteger: n is 0_;
var string: stri is "";
begin
for m range 0_ to 3_ do
for n range 0_ to 9_ do
writeln("A(" <& m <& ", " <& n <& ") = " <& ackermann(m, n));
end for;
end for;
writeln("A(4, 0) = " <& ackermann(4_, 0_));
writeln("A(4, 1) = " <& ackermann(4_, 1_));
stri := str(ackermann(4_, 2_));
writeln("A(4, 2) = (" <& length(stri) <& " digits)");
writeln(stri[1 len 80]);
writeln("...");
writeln(stri[length(stri) - 79 ..]);
end func;</syntaxhighlight>
Original source: [https://seed7.sourceforge.net/algorith/math.htm#bigInteger_ackermann]
{{out}}
<pre>
A(0, 0) = 1
A(0, 1) = 2
A(0, 2) = 3
A(0, 3) = 4
A(0, 4) = 5
A(0, 5) = 6
A(0, 6) = 7
A(0, 7) = 8
A(0, 8) = 9
A(0, 9) = 10
A(1, 0) = 2
A(1, 1) = 3
A(1, 2) = 4
A(1, 3) = 5
A(1, 4) = 6
A(1, 5) = 7
A(1, 6) = 8
A(1, 7) = 9
A(1, 8) = 10
A(1, 9) = 11
A(2, 0) = 3
A(2, 1) = 5
A(2, 2) = 7
A(2, 3) = 9
A(2, 4) = 11
A(2, 5) = 13
A(2, 6) = 15
A(2, 7) = 17
A(2, 8) = 19
A(2, 9) = 21
A(3, 0) = 5
A(3, 1) = 13
A(3, 2) = 29
A(3, 3) = 61
A(3, 4) = 125
A(3, 5) = 253
A(3, 6) = 509
A(3, 7) = 1021
A(3, 8) = 2045
A(3, 9) = 4093
A(4, 0) = 13
A(4, 1) = 65533
A(4, 2) = (19729 digits)
20035299304068464649790723515602557504478254755697514192650169737108940595563114
...
84717124577965048175856395072895337539755822087777506072339445587895905719156733
</pre>
=={{header|SETL}}==
<
(for m in [0..3])
Line 8,458 ⟶ 8,888:
end proc;
end program;</
=={{header|Shen}}==
<
0 N -> (+ N 1)
M 0 -> (ack (- M 1) 1)
M N -> (ack (- M 1)
(ack M (- N 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) }
func A(m, n) { A(m-1, A(m, n-1)) }</
Calling the function:
<
=={{header|Simula}}==
as modified by R. Péter and R. Robinson:
<
INTEGER procedure
Ackermann(g, p); SHORT INTEGER g, p;
Line 8,498 ⟶ 8,928:
outint(Ackermann(g, p), 0); outimage
END
END</
{{Output}}
<pre>Ackermann(4, 0) = 13
Line 8,508 ⟶ 8,938:
=={{header|Slate}}==
<
[
m isZero
Line 8,516 ⟶ 8,946:
ifTrue: [m - 1 ackermann: n]
ifFalse: [m - 1 ackermann: (m ackermann: n - 1)]]
].</
=={{header|Smalltalk}}==
<
ackermann := [ :n :m |
(n = 0) ifTrue: [ (m + 1) ]
Line 8,533 ⟶ 8,963:
(ackermann value: 0 value: 0) displayNl.
(ackermann value: 3 value: 4) displayNl.</
=={{header|SmileBASIC}}==
<
IF M==0 THEN
RETURN N+1
Line 8,544 ⟶ 8,974:
RETURN ACK(M-1,ACK(M,N-1))
ENDIF
END</
=={{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)
Line 8,560 ⟶ 8,990:
output = str; str = ''
n = 0; m = lt(m,3) m + 1 :s(L1)
end</
{{out}}
<pre>1 2 3 4 5 6 7
Line 8,568 ⟶ 8,998:
=={{header|SNUSP}}==
<
| | Ackermann function
| | /=========\!==\!====\ recursion:
Line 8,579 ⟶ 9,009:
? ? | \<<<+>+>>-/
\>>+<<-/!==========/
# #</
One could employ [[:Category:Recursion|tail recursion]] elimination by replacing "@/#" with "/" in two places above.
=={{header|SPAD}}==
{{works with|FriCAS, OpenAxiom, Axiom}}
<syntaxhighlight lang="spad">
NNI ==> NonNegativeInteger
Line 8,596 ⟶ 9,026:
-- Example
matrix [[A(i,j) for i in 0..3] for j in 0..3]
</syntaxhighlight>
{{out}}
Line 8,614 ⟶ 9,044:
{{works with|Db2 LUW}} version 9.7 or higher.
With SQL PL:
<
--#SET TERMINATOR @
Line 8,654 ⟶ 9,084:
END WHILE;
END @
</syntaxhighlight>
Output:
<pre>
Line 8,697 ⟶ 9,127:
=={{header|Standard ML}}==
<
| a (m, 0) = a (m-1, 1)
| a (m, n) = a (m-1, a (m, n-1))</
=={{header|Stata}}==
<
function ackermann(m,n) {
if (m==0) {
Line 8,718 ⟶ 9,148:
11
125
end</
=={{header|Swift}}==
<
if m == 0 {
return n+1
Line 8,729 ⟶ 9,159:
return ackerman(m-1, ackerman(m, n-1))
}
}</
=={{header|Tcl}}==
===Simple===
{{trans|Ruby}}
<
if {$m == 0} {
expr {$n + 1}
Line 8,742 ⟶ 9,172:
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}
Line 8,753 ⟶ 9,183:
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
Line 8,811 ⟶ 9,241:
# Some small tweaks...
interp recursionlimit {} 100000
interp alias {} ack {} cacheable ack</
But even with all this, you still run into problems calculating <math>\mathit{ack}(4,3)</math> as that's kind-of large…
Line 8,818 ⟶ 9,248:
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
Line 8,838 ⟶ 9,268:
:prgmACKERMAN
:End
: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
:Disp Ans</
=={{header|TI-89 BASIC}}==
<
=={{header|TorqueScript}}==
<
{
if(%m==0)
Line 8,861 ⟶ 9,291:
if(%m>0&&%n>0)
return ackermann(%m-1,ackermann(%m,%n-1));
}</
=={{header|Transd}}==
<syntaxhighlight lang="Scheme">#lang transd
MainModule: {
Ack: Lambda<Int Int Int>(λ m Int() n Int()
(if (not m) (ret (+ n 1)))
(if (not n) (ret (exec Ack (- m 1) 1)))
(ret (exec Ack (- m 1) (exec Ack m (- n 1))))
),
_start: (λ (textout (exec Ack 3 1) "\n"
(exec Ack 3 2) "\n"
(exec Ack 3 3)))
}</syntaxhighlight>
{{out}}
<pre>
13
29
61
</pre>
=={{header|TSE SAL}}==
<
INTEGER PROC FNMathGetAckermannRecursiveI( INTEGER mI, INTEGER nI )
IF ( mI == 0 )
Line 8,881 ⟶ 9,331:
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
END</
=={{header|TXR}}==
Line 8,888 ⟶ 9,338:
with memoization.
<
(let ((hash (gensym "hash-"))
(argl (gensym "args-"))
Line 8,909 ⟶ 9,359:
(each ((i (range 0 3)))
(each ((j (range 0 4)))
(format t "ack(~a, ~a) = ~a\n" i j (ack i j))))</
{{out}}
Line 8,936 ⟶ 9,386:
=={{header|UNIX Shell}}==
{{works with|Bash}}
<
local m=$1
local n=$2
Line 8,946 ⟶ 9,396:
ack $((m-1)) $(ack $m $((n-1)))
fi
}</
Example:
<
for ((n=0;n<=6;n++)); do
ack $m $n
Line 8,954 ⟶ 9,404:
done
echo
done</
{{out}}
<pre>1 2 3 4 5 6 7
Line 8,960 ⟶ 9,410:
3 5 7 9 11 13 15
5 13 29 61 125 253 509</pre>
=={{header|Ursalang}}==
<syntaxhighlight lang="ursalang">let A = fn(m, n) {
if m == 0 {n + 1}
else if m > 0 and n == 0 {A(m - 1, 1)}
else {A(m - 1, A(m, n - 1))}
}
print(A(0, 0))
print(A(3, 4))
print(A(3, 1))</syntaxhighlight>
=={{header|Ursala}}==
Anonymous recursion is the usual way of doing things like this.
<
#import nat
Line 8,970 ⟶ 9,431:
~&al^?\successor@ar ~&ar?(
^R/~&f ^/predecessor@al ^|R/~& ^|/~& predecessor,
^|R/~& ~&\1+ predecessor@l)</
test program for the first 4 by 7 numbers:
<
test = block7 ackermann*K0 iota~~/4 7</
{{out}}
<pre>
Line 8,985 ⟶ 9,446:
=={{header|V}}==
{{trans|Joy}}
<
[ [pop zero?] [popd succ]
[zero?] [pop pred 1 ack]
[true] [[dup pred swap] dip pred ack ack ]
] when].</
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]
] when].</
=={{header|Vala}}==
<
if (m == 0) return n + 1;
if (n == 0) return ackermann(m - 1, 1);
Line 9,010 ⟶ 9,471:
}
}
}</
{{out}}
Line 9,057 ⟶ 9,518:
=={{header|VBA}}==
<
Dim result As Variant
Debug.Assert m >= 0
Line 9,085 ⟶ 9,546:
Debug.Print
Next i
End Sub</
<pre> n= 0 1 2 3 4 5 6 7
m=0 1 2 3 4 5 6 7 8
Line 9,095 ⟶ 9,556:
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)
Line 9,114 ⟶ 9,575:
end if
end function</
;Invocation
<
'~ depth = 0
wscript.echo ack( 2, 1 )
'~ depth = 0
wscript.echo ack( 4, 4 )</
{{out}}
<pre>
Line 9,131 ⟶ 9,592:
{{trans|Rexx}}
{{works with|Visual Basic|VB6 Standard}}
<syntaxhighlight lang="vb">
Option Explicit
Dim calls As Long
Line 9,160 ⟶ 9,621:
End If
End If
End Function 'ackermann</
{{Out}}
<pre style="height:20ex">ackermann( 0 , 0 )= 1 calls= 1
Line 9,205 ⟶ 9,666:
ackermann( 4 , 1 )= out of stack space</pre>
=={{header|V (Vlang)}}==
<
if m == 0 {
return n + 1
Line 9,223 ⟶ 9,684:
}
}
</syntaxhighlight>
{{out}}
Line 9,249 ⟶ 9,710:
=={{header|Wart}}==
<
(if m=0
n+1
Line 9,255 ⟶ 9,716:
(ackermann m-1 1)
:else
(ackermann m-1 (ackermann m n-1)))</
=={{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|
Line 9,278 ⟶ 9,739:
var p2 = pair[1]
System.print("A[%(p1), %(p2)] = %(Ackermann.call(p1, p2))")
}</
{{out}}
Line 9,293 ⟶ 9,754:
{{works with|nasm}}
{{works with|windows}}
<
section .text
Line 9,323 ⟶ 9,784:
call ack1 ;return ack(M-1,1)
ret
</syntaxhighlight>
=={{header|XLISP}}==
<
(cond
((= m 0) (+ n 1))
((= n 0) (ackermann (- m 1) 1))
(t (ackermann (- m 1) (ackermann m (- n 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
Line 9,342 ⟶ 9,803:
=={{header|XPL0}}==
<
func Ackermann(M, N);
Line 9,357 ⟶ 9,818:
CrLf(0);
];
]</
Recursion overflows the stack if either M or N is extended by a single count.
{{out}}
Line 9,370 ⟶ 9,831:
The following named template calculates the Ackermann function:
<
<xsl:template name="ackermann">
<xsl:param name="m"/>
Line 9,400 ⟶ 9,861:
</xsl:choose>
</xsl:template>
</syntaxhighlight>
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,449 ⟶ 9,910:
</xsl:template>
</xsl:stylesheet>
</syntaxhighlight>
Which will transform this input
<
<?xml version="1.0" ?>
<?xml-stylesheet type="text/xsl" href="ackermann.xslt"?>
Line 9,601 ⟶ 10,062:
</args>
</arguments>
</syntaxhighlight>
into this output
Line 9,644 ⟶ 10,105:
=={{header|Yabasic}}==
<
if M = 0 return N + 1
if N = 0 return ack(M-1,1)
Line 9,651 ⟶ 10,112:
print ack(3, 4)
</syntaxhighlight>
What smart code can get. Fast as lightning!
{{trans|Phix}}
<
if m=0 then
return n+1
Line 9,682 ⟶ 10,143:
end sub
Ackermann()</
=={{header|Yorick}}==
<
if(m == 0)
return n + 1;
Line 9,692 ⟶ 10,153:
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
Line 9,705 ⟶ 10,166:
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
Line 9,818 ⟶ 10,276:
txt_m_is: db "m=$"
crlf: db 10,13,'$'</
{{out}}
<pre>
Line 9,830 ⟶ 10,288:
Source -> http://ideone.com/53FzPA
Compiled -> http://ideone.com/OlS7zL
<
comment:
(=) m 0
Line 9,858 ⟶ 10,316:
comment:
#true
(003) "=" n1 n2</
=={{header|Zig}}==
<
if (m == 0) return n + 1;
if (n == 0) return ack(m - 1, 1);
Line 9,877 ⟶ 10,335:
try stdout.print("\n", .{});
}
}</
{{out}}
<pre> 1 2 3 4 5 6 7 8 9
Line 9,886 ⟶ 10,344:
=={{header|ZX Spectrum Basic}}==
{{trans|BASIC256}}
<
20 LET s(1,1)=3: REM M
30 LET s(1,2)=7: REM N
Line 9,904 ⟶ 10,362:
190 LET s(lev-1,3)=s(lev,3)
200 LET lev=lev-1
210 RETURN </
{{out}}
<pre>A(3,7) = 1021</pre>
{{omit from|LaTeX}}
{{omit from|Make}}
{{omit from|PlainTeX}}
|