Ackermann function: Difference between revisions
m
Automated syntax highlighting fixup (second round - minor fixes)
m (→{{header|Joy}}) |
Thundergnat (talk | contribs) m (Automated syntax highlighting fixup (second round - minor fixes)) |
||
Line 34:
{{trans|Python}}
<syntaxhighlight lang="11l">F ack2(m, n) -> Int
R I m == 0 {(n + 1)
} E I m == 1 {(n + 2)
Line 57:
The OS/360 linkage is a bit tricky with the S/360 basic instruction set.
To simplify, the program is recursive not reentrant.
<syntaxhighlight lang="360asm">* Ackermann function 07/09/2015
&LAB XDECO ®,&TARGET
.*-----------------------------------------------------------------*
Line 199:
This implementation is based on the code shown in the computerphile episode in the youtube link at the top of this page (time index 5:00).
<syntaxhighlight lang="68000devpac">;
; Ackermann function for Motorola 68000 under AmigaOs 2+ by Thorham
;
Line 317:
and <code>n ∊ [0,9)</code>, on a real 8080 this takes a little over two minutes.
<syntaxhighlight lang="8080asm"> org 100h
jmp demo
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Line 410:
This code does 16-bit math just like the 8080 version.
<syntaxhighlight lang="asm"> cpu 8086
bits 16
org 100h
Line 479:
=={{header|8th}}==
<syntaxhighlight lang=
\ Ackermann function, illustrating use of "memoization".
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=
/* ARM assembly AARCH64 Raspberry PI 3B or android 64 bits */
/* program ackermann64.s */
Line 739:
=={{header|ABAP}}==
<syntaxhighlight lang=
REPORT zhuberv_ackermann.
Line 789:
=={{header|Action!}}==
Action! language does not support recursion. Therefore an iterative approach with a stack has been proposed.
<syntaxhighlight lang=
CARD ARRAY stack(MAXSIZE)
CARD stacksize=[0]
Line 872:
=={{header|ActionScript}}==
<syntaxhighlight lang="actionscript">public function ackermann(m:uint, n:uint):uint
{
if (m == 0)
Line 887:
=={{header|Ada}}==
<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Ackermann is
Line 918:
{{works with|Agda|2.5.2}}
{{libheader|agda-stdlib v0.13}}
<syntaxhighlight lang="agda">
open import Data.Nat
open import Data.Nat.Show
Line 935:
Note the unicode ℕ characters, they can be input in emacs agda mode using "\bN". Running in bash:
<syntaxhighlight lang="bash">
agda --compile Ackermann.agda
./Ackermann
Line 947:
=={{header|ALGOL 60}}==
{{works with|A60}}
<syntaxhighlight lang="algol60">begin
integer procedure ackermann(m,n);value m,n;integer m,n;
ackermann:=if m=0 then n+1
Line 972:
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}
<syntaxhighlight lang="algol68">PROC test ackermann = VOID:
BEGIN
PROC ackermann = (INT m, n)INT:
Line 1,003:
=={{header|ALGOL W}}==
{{Trans|ALGOL 60}}
<syntaxhighlight lang="algolw">begin
integer procedure ackermann( integer value m,n ) ;
if m=0 then n+1
Line 1,023:
=={{header|APL}}==
{{works with|Dyalog APL}}
<syntaxhighlight lang=
0=1⊃⍵:1+2⊃⍵
0=2⊃⍵:∇(¯1+1⊃⍵)1
Line 1,031:
=={{header|AppleScript}}==
<syntaxhighlight lang=
if m is equal to 0 then return n + 1
if n is equal to 0 then return ackermann(m - 1, 1)
Line 1,039:
=={{header|Argile}}==
{{works with|Argile|1.0.0}}
<syntaxhighlight lang=
for each (val nat n) from 0 to 6
Line 1,051:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}
<syntaxhighlight lang=
/* ARM assembly Raspberry PI or android 32 bits */
/* program ackermann.s */
Line 1,218:
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">ackermann: function [m,n][
(m=0)? -> n+1 [
(n=0)? -> ackermann m-1 1
Line 1,255:
=={{header|ATS}}==
<syntaxhighlight lang=
{m,n:nat} .<m,n>.
(m: int m, n: int n): Nat =
Line 1,265:
=={{header|AutoHotkey}}==
<syntaxhighlight lang=
If (m > 0) && (n = 0)
Return A(m-1,1)
Line 1,279:
=={{header|AutoIt}}==
=== Classical version ===
<syntaxhighlight lang="autoit">Func Ackermann($m, $n)
If ($m = 0) Then
Return $n+1
Line 1,295:
This version works way faster than the classical one: Ackermann(3, 5) runs in 12,7 ms, while the classical version takes 402,2 ms.
<syntaxhighlight lang="autoit">Global $ackermann[2047][2047] ; Set the size to whatever you want
Func Ackermann($m, $n)
If ($ackermann[$m][$n] <> 0) Then
Line 1,315:
=={{header|AWK}}==
<syntaxhighlight lang="awk">function ackermann(m, n)
{
if ( m == 0 ) {
Line 1,335:
=={{header|Babel}}==
<syntaxhighlight lang="babel">main:
{((0 0) (0 1) (0 2)
(0 3) (0 4) (1 0)
Line 1,391:
=={{header|BASIC}}==
==={{header|Applesoft BASIC}}===
<syntaxhighlight lang="basic">100 DIM R%(2900),M(2900),N(2900)
110 FOR M = 0 TO 3
120 FOR N = 0 TO 4
Line 1,417:
==={{header|BASIC256}}===
<syntaxhighlight lang="basic256">dim stack(5000, 3) # BASIC-256 lacks functions (as of ver. 0.9.6.66)
stack[0,0] = 3 # M
stack[0,1] = 7 # N
Line 1,455:
</pre>
<syntaxhighlight lang="basic256"># BASIC256 since 0.9.9.1 supports functions
for m = 0 to 3
for n = 0 to 4
Line 1,499:
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic"> PRINT FNackermann(3, 7)
END
Line 1,511:
BASIC runs out of stack space very quickly.
The call <tt>ack(3, 4)</tt> gives a stack error.
<syntaxhighlight lang="qbasic">DECLARE FUNCTION ack! (m!, n!)
FUNCTION ack (m!, n!)
Line 1,526:
=={{header|Batch File}}==
Had trouble with this, so called in the gurus at [http://stackoverflow.com/questions/2680668/what-is-wrong-with-this-recursive-windows-cmd-script-it-wont-do-ackermann-prope StackOverflow]. Thanks to Patrick Cuff for pointing out where I was going wrong.
<syntaxhighlight lang="dos">::Ackermann.cmd
@echo off
set depth=0
Line 1,558:
if %depth%==0 ( exit %t% ) else ( exit /b %t% )</syntaxhighlight>
Because of the <code>exit</code> statements, running this bare closes one's shell, so this test routine handles the calling of Ackermann.cmd
<syntaxhighlight lang="dos">::Ack.cmd
@echo off
cmd/c ackermann.cmd %1 %2
Line 1,579:
{{works with|OpenBSD bc}}
{{Works with|GNU bc}}
<syntaxhighlight lang="bc">define ack(m, n) {
if ( m == 0 ) return (n+1);
if ( n == 0 ) return (ack(m-1, 1));
Line 1,593:
=={{header|BCPL}}==
<syntaxhighlight lang=
LET ack(m, n) = m=0 -> n+1,
Line 1,609:
Iterative slow version:
<syntaxhighlight lang="beeswax">
>M?f@h@gMf@h3yzp if m>0 and n>0 => replace m,n with m-1,m,n-1
>@h@g'b?1f@h@gM?f@hzp if m>0 and n=0 => replace m,n with m-1,1
Line 1,625:
Each block of <code>1FJ</code> or <code>1fFJ</code> in the code is a call of the Ackermann function itself.
<syntaxhighlight lang="beeswax">Ag~1?Lp1~2@g'p?g?Pf1FJ Ackermann function. if m=0 => run Ackermann function (m, n+1)
xI; x@g'p??@Mf1fFJ if m>0 and n=0 => run Ackermann (m-1,1)
xM@~gM??f~f@f1FJ if m>0 and n>0 => run Ackermann(m,Ackermann(m-1,n-1))
Line 1,631:
Highly optimized and fast version, returns A(4,1)/A(5,0) almost instantaneously:
<syntaxhighlight lang="beeswax">
>Mf@Ph?@g@2h@Mf@Php if m>4 and n>0 => replace m,n with m-1,m,n-1
>~4~L#1~2hg'd?1f@hgM?f2h p if m>4 and n=0 => replace m,n with m-1,1
Line 1,651:
{{trans|ERRE}}
Since Befunge-93 doesn't have recursive capabilities we need to use an iterative algorithm.
<syntaxhighlight lang="befunge">&>&>vvg0>#0\#-:#1_1v
@v:\<vp0 0:-1<\+<
^>00p>:#^_$1+\:#^_$.
Line 1,658:
===Befunge-98===
{{works with|CCBI|2.1}}
<syntaxhighlight lang="befunge">r[1&&{0
>v
j
Line 1,670:
=={{header|BQN}}==
<syntaxhighlight lang=
A 0‿n: n+1;
A m‿0: A (m-1)‿1;
Line 1,676:
}</syntaxhighlight>
Example usage:
<syntaxhighlight lang="text"> A 0‿3
4
A 1‿4
Line 1,690:
The value of A(4,1) cannot be computed due to stack overflow.
It can compute A(3,9) (4093), but probably not A(3,10)
<syntaxhighlight lang="bracmat">( Ack
= m n
. !arg:(?m,?n)
Line 1,705:
Although all known values are stored in the hash table, the converse is not true: an element in the hash table is either a "known known" or an "unknown unknown" associated with an "known unknown".
<syntaxhighlight lang="bracmat"> ( A
= m n value key eq chain
, find insert future stack va val
Line 1,774:
</pre>
The last solution is a recursive solution that employs some extra formulas, inspired by the Common Lisp solution further down.
<syntaxhighlight lang="bracmat">( AckFormula
= m n
. !arg:(?m,?n)
Line 1,792:
=={{header|Brat}}==
<syntaxhighlight lang="brat">ackermann = { m, n |
when { m == 0 } { n + 1 }
{ m > 0 && n == 0 } { ackermann(m - 1, 1) }
Line 1,802:
=={{header|C}}==
Straightforward implementation per Ackermann definition:
<syntaxhighlight lang=
int ackermann(int m, int n)
Line 1,842:
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:
<syntaxhighlight lang=
#include <stdlib.h>
#include <string.h>
Line 1,908:
A couple of alternative approaches...
<syntaxhighlight lang=
#include <conio.h>
Line 2,010:
A couple of more iterative techniques...
<syntaxhighlight lang=
#include <conio.h>
Line 2,163:
===Basic Version===
<syntaxhighlight lang="csharp">using System;
class Program
{
Line 2,220:
===Efficient Version===
<syntaxhighlight lang="csharp">
using System;
using System.Numerics;
Line 2,354:
===Basic version===
<syntaxhighlight lang="cpp">#include <iostream>
unsigned int ackermann(unsigned int m, unsigned int n) {
Line 2,379:
C++11 with boost's big integer type. Compile with:
g++ -std=c++11 -I /path/to/boost ackermann.cpp.
<syntaxhighlight lang="cpp">#include <iostream>
#include <sstream>
#include <string>
Line 2,483:
=={{header|Chapel}}==
<syntaxhighlight lang="chapel">proc A(m:int, n:int):int {
if m == 0 then
return n + 1;
Line 2,493:
=={{header|Clay}}==
<syntaxhighlight lang=
if(m == 0)
return n + 1;
Line 2,504:
=={{header|CLIPS}}==
'''Functional solution'''
<syntaxhighlight lang="clips">(deffunction ackerman
(?m ?n)
(if (= 0 ?m)
Line 2,525:
</pre>
'''Fact-based solution'''
<syntaxhighlight lang="clips">(deffacts solve-items
(solve 0 4)
(solve 1 4)
Line 2,620:
=={{header|Clojure}}==
<syntaxhighlight lang="clojure">(defn ackermann [m n]
(cond (zero? m) (inc n)
(zero? n) (ackermann (dec m) 1)
Line 2,626:
=={{header|CLU}}==
<syntaxhighlight lang="clu">% Ackermann function
ack = proc (m, n: int) returns (int)
if m=0 then return(n+1)
Line 2,652:
=={{header|COBOL}}==
<syntaxhighlight lang="cobol"> IDENTIFICATION DIVISION.
PROGRAM-ID. Ackermann.
Line 2,686:
=={{header|CoffeeScript}}==
<syntaxhighlight lang="coffeescript">ackermann = (m, n) ->
if m is 0 then n + 1
else if m > 0 and n is 0 then ackermann m - 1, 1
Line 2,692:
=={{header|Comal}}==
<syntaxhighlight lang="comal">0010 //
0020 // Ackermann function
0030 //
Line 2,716:
=={{header|Common Lisp}}==
<syntaxhighlight lang="lisp">(defun ackermann (m n)
(cond ((zerop m) (1+ n))
((zerop n) (ackermann (1- m) 1))
(t (ackermann (1- m) (ackermann m (1- n))))))</syntaxhighlight>
More elaborately:
<syntaxhighlight lang="lisp">(defun ackermann (m n)
(case m ((0) (1+ n))
((1) (+ 2 n))
Line 2,744:
=={{header|Component Pascal}}==
BlackBox Component Builder
<syntaxhighlight lang="oberon2">
MODULE NpctAckerman;
Line 2,785:
=={{header|Coq}}==
<syntaxhighlight lang="coq">Require Import Arith.
Fixpoint A m := fix A_m n :=
match m with
Line 2,796:
end.</syntaxhighlight>
<syntaxhighlight lang="coq">Require Import Utf8.
Section FOLD.
Line 2,813:
=={{header|Crystal}}==
{{trans|Ruby}}
<syntaxhighlight lang="ruby">def ack(m, n)
if m == 0
n + 1
Line 2,839:
=={{header|D}}==
===Basic version===
<syntaxhighlight lang="d">ulong ackermann(in ulong m, in ulong n) pure nothrow @nogc {
if (m == 0)
return n + 1;
Line 2,853:
===More Efficient Version===
{{trans|Mathematica}}
<syntaxhighlight lang="d">import std.stdio, std.bigint, std.conv;
BigInt ipow(BigInt base, BigInt exp) pure nothrow {
Line 2,930:
=={{header|Dart}}==
no caching, the implementation takes ages even for A(4,1)
<syntaxhighlight lang="dart">int A(int m, int n) => m==0 ? n+1 : n==0 ? A(m-1,1) : A(m-1,A(m,n-1));
main() {
Line 2,946:
=={{header|Dc}}==
This needs a modern Dc with <code>r</code> (swap) and <code>#</code> (comment). It easily can be adapted to an older Dc, but it will impact readability a lot.
<syntaxhighlight lang="dc">[ # todo: n 0 -- n+1 and break 2 levels
+ 1 + # n+1
q
Line 2,975:
=={{header|Delphi}}==
<syntaxhighlight lang="delphi">function Ackermann(m,n:Int64):Int64;
begin
if m = 0 then
Line 2,986:
=={{header|Draco}}==
<syntaxhighlight lang="draco">/* Ackermann function */
proc ack(word m, n) word:
if m=0 then n+1
Line 3,011:
=={{header|DWScript}}==
<syntaxhighlight lang="delphi">function Ackermann(m, n : Integer) : Integer;
begin
if m = 0 then
Line 3,021:
=={{header|Dylan}}==
<syntaxhighlight lang="dylan">define method ack(m == 0, n :: <integer>)
n + 1
end;
Line 3,029:
=={{header|E}}==
<syntaxhighlight lang="e">def A(m, n) {
return if (m <=> 0) { n+1 } \
else if (m > 0 && n <=> 0) { A(m-1, 1) } \
Line 3,036:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">func ackerm m n . r .
if m = 0
r = n + 1
Line 3,050:
=={{header|Egel}}==
<syntaxhighlight lang=
def ackermann =
[ 0 N -> N + 1
Line 3,062:
[https://github.com/ljr1981/rosettacode_answers/blob/main/testing/rc_ackerman/rc_ackerman_test_set.e Test of Example code]
<syntaxhighlight lang=
class
ACKERMAN_EXAMPLE
Line 3,089:
=={{header|Ela}}==
<syntaxhighlight lang="ela">ack 0 n = n+1
ack m 0 = ack (m - 1) 1
ack m n = ack (m - 1) <| ack m <| n - 1</syntaxhighlight>
Line 3,095:
=={{header|Elena}}==
ELENA 4.x :
<syntaxhighlight lang="elena">import extensions;
ackermann(m,n)
Line 3,154:
=={{header|Elixir}}==
<syntaxhighlight lang="elixir">defmodule Ackermann do
def ack(0, n), do: n + 1
def ack(m, 0), do: ack(m - 1, 1)
Line 3,173:
=={{header|Emacs Lisp}}==
<syntaxhighlight lang="lisp">(defun ackermann (m n)
(cond ((zerop m) (1+ n))
((zerop n) (ackermann (1- m) 1))
Line 3,181:
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">
-module(ackermann).
-export([ackermann/2]).
Line 3,197:
substituted with the new ERRE control statements.
<syntaxhighlight lang="erre">
PROGRAM ACKERMAN
Line 3,270:
=={{header|Euler Math Toolbox}}==
<syntaxhighlight lang=
>M=zeros(1000,1000);
>function map A(m,n) ...
Line 3,291:
=={{header|Euphoria}}==
This is based on the [[VBScript]] example.
<syntaxhighlight lang=
if m = 0 then
return n + 1
Line 3,309:
=={{header|Ezhil}}==
<syntaxhighlight lang=
நிரல்பாகம் அகெர்மன்(முதலெண், இரண்டாமெண்)
Line 3,352:
=={{header|F_Sharp|F#}}==
The following program implements the Ackermann function in F# but is not tail-recursive and so runs out of stack space quite fast.
<syntaxhighlight lang="fsharp">let rec ackermann m n =
match m, n with
| 0, n -> n + 1
Line 3,361:
printfn "%A" (ackermann (int fsi.CommandLineArgs.[1]) (int fsi.CommandLineArgs.[2]))</syntaxhighlight>
Transforming this into continuation passing style avoids limited stack space by permitting tail-recursion.
<syntaxhighlight lang="fsharp">let ackermann M N =
let rec acker (m, n, k) =
match m,n with
Line 3,370:
=={{header|Factor}}==
<syntaxhighlight lang="factor">USING: kernel math locals combinators ;
IN: ackermann
Line 3,381:
=={{header|Falcon}}==
<syntaxhighlight lang="falcon">function ackermann( m, n )
if m == 0: return( n + 1 )
if n == 0: return( ackermann( m - 1, 1 ) )
Line 3,404:
=={{header|FALSE}}==
<syntaxhighlight lang="false">[$$[%
\$$[%
1-\$@@a;! { i j -> A(i-1, A(i, j-1)) }
Line 3,418:
=={{header|Fantom}}==
<syntaxhighlight lang="fantom">class Main
{
// assuming m,n are positive
Line 3,476:
=={{header|FBSL}}==
Mixed-language solution using pure FBSL, Dynamic Assembler, and Dynamic C layers of FBSL v3.5 concurrently. '''The following is a single script'''; the breaks are caused by switching between RC's different syntax highlighting schemes:
<syntaxhighlight lang="qbasic">#APPTYPE CONSOLE
TestAckermann()
Line 3,497:
END FUNCTION
DYNC AckermannC(m AS INTEGER, n AS INTEGER) AS INTEGER</syntaxhighlight><syntaxhighlight lang=
int Ackermann(int m, int n)
{
Line 3,508:
{
return Ackermann(m, n);
}</syntaxhighlight><syntaxhighlight lang="qbasic">
END DYNC
DYNASM AckermannA(m AS INTEGER, n AS INTEGER) AS INTEGER</syntaxhighlight><syntaxhighlight lang="asm">
ENTER 0, 0
INVOKE Ackermann, m, n
Line 3,547:
LEAVE
RET 8
</syntaxhighlight><syntaxhighlight lang="qbasic">END DYNASM</syntaxhighlight>
{{out}}
Line 3,560:
=={{header|Fermat}}==
<syntaxhighlight lang="fermat">Func A(m,n) = if m = 0 then n+1 else if n = 0 then A(m-1,1) else A(m-1,A(m,n-1)) fi fi.;
A(3,8)</syntaxhighlight>
{{out}}
Line 3,568:
=={{header|Forth}}==
<syntaxhighlight lang="forth">: acker ( m n -- u )
over 0= IF nip 1+ EXIT THEN
swap 1- swap ( m-1 n -- )
Line 3,577:
FORTH> 3 4 acker . 125 ok</pre>
An optimized version:
<syntaxhighlight lang="forth">: ackermann ( m n -- u )
over ( case statement)
0 over = if drop nip 1+ else
Line 3,594:
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<syntaxhighlight lang="fortran">PROGRAM EXAMPLE
IMPLICIT NONE
Line 3,626:
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">' version 28-10-2016
' compile with: fbc -s console
' to do A(4, 2) the stack size needs to be increased
Line 3,675:
=={{header|FunL}}==
<syntaxhighlight lang="funl">def
ackermann( 0, n ) = n + 1
ackermann( m, 0 ) = ackermann( m - 1, 1 )
Line 3,710:
=={{header|Futhark}}==
<syntaxhighlight lang=
fun ackermann(m: int, n: int): int =
if m == 0 then n + 1
Line 3,718:
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
include "NSLog.incl"
Line 3,800:
=={{header|Gambas}}==
<syntaxhighlight lang="gambas">Public Function Ackermann(m As Float, n As Float) As Float
If m = 0 Then
Return n + 1
Line 3,820:
=={{header|GAP}}==
<syntaxhighlight lang="gap">ack := function(m, n)
if m = 0 then
return n + 1;
Line 3,833:
=={{header|Genyris}}==
<syntaxhighlight lang="genyris">def A (m n)
cond
(equal? m 0)
Line 3,845:
=={{header|GML}}==
Define a script resource named ackermann and paste this code inside:
<syntaxhighlight lang=
var m, n;
m = argument0;
Line 3,863:
=={{header|gnuplot}}==
<syntaxhighlight lang="gnuplot">A (m, n) = m == 0 ? n + 1 : n == 0 ? A (m - 1, 1) : A (m - 1, A (m, n - 1))
print A (0, 4)
print A (1, 4)
Line 3,876:
=={{header|Go}}==
===Classic version===
<syntaxhighlight lang="go">func Ackermann(m, n uint) uint {
switch 0 {
case m:
Line 3,886:
}</syntaxhighlight>
===Expanded version===
<syntaxhighlight lang="go">func Ackermann2(m, n uint) uint {
switch {
case m == 0:
Line 3,902:
}</syntaxhighlight>
===Expanded version with arbitrary precision===
<syntaxhighlight lang="go">package main
import (
Line 4,005:
=={{header|Golfscript}}==
<syntaxhighlight lang="golfscript">{
:_n; :_m;
_m 0= {_n 1+}
Line 4,015:
=={{header|Groovy}}==
<syntaxhighlight lang="groovy">def ack ( m, n ) {
assert m >= 0 && n >= 0 : 'both arguments must be non-negative'
m == 0 ? n + 1 : n == 0 ? ack(m-1, 1) : ack(m-1, ack(m, n-1))
}</syntaxhighlight>
Test program:
<syntaxhighlight lang="groovy">def ackMatrix = (0..3).collect { m -> (0..8).collect { n -> ack(m, n) } }
ackMatrix.each { it.each { elt -> printf "%7d", elt }; println() }</syntaxhighlight>
{{out}}
Line 4,030:
=={{header|Hare}}==
<syntaxhighlight lang="hare">use fmt;
fn ackermann(m: u64, n: u64) u64 = {
Line 4,052:
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">ack :: Int -> Int -> Int
ack 0 n = succ n
ack m 0 = ack (pred m) 1
Line 4,064:
Generating a list instead:
<syntaxhighlight lang="haskell">import Data.List (mapAccumL)
-- everything here are [Int] or [[Int]], which would overflow
Line 4,076:
=={{header|Haxe}}==
<syntaxhighlight lang="haxe">class RosettaDemo
{
static public function main()
Line 4,098:
=={{header|Hoon}}==
<syntaxhighlight lang=
|= [m=@ud n=@ud]
?: =(m 0)
Line 4,111:
Taken from the public domain Icon Programming Library's [http://www.cs.arizona.edu/icon/library/procs/memrfncs.htm acker in memrfncs],
written by Ralph E. Griswold.
<syntaxhighlight lang=
static memory
Line 4,144:
=={{header|Idris}}==
<syntaxhighlight lang="idris">A : Nat -> Nat -> Nat
A Z n = S n
A (S m) Z = A m (S Z)
Line 4,151:
=={{header|Ioke}}==
{{trans|Clojure}}
<syntaxhighlight lang="ioke">ackermann = method(m,n,
cond(
m zero?, n succ,
Line 4,160:
=={{header|J}}==
As posted at the [[j:Essays/Ackermann%27s%20Function|J wiki]]
<syntaxhighlight lang="j">ack=: c1`c1`c2`c3 @. (#.@,&*) M.
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}}
<syntaxhighlight lang="j"> 0 ack 3
4
1 ack 3
Line 4,178:
The Ackermann function derived in this fashion is primitive recursive. This is possible because in J (as in some other languages) functions, or representations of them, are first-class values.
<syntaxhighlight lang="j"> Ack=. 3 -~ [ ({&(2 4$'>: 2x&+') ::(,&'&1'&'2x&*'@:(-&2))"0@:[ 128!:2 ]) 3 + ]</syntaxhighlight>
{{out|Example use}}
<syntaxhighlight lang="j"> 0 1 2 3 Ack 0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
Line 4,199:
A structured derivation of Ack follows:
<syntaxhighlight lang="j"> o=. @: NB. Composition of verbs (functions)
x=. o[ NB. Composing the left noun (argument)
Line 4,229:
=={{header|Java}}==
[[Category:Arbitrary precision]]
<syntaxhighlight lang="java">import java.math.BigInteger;
public static BigInteger ack(BigInteger m, BigInteger n) {
Line 4,239:
{{works with|Java|8+}}
<syntaxhighlight lang="java5">@FunctionalInterface
public interface FunctionalField<FIELD extends Enum<?>> {
public Object untypedField(FIELD field);
Line 4,248:
}
}</syntaxhighlight>
<syntaxhighlight lang="java5">import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Predicate;
Line 4,294:
}
}</syntaxhighlight>
<syntaxhighlight lang="java5">import java.math.BigInteger;
import java.util.Stack;
import java.util.function.BinaryOperator;
Line 4,440:
}</syntaxhighlight>
{{Iterative version}}
<syntaxhighlight lang="java5">/*
* Source https://stackoverflow.com/a/51092690/5520417
*/
Line 4,834:
=={{header|JavaScript}}==
===ES5===
<syntaxhighlight lang="javascript">function ack(m, n) {
return m === 0 ? n + 1 : ack(m - 1, n === 0 ? 1 : ack(m, n - 1));
}</syntaxhighlight>
===Eliminating Tail Calls===
<syntaxhighlight lang="javascript">function ack(M,N) {
for (; M > 0; M--) {
N = N === 0 ? 1 : ack(M,N-1);
Line 4,845:
}</syntaxhighlight>
===Iterative, With Explicit Stack===
<syntaxhighlight lang="javascript">function stackermann(M, N) {
const stack = [];
for (;;) {
Line 4,866:
}</syntaxhighlight>
===Stackless Iterative===
<syntaxhighlight lang="javascript">#!/usr/bin/env nodejs
function ack(M, N){
const next = new Float64Array(M + 1);
Line 4,901:
===ES6===
<syntaxhighlight lang="javascript">(() => {
'use strict';
Line 4,943:
=={{header|Joy}}==
<syntaxhighlight lang="joy">DEFINE ack == [[[pop null] popd succ]
[[null] pop pred 1 ack]
[[dup pred swap] dip pred ack ack]]
cond.</syntaxhighlight>
another using a combinator:
<syntaxhighlight lang="joy">DEFINE ack == [[[pop null] [popd succ]]
[[null] [pop pred 1] []]
[[[dup pred swap] dip pred] [] []]]
Line 4,956:
{{ works with|jq|1.4}}
===Without Memoization===
<syntaxhighlight lang="jq"># input: [m,n]
def ack:
.[0] as $m | .[1] as $n
Line 4,964:
end ;</syntaxhighlight>
'''Example:'''
<syntaxhighlight lang="jq">range(0;5) as $i
| range(0; if $i > 3 then 1 else 6 end) as $j
| "A(\($i),\($j)) = \( [$i,$j] | ack )"</syntaxhighlight>
{{out}}
<syntaxhighlight lang="sh"># jq -n -r -f ackermann.jq
A(0,0) = 1
A(0,1) = 2
Line 4,995:
A(4,0) = 13</syntaxhighlight>
===With Memoization and Optimization===
<syntaxhighlight lang="jq"># input: [m,n, cache]
# output [value, updatedCache]
def ack:
Line 5,025:
def A(m;n): [m,n,{}] | ack | .[0];
</syntaxhighlight>
'''Example:'''<syntaxhighlight lang="jq">A(4,1)</syntaxhighlight>
{{out}}
<syntaxhighlight lang="sh">65533</syntaxhighlight>
=={{header|Jsish}}==
From javascript entry.
<syntaxhighlight lang="javascript">/* Ackermann function, in Jsish */
function ack(m, n) {
Line 5,068:
=={{header|Julia}}==
<syntaxhighlight lang="julia">function ack(m,n)
if m == 0
return n + 1
Line 5,079:
'''One-liner:'''
<syntaxhighlight lang="julia">ack2(m::Integer, n::Integer) = m == 0 ? n + 1 : n == 0 ? ack2(m - 1, 1) : ack2(m - 1, ack2(m, n - 1))</syntaxhighlight>
'''Using memoization''', [https://github.com/simonster/Memoize.jl source]:
<syntaxhighlight lang="julia">using Memoize
@memoize ack3(m::Integer, n::Integer) = m == 0 ? n + 1 : n == 0 ? ack3(m - 1, 1) : ack3(m - 1, ack3(m, n - 1))</syntaxhighlight>
Line 5,096:
=={{header|K}}==
See [https://github.com/kevinlawler/kona/wiki the K wiki]
<syntaxhighlight lang="k">ack:{:[0=x;y+1;0=y;_f[x-1;1];_f[x-1;_f[x;y-1]]]}
ack[2;2]</syntaxhighlight>
=={{header|Kdf9 Usercode}}==
<syntaxhighlight lang="kdf9 usercode">V6; W0;
YS26000;
RESTART; J999; J999;
Line 5,152:
=={{header|Klingphix}}==
<syntaxhighlight lang="text">:ack
%n !n %m !m
Line 5,171:
=={{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)</syntaxhighlight>
=={{header|Kotlin}}==
<syntaxhighlight lang="scala">
tailrec fun A(m: Long, n: Long): Long {
require(m >= 0L) { "m must not be negative" }
Line 5,213:
=={{header|Lambdatalk}}==
<syntaxhighlight lang=
{def ack
{lambda {:m :n}
Line 5,239:
=={{header|Lasso}}==
<syntaxhighlight lang="lasso">#!/usr/bin/lasso9
define ackermann(m::integer, n::integer) => {
Line 5,273:
=={{header|LFE}}==
<syntaxhighlight lang="lisp">(defun ackermann
((0 n) (+ n 1))
((m 0) (ackermann (- m 1) 1))
Line 5,279:
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">Print Ackermann(1, 2)
Function Ackermann(m, n)
Line 5,295:
=={{header|LiveCode}}==
<syntaxhighlight lang=
switch
Case m = 0
Line 5,307:
=={{header|Logo}}==
<syntaxhighlight lang="logo">to ack :i :j
if :i = 0 [output :j+1]
if :j = 0 [output ack :i-1 1]
Line 5,314:
=={{header|Logtalk}}==
<syntaxhighlight lang="logtalk">ack(0, N, V) :-
!,
V is N + 1.
Line 5,329:
=={{header|LOLCODE}}==
{{trans|C}}
<syntaxhighlight lang=
HOW IZ I ackermann YR m AN YR n
Line 5,353:
=={{header|Lua}}==
<syntaxhighlight lang="lua">function ack(M,N)
if M == 0 then return N + 1 end
if N == 0 then return ack(M-1,1) end
Line 5,360:
=== Stackless iterative solution with multiple precision, fast ===
<syntaxhighlight lang="lua">
#!/usr/bin/env luajit
local gmp = require 'gmp' ('libgmp')
Line 5,415:
=={{header|Lucid}}==
<syntaxhighlight lang="lucid">ack(m,n)
where
ack(m,n) = if m eq 0 then n+1
Line 5,424:
=={{header|Luck}}==
<syntaxhighlight lang="luck">function ackermann(m: int, n: int): int = (
if m==0 then n+1
else if n==0 then ackermann(m-1,1)
Line 5,431:
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang=
Module Checkit {
Def ackermann(m,n) =If(m=0-> n+1, If(n=0-> ackermann(m-1,1), ackermann(m-1,ackermann(m,n-1))))
Line 5,449:
=={{header|M4}}==
<syntaxhighlight lang=
ack(3,3)</syntaxhighlight>
{{out}}
Line 5,467:
the arguments to the recursive function via the stack or the global variables. The following program demonstrates this.
<syntaxhighlight lang=
DIMENSION LIST(3000)
SET LIST TO LIST
Line 5,551:
=={{header|Maple}}==
Strictly by the definition given above, we can code this as follows.
<syntaxhighlight lang=
Ackermann := proc( m :: nonnegint, n :: nonnegint )
option remember; # optional automatic memoization
Line 5,563:
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=
Ackermann := proc( m :: nonnegint, n :: nonnegint )
option remember; # optional automatic memoization
Line 5,587:
To compute Ackermann( 1, i ) for i from 1 to 10 use
<syntaxhighlight lang=
> 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=
> 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=
> length( Ackermann( 4, 2 ) );
19729
Line 5,608:
This particular version of Ackermann's function was created in Mathcad Prime Express 7.0, a free version of Mathcad Prime 7.0 with restrictions (such as no programming or symbolics). All Prime Express numbers are complex. There is a recursion depth limit of about 4,500.
<syntaxhighlight lang=
The worksheet also contains an explictly-calculated version of Ackermann's function that calls the tetration function n<sub>a</sub>.
Line 5,623:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
Two possible implementations would be:
<syntaxhighlight lang=
Ackermann1[m_,n_]:=
If[m==0,n+1,
Line 5,636:
Note that the second implementation is quite a bit faster, as doing 'if' comparisons is slower than the built-in pattern matching algorithms.
Examples:
<syntaxhighlight lang=
gives back:
<syntaxhighlight lang=
Ackermann2[1,2] = 4
Ackermann2[1,3] = 5
Line 5,663:
Ackermann2[3,8] = 2045</syntaxhighlight>
If we would like to calculate Ackermann[4,1] or Ackermann[4,2] we have to optimize a little bit:
<syntaxhighlight lang=
$RecursionLimit=Infinity;
Ackermann3[0,n_]:=n+1;
Line 5,673:
Now computing Ackermann[4,1] and Ackermann[4,2] can be done quickly (<0.01 sec):
Examples 2:
<syntaxhighlight lang=
Ackermann3[4, 2]</syntaxhighlight>
gives back:
<div style="width:full;overflow:scroll"><syntaxhighlight lang=
2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880........699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156733</syntaxhighlight></div>
Ackermann[4,2] has 19729 digits, several thousands of digits omitted in the result above for obvious reasons. Ackermann[5,0] can be computed also quite fast, and is equal to 65533.
Line 5,682:
=={{header|MATLAB}}==
<syntaxhighlight lang=
if m == 0
A = n+1;
Line 5,693:
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">ackermann(m, n) := if integerp(m) and integerp(n) then ackermann[m, n] else 'ackermann(m, n)$
ackermann[m, n] := if m = 0 then n + 1
Line 5,711:
=={{header|MAXScript}}==
Use with caution. Will cause a stack overflow for m > 3.
<syntaxhighlight lang="maxscript">fn ackermann m n =
(
if m == 0 then
Line 5,729:
=={{header|Mercury}}==
This is the Ackermann function with some (obvious) elements elided. The <code>ack/3</code> predicate is implemented in terms of the <code>ack/2</code> function. The <code>ack/2</code> function is implemented in terms of the <code>ack/3</code> predicate. This makes the code both more concise and easier to follow than would otherwise be the case. The <code>integer</code> type is used instead of <code>int</code> because the problem statement stipulates the use of bignum integers if possible.
<syntaxhighlight lang="mercury">:- func ack(integer, integer) = integer.
ack(M, N) = R :- ack(M, N, R).
Line 5,742:
=={{header|min}}==
{{works with|min|0.19.3}}
<syntaxhighlight lang="min">(
:n :m
(
Line 5,753:
=={{header|MiniScript}}==
<syntaxhighlight lang=
if m == 0 then return n+1
if n == 0 then return ackermann(m - 1, 1)
Line 5,766:
=={{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
Line 5,774:
ML/I loves recursion, but runs out of its default amount of storage with larger numbers than those tested here!
===Program===
<syntaxhighlight lang=
"" Ackermann function
"" Will overflow when it reaches implementation-defined signed integer limit
Line 5,808:
a(4,0) => ACK(4,0)</syntaxhighlight>
{{out}}
<syntaxhighlight lang=
a(0,1) => 2
a(0,2) => 3
Line 5,829:
=={{header|mLite}}==
<syntaxhighlight lang="haskell">fun ackermann( 0, n ) = n + 1
| ( m, 0 ) = ackermann( m - 1, 1 )
| ( m, n ) = ackermann( m - 1, ackermann(m, n - 1) )</syntaxhighlight>
Test code providing tuples from (0,0) to (3,8)
<syntaxhighlight lang="haskell">fun jota x = map (fn x = x-1) ` iota x
fun test_tuples (x, y) = append_map (fn a = map (fn b = (b, a)) ` jota x) ` jota y
Line 5,842:
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE ackerman;
IMPORT ASCII, NumConv, InOut;
Line 5,883:
=={{header|Modula-3}}==
The type CARDINAL is defined in Modula-3 as [0..LAST(INTEGER)], in other words, it can hold all positive integers.
<syntaxhighlight lang="modula3">MODULE Ack EXPORTS Main;
FROM IO IMPORT Put;
Line 5,914:
=={{header|MUMPS}}==
<syntaxhighlight lang=
If m=0 Quit n+1
If m>0,n=0 Quit $$Ackermann(m-1,1)
Line 5,925:
=={{header|Neko}}==
<syntaxhighlight lang=
Ackermann recursion, in Neko
Tectonics:
Line 5,970:
=={{header|Nemerle}}==
In Nemerle, we can state the Ackermann function as a lambda. By using pattern-matching, our definition strongly resembles the mathematical notation.
<syntaxhighlight lang=
using System;
using Nemerle.IO;
Line 5,993:
</syntaxhighlight>
A terser version using implicit <code>match</code> (which doesn't use the alias <code>A</code> internally):
<syntaxhighlight lang=
def ackermann(m, n) {
| (0, n) => n + 1
Line 6,002:
</syntaxhighlight>
Or, if we were set on using the <code>A</code> notation, we could do this:
<syntaxhighlight lang=
def ackermann = {
def A(m, n) {
Line 6,015:
=={{header|NetRexx}}==
<syntaxhighlight lang=
options replace format comments java crossref symbols binary
Line 6,042:
=={{header|NewLISP}}==
<syntaxhighlight lang="newlisp">
#! /usr/local/bin/newlisp
Line 6,058:
=={{header|Nim}}==
<syntaxhighlight lang="nim">from strutils import parseInt
proc ackermann(m, n: int64): int64 =
Line 6,089:
Source: [https://github.com/nitlang/nit/blob/master/examples/rosettacode/ackermann_function.nit the official Nit’s repository].
<syntaxhighlight lang="nit"># Task: Ackermann function
#
# A simple straightforward recursive implementation.
Line 6,145:
=={{header|Oberon-2}}==
<syntaxhighlight lang="oberon2">MODULE ackerman;
IMPORT Out;
Line 6,174:
=={{header|Objeck}}==
{{trans|C#|C sharp}}
<syntaxhighlight lang="objeck">class Ackermann {
function : Main(args : String[]) ~ Nil {
for(m := 0; m <= 3; ++m;) {
Line 6,228:
=={{header|OCaml}}==
<syntaxhighlight lang="ocaml">let rec a m n =
if m=0 then (n+1) else
if n=0 then (a (m-1) 1) else
(a (m-1) (a m (n-1)))</syntaxhighlight>
or:
<syntaxhighlight lang="ocaml">let rec a = function
| 0, n -> (n+1)
| m, 0 -> a(m-1, 1)
| m, n -> a(m-1, a(m, n-1))</syntaxhighlight>
with memoization using an hash-table:
<syntaxhighlight lang="ocaml">let h = Hashtbl.create 4001
let a m n =
Line 6,247:
(res)</syntaxhighlight>
taking advantage of the memoization we start calling small values of '''m''' and '''n''' in order to reduce the recursion call stack:
<syntaxhighlight lang="ocaml">let a m n =
for _m = 0 to m do
for _n = 0 to n do
Line 6,256:
=== Arbitrary precision ===
With arbitrary-precision integers ([http://caml.inria.fr/pub/docs/manual-ocaml/libref/Big_int.html Big_int module]):
<syntaxhighlight lang="ocaml">open Big_int
let one = unit_big_int
let zero = zero_big_int
Line 6,271:
=== Tail-Recursive ===
Here is a [[:Category:Recursion|tail-recursive]] version:
<syntaxhighlight lang="ocaml">let rec find_option h v =
try Some(Hashtbl.find h v)
with Not_found -> None
Line 6,302:
let a = a (Hashtbl.create 42 (* arbitrary *) ) [] [] ;;</syntaxhighlight>
This one uses the arbitrary precision, the tail-recursion, and the optimisation explain on the Wikipedia page about <tt>(m,n) = (3,_)</tt>.
<syntaxhighlight lang="ocaml">open Big_int
let one = unit_big_int
let zero = zero_big_int
Line 6,383:
=={{header|Octave}}==
<syntaxhighlight lang="octave">function r = ackerman(m, n)
if ( m == 0 )
r = n + 1;
Line 6,398:
=={{header|Oforth}}==
<syntaxhighlight lang=
m ifZero: [ n 1+ return ]
m 1- n ifZero: [ 1 ] else: [ A( m, n 1- ) ] A
Line 6,404:
=={{header|Ol}}==
<syntaxhighlight lang="scheme">
; simple version
(define (A m n)
Line 6,450:
=={{header|OOC}}==
<syntaxhighlight lang="ooc">
ack: func (m: Int, n: Int) -> Int {
if (m == 0) {
Line 6,471:
=={{header|ooRexx}}==
<syntaxhighlight lang=
loop m = 0 to 3
loop n = 0 to 6
Line 6,519:
=={{header|Order}}==
<syntaxhighlight lang="c">#include <order/interpreter.h>
#define ORDER_PP_DEF_8ack ORDER_PP_FN( \
Line 6,531:
=={{header|Oz}}==
Oz has arbitrary precision integers.
<syntaxhighlight lang="oz">declare
fun {Ack M N}
Line 6,546:
=={{header|PARI/GP}}==
Naive implementation.
<syntaxhighlight lang="parigp">A(m,n)={
if(m,
if(n,
Line 6,559:
=={{header|Pascal}}==
<syntaxhighlight lang="pascal">Program Ackerman;
function ackermann(m, n: Integer) : Integer;
Line 6,582:
=={{header|Perl}}==
We memoize calls to ''A'' to make ''A''(2, ''n'') and ''A''(3, ''n'') feasible for larger values of ''n''.
<syntaxhighlight lang="perl">{
my @memo;
sub A {
Line 6,597:
An implementation using the conditional statements 'if', 'elsif' and 'else':
<syntaxhighlight lang="perl">sub A {
my ($m, $n) = @_;
if ($m == 0) { $n + 1 }
Line 6,605:
An implementation using ternary chaining:
<syntaxhighlight lang="perl">sub A {
my ($m, $n) = @_;
$m == 0 ? $n + 1 :
Line 6,613:
Adding memoization and extra terms:
<syntaxhighlight lang="perl">use Memoize; memoize('ack2');
use bigint try=>"GMP";
Line 6,635:
An optimized version, which uses <code>@_</code> as a stack,
instead of recursion. Very fast.
<syntaxhighlight lang=
use warnings;
use Math::BigInt;
Line 6,674:
=={{header|Phix}}==
=== native version ===
<!--<syntaxhighlight lang=
<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,725:
{{trans|Go}}
{{libheader|Phix/mpfr}}
<!--<syntaxhighlight lang=
<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,828:
=={{header|Phixmonti}}==
<syntaxhighlight lang=
var n var m
Line 6,845:
=={{header|PHP}}==
<syntaxhighlight lang="php">function ackermann( $m , $n )
{
if ( $m==0 )
Line 6,862:
=={{header|Picat}}==
<syntaxhighlight lang=
foreach(M in 0..3)
println([m=M,[a(M,N) : N in 0..16]])
Line 6,921:
=={{header|PicoLisp}}==
<syntaxhighlight lang=
(cond
((=0 X) (inc Y))
Line 7,294:
=={{header|Pike}}==
<syntaxhighlight lang="pike">int main(){
write(ackermann(3,4) + "\n");
}
Line 7,309:
=={{header|PL/I}}==
<syntaxhighlight lang=
declare (m, n) fixed (30);
if m = 0 then return (n+1);
Line 7,318:
=={{header|PL/SQL}}==
<syntaxhighlight lang=
FUNCTION ackermann(pi_m IN NUMBER,
Line 7,373:
=={{header|PostScript}}==
<syntaxhighlight lang="postscript">/ackermann{
/n exch def
/m exch def %PostScript takes arguments in the reverse order as specified in the function definition
Line 7,388:
}def</syntaxhighlight>
{{libheader|initlib}}
<syntaxhighlight lang="postscript">/A {
[/.m /.n] let
{
Line 7,398:
=={{header|Potion}}==
<syntaxhighlight lang=
if (m == 0): n + 1
. elsif (n == 0): ack(m - 1, 1)
Line 7,411:
=={{header|PowerBASIC}}==
<syntaxhighlight lang="powerbasic">FUNCTION PBMAIN () AS LONG
DIM m AS QUAD, n AS QUAD
Line 7,432:
=={{header|PowerShell}}==
{{trans|PHP}}
<syntaxhighlight lang="powershell">function ackermann ([long] $m, [long] $n) {
if ($m -eq 0) {
return $n + 1
Line 7,444:
}</syntaxhighlight>
Building an example table (takes a while to compute, though, especially for the last three numbers; also it fails with the last line in Powershell v1 since the maximum recursion depth is only 100 there):
<syntaxhighlight lang="powershell">foreach ($m in 0..3) {
foreach ($n in 0..6) {
Write-Host -NoNewline ("{0,5}" -f (ackermann $m $n))
Line 7,457:
===A More "PowerShelly" Way===
<syntaxhighlight lang=
function Get-Ackermann ([int64]$m, [int64]$n)
{
Line 7,474:
</syntaxhighlight>
Save the result to an array (for possible future use?), then display it using the <code>Format-Wide</code> cmdlet:
<syntaxhighlight lang=
$ackermann = 0..3 | ForEach-Object {$m = $_; 0..6 | ForEach-Object {Get-Ackermann $m $_}}
Line 7,488:
=={{header|Processing}}==
<syntaxhighlight lang="java">int ackermann(int m, int n) {
if (m == 0)
return n + 1;
Line 7,520:
m = 5 it throws 'maximum recursion depth exceeded'
<syntaxhighlight lang="python">from __future__ import print_function
def setup():
Line 7,541:
Processing.R may exceed its stack depth at ~n==6 and returns null.
<syntaxhighlight lang="r">setup <- function() {
for (m in 0:3) {
for (n in 0:4) {
Line 7,568:
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<syntaxhighlight lang="prolog">:- table ack/3. % memoization reduces the execution time of ack(4,1,X) from several
% minutes to about one second on a typical desktop computer.
ack(0, N, Ans) :- Ans is N+1.
Line 7,575:
=={{header|Pure}}==
<syntaxhighlight lang="pure">A 0 n = n+1;
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}}==
<syntaxhighlight lang=
#N canvas 741 265 450 436 10;
#X obj 83 111 t b l;
Line 7,628:
=={{header|PureBasic}}==
<syntaxhighlight lang=
If m = 0
ProcedureReturn n + 1
Line 7,641:
=={{header|Purity}}==
<syntaxhighlight lang=
data Ackermann = FoldNat <const Succ, Iter></syntaxhighlight>
Line 7,647:
===Python: Explicitly recursive===
{{works with|Python|2.5}}
<syntaxhighlight lang="python">def ack1(M, N):
return (N + 1) if M == 0 else (
ack1(M-1, 1) if N == 0 else ack1(M-1, ack1(M, N-1)))</syntaxhighlight>
Another version:
<syntaxhighlight lang="python">from functools import lru_cache
@lru_cache(None)
Line 7,662:
return ack2(M - 1, ack2(M, N - 1))</syntaxhighlight>
{{out|Example of use}}
<syntaxhighlight lang="python">>>> import sys
>>> sys.setrecursionlimit(3000)
>>> ack1(0,0)
Line 7,673:
125</syntaxhighlight>
From the Mathematica ack3 example:
<syntaxhighlight lang="python">def ack2(M, N):
return (N + 1) if M == 0 else (
(N + 2) if M == 1 else (
Line 7,684:
The heading is more correct than saying the following is iterative as an explicit stack is used to replace explicit recursive function calls. I don't think this is what Comp. Sci. professors mean by iterative.
<syntaxhighlight lang="python">from collections import deque
def ack_ix(m, n):
Line 7,733:
=={{header|Quackery}}==
<syntaxhighlight lang=
[ over 0 = iff
[ nip 1 + ] done
Line 7,747:
=={{header|R}}==
<syntaxhighlight lang=
if ( m == 0 ) {
n+1
Line 7,756:
}
}</syntaxhighlight>
<syntaxhighlight lang=
print(ackermann(i, 4))
}</syntaxhighlight>
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
(define (ackermann m n)
Line 7,773:
{{works with|Rakudo|2018.03}}
<syntaxhighlight lang=
if $m == 0 { $n + 1 }
elsif $n == 0 { A($m - 1, 1) }
Line 7,779:
}</syntaxhighlight>
An implementation using multiple dispatch:
<syntaxhighlight lang=
multi sub A(Int $m, 0 ) { A($m - 1, 1) }
multi sub A(Int $m, Int $n) { A($m - 1, A($m, $n - 1)) }</syntaxhighlight>
Line 7,785:
Here's a caching version of that, written in the sigilless style, with liberal use of Unicode, and the extra optimizing terms to make A(4,2) possible:
<syntaxhighlight lang=
multi A(0, Int \𝑛) { 𝑛 + 1 }
Line 7,812:
=={{header|ReScript}}==
<syntaxhighlight lang=
let _n = Sys.argv[3]
Line 7,839:
=={{header|REXX}}==
===no optimization===
<syntaxhighlight lang="rexx">/*REXX program calculates and displays some values for the Ackermann function. */
/*╔════════════════════════════════════════════════════════════════════════╗
║ Note: the Ackermann function (as implemented here) utilizes deep ║
Line 7,944:
===optimized for m ≤ 2===
<syntaxhighlight lang="rexx">/*REXX program calculates and displays some values for the Ackermann function. */
high=24
do j=0 to 3; say
Line 8,048:
<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.
<syntaxhighlight lang="rexx">/*REXX program calculates and displays some values for the Ackermann function. */
numeric digits 100 /*use up to 100 decimal digit integers.*/
/*╔═════════════════════════════════════════════════════════════╗
Line 8,171:
=={{header|Ring}}==
{{trans|C#}}
<syntaxhighlight lang="ring">for m = 0 to 3
for n = 0 to 4
see "Ackermann(" + m + ", " + n + ") = " + Ackermann(m, n) + nl
Line 8,214:
=={{header|Risc-V}}==
the basic recursive function, because memorization and other improvements would blow the clarity.
<syntaxhighlight lang=
beqz a1, npe #case m = 0
beqz a2, mme #case m > 0 & n = 0
Line 8,245:
=={{header|Ruby}}==
{{trans|Ada}}
<syntaxhighlight lang="ruby">def ack(m, n)
if m == 0
n + 1
Line 8,255:
end</syntaxhighlight>
Example:
<syntaxhighlight lang="ruby">(0..3).each do |m|
puts (0..6).map { |n| ack(m, n) }.join(' ')
end</syntaxhighlight>
Line 8,265:
=={{header|Run BASIC}}==
<syntaxhighlight lang="runbasic">print ackermann(1, 2)
function ackermann(m, n)
Line 8,274:
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn ack(m: isize, n: isize) -> isize {
if m == 0 {
n + 1
Line 8,292:
Or:
<syntaxhighlight lang="rust">
fn ack(m: u64, n: u64) -> u64 {
match (m, n) {
Line 8,303:
=={{header|Sather}}==
<syntaxhighlight lang="sather">class MAIN is
ackermann(m, n:INT):INT
Line 8,323:
end;</syntaxhighlight>
Instead of <code>INT</code>, the class <code>INTI</code> could be used, even though we need to use a workaround since in the GNU Sather v1.2.3 compiler the INTI literals are not implemented yet.
<syntaxhighlight lang="sather">class MAIN is
ackermann(m, n:INTI):INTI is
Line 8,345:
=={{header|Scala}}==
<syntaxhighlight lang="scala">def ack(m: BigInt, n: BigInt): BigInt = {
if (m==0) n+1
else if (n==0) ack(m-1, 1)
Line 8,356:
</pre>
Memoized version using a mutable hash map:
<syntaxhighlight lang="scala">val ackMap = new mutable.HashMap[(BigInt,BigInt),BigInt]
def ackMemo(m: BigInt, n: BigInt): BigInt = {
ackMap.getOrElseUpdate((m,n), ack(m,n))
Line 8,362:
=={{header|Scheme}}==
<syntaxhighlight lang="scheme">(define (A m n)
(cond
((= m 0) (+ n 1))
Line 8,370:
An improved solution that uses a lazy data structure, streams, and defines [[Knuth up-arrow]]s to calculate iterative exponentiation:
<syntaxhighlight lang="scheme">(define (A m n)
(letrec ((A-stream
(cons-stream
Line 8,401:
=={{header|Scilab}}==
<syntaxhighlight lang="text">clear
function acker=ackermann(m,n)
global calls
Line 8,455:
=={{header|Seed7}}==
<syntaxhighlight lang="seed7">const func integer: ackermann (in integer: m, in integer: n) is func
result
var integer: result is 0;
Line 8,470:
=={{header|SETL}}==
<syntaxhighlight lang=
(for m in [0..3])
Line 8,483:
=={{header|Shen}}==
<syntaxhighlight lang="shen">(define ack
0 N -> (+ N 1)
M 0 -> (ack (- M 1) 1)
Line 8,490:
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func A(m, n) {
m == 0 ? (n + 1)
: (n == 0 ? (A(m - 1, 1))
Line 8,497:
Alternatively, using multiple dispatch:
<syntaxhighlight lang="ruby">func A((0), n) { n + 1 }
func A(m, (0)) { A(m - 1, 1) }
func A(m, n) { A(m-1, A(m, n-1)) }</syntaxhighlight>
Calling the function:
<syntaxhighlight lang="ruby">say A(3, 2); # prints: 29</syntaxhighlight>
=={{header|Simula}}==
as modified by R. Péter and R. Robinson:
<syntaxhighlight lang=
INTEGER procedure
Ackermann(g, p); SHORT INTEGER g, p;
Line 8,530:
=={{header|Slate}}==
<syntaxhighlight lang="slate">m@(Integer traits) ackermann: n@(Integer traits)
[
m isZero
Line 8,541:
=={{header|Smalltalk}}==
<syntaxhighlight lang="smalltalk">|ackermann|
ackermann := [ :n :m |
(n = 0) ifTrue: [ (m + 1) ]
Line 8,558:
=={{header|SmileBASIC}}==
<syntaxhighlight lang="smilebasic">DEF ACK(M,N)
IF M==0 THEN
RETURN N+1
Line 8,571:
{{works with|Macro Spitbol}}
Both Snobol4+ and CSnobol stack overflow, at ack(3,3) and ack(3,4), respectively.
<syntaxhighlight lang=
ack ack = eq(m,0) n + 1 :s(return)
ack = eq(n,0) ack(m - 1,1) :s(return)
Line 8,590:
=={{header|SNUSP}}==
<syntaxhighlight lang="snusp"> /==!/==atoi=@@@-@-----#
| | Ackermann function
| | /=========\!==\!====\ recursion:
Line 8,606:
=={{header|SPAD}}==
{{works with|FriCAS, OpenAxiom, Axiom}}
<syntaxhighlight lang=
NNI ==> NonNegativeInteger
Line 8,636:
{{works with|Db2 LUW}} version 9.7 or higher.
With SQL PL:
<syntaxhighlight lang="sql pl">
--#SET TERMINATOR @
Line 8,719:
=={{header|Standard ML}}==
<syntaxhighlight lang="sml">fun a (0, n) = n+1
| a (m, 0) = a (m-1, 1)
| a (m, n) = a (m-1, a (m, n-1))</syntaxhighlight>
=={{header|Stata}}==
<syntaxhighlight lang="stata">mata
function ackermann(m,n) {
if (m==0) {
Line 8,743:
=={{header|Swift}}==
<syntaxhighlight lang="swift">func ackerman(m:Int, n:Int) -> Int {
if m == 0 {
return n+1
Line 8,756:
===Simple===
{{trans|Ruby}}
<syntaxhighlight lang="tcl">proc ack {m n} {
if {$m == 0} {
expr {$n + 1}
Line 8,767:
===With Tail Recursion===
With Tcl 8.6, this version is preferred (though the language supports tailcall optimization, it does not apply it automatically in order to preserve stack frame semantics):
<syntaxhighlight lang="tcl">proc ack {m n} {
if {$m == 0} {
expr {$n + 1}
Line 8,779:
If we want to explore the higher reaches of the world of Ackermann's function, we need techniques to really cut the amount of computation being done.
{{works with|Tcl|8.6}}
<syntaxhighlight lang="tcl">package require Tcl 8.6
# A memoization engine, from http://wiki.tcl.tk/18152
Line 8,840:
This program assumes the variables N and M are the arguments of the function, and that the list L1 is empty. It stores the result in the system variable ANS. (Program names can be no longer than 8 characters, so I had to truncate the function's name.)
<syntaxhighlight lang="ti83b">PROGRAM:ACKERMAN
:If not(M
:Then
Line 8,864:
Here is a handler function that makes the previous function easier to use. (You can name it whatever you want.)
<syntaxhighlight lang="ti83b">PROGRAM:AHANDLER
:0→dim(L1
:Prompt M
Line 8,872:
=={{header|TI-89 BASIC}}==
<syntaxhighlight lang="ti89b">Define A(m,n) = when(m=0, n+1, when(n=0, A(m-1,1), A(m-1, A(m, n-1))))</syntaxhighlight>
=={{header|TorqueScript}}==
<syntaxhighlight lang=
{
if(%m==0)
Line 8,886:
=={{header|TSE SAL}}==
<syntaxhighlight lang=
INTEGER PROC FNMathGetAckermannRecursiveI( INTEGER mI, INTEGER nI )
IF ( mI == 0 )
Line 8,910:
with memoization.
<syntaxhighlight lang="txrlisp">(defmacro defmemofun (name (. args) . body)
(let ((hash (gensym "hash-"))
(argl (gensym "args-"))
Line 8,958:
=={{header|UNIX Shell}}==
{{works with|Bash}}
<syntaxhighlight lang="bash">ack() {
local m=$1
local n=$2
Line 8,970:
}</syntaxhighlight>
Example:
<syntaxhighlight lang="bash">for ((m=0;m<=3;m++)); do
for ((n=0;n<=6;n++)); do
ack $m $n
Line 8,985:
=={{header|Ursala}}==
Anonymous recursion is the usual way of doing things like this.
<syntaxhighlight lang=
#import nat
Line 8,994:
^|R/~& ~&\1+ predecessor@l)</syntaxhighlight>
test program for the first 4 by 7 numbers:
<syntaxhighlight lang=
test = block7 ackermann*K0 iota~~/4 7</syntaxhighlight>
Line 9,007:
=={{header|V}}==
{{trans|Joy}}
<syntaxhighlight lang="v">[ack
[ [pop zero?] [popd succ]
[zero?] [pop pred 1 ack]
Line 9,013:
] when].</syntaxhighlight>
using destructuring view
<syntaxhighlight lang="v">[ack
[ [pop zero?] [ [m n : [n succ]] view i]
[zero?] [ [m n : [m pred 1 ack]] view i]
Line 9,020:
=={{header|Vala}}==
<syntaxhighlight lang="vala">uint64 ackermann(uint64 m, uint64 n) {
if (m == 0) return n + 1;
if (n == 0) return ackermann(m - 1, 1);
Line 9,079:
=={{header|VBA}}==
<syntaxhighlight lang="vb">Private Function Ackermann_function(m As Variant, n As Variant) As Variant
Dim result As Variant
Debug.Assert m >= 0
Line 9,117:
Based on BASIC version. Uncomment all the lines referring to <code>depth</code> and see just how deep the recursion goes.
;Implementation
<syntaxhighlight lang="vb">option explicit
'~ dim depth
function ack(m, n)
Line 9,138:
end function</syntaxhighlight>
;Invocation
<syntaxhighlight lang="vb">wscript.echo ack( 1, 10 )
'~ depth = 0
wscript.echo ack( 2, 1 )
Line 9,153:
{{trans|Rexx}}
{{works with|Visual Basic|VB6 Standard}}
<syntaxhighlight lang="vb">
Option Explicit
Dim calls As Long
Line 9,228:
=={{header|Vlang}}==
<syntaxhighlight lang="go">fn ackermann(m int, n int ) int {
if m == 0 {
return n + 1
Line 9,271:
=={{header|Wart}}==
<syntaxhighlight lang="wart">def (ackermann m n)
(if m=0
n+1
Line 9,280:
=={{header|WDTE}}==
<syntaxhighlight lang=
== m 0 => + n 1;
== n 0 => a (- m 1) 1;
Line 9,287:
=={{header|Wren}}==
<syntaxhighlight lang="ecmascript">// To use recursion definition and declaration must be on separate lines
var Ackermann
Ackermann = Fn.new {|m, n|
Line 9,315:
{{works with|nasm}}
{{works with|windows}}
<syntaxhighlight lang="asm">
section .text
Line 9,348:
=={{header|XLISP}}==
<syntaxhighlight lang="lisp">(defun ackermann (m n)
(cond
((= m 0) (+ n 1))
Line 9,354:
(t (ackermann (- m 1) (ackermann m (- n 1))))))</syntaxhighlight>
Test it:
<syntaxhighlight lang="lisp">(print (ackermann 3 9))</syntaxhighlight>
Output (after a very perceptible pause):
<pre>4093</pre>
That worked well. Test it again:
<syntaxhighlight lang="lisp">(print (ackermann 4 1))</syntaxhighlight>
Output (after another pause):
<pre>Abort: control stack overflow
Line 9,364:
=={{header|XPL0}}==
<syntaxhighlight lang=
func Ackermann(M, N);
Line 9,392:
The following named template calculates the Ackermann function:
<syntaxhighlight lang="xml">
<xsl:template name="ackermann">
<xsl:param name="m"/>
Line 9,425:
Here it is as part of a template
<syntaxhighlight lang="xml">
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="1.0">
Line 9,474:
Which will transform this input
<syntaxhighlight lang="xml">
<?xml version="1.0" ?>
<?xml-stylesheet type="text/xsl" href="ackermann.xslt"?>
Line 9,666:
=={{header|Yabasic}}==
<syntaxhighlight lang=
if M = 0 return N + 1
if N = 0 return ack(M-1,1)
Line 9,677:
What smart code can get. Fast as lightning!
{{trans|Phix}}
<syntaxhighlight lang=
if m=0 then
return n+1
Line 9,707:
=={{header|Yorick}}==
<syntaxhighlight lang="yorick">func ack(m, n) {
if(m == 0)
return n + 1;
Line 9,716:
}</syntaxhighlight>
Example invocation:
<syntaxhighlight lang="yorick">for(m = 0; m <= 3; m++) {
for(n = 0; n <= 6; n++)
write, format="%d ", ack(m, n);
Line 9,727:
5 13 29 61 125 253 509</pre>
{{omit from|LaTeX}}▼
{{omit from|Make}}▼
{{omit from|PlainTeX}}▼
=={{header|Z80 Assembly}}==
This function does 16-bit math. Sjasmplus syntax, CP/M executable.
<syntaxhighlight lang="z80"> OPT --syntax=abf : OUTPUT "ackerman.com"
ORG $100
jr demo_start
Line 9,852 ⟶ 9,849:
Source -> http://ideone.com/53FzPA
Compiled -> http://ideone.com/OlS7zL
<syntaxhighlight lang="zed">(A) m n
comment:
(=) m 0
Line 9,883 ⟶ 9,880:
=={{header|Zig}}==
<syntaxhighlight lang="zig">pub fn ack(m: u64, n: u64) u64 {
if (m == 0) return n + 1;
if (n == 0) return ack(m - 1, 1);
Line 9,908 ⟶ 9,905:
=={{header|ZX Spectrum Basic}}==
{{trans|BASIC256}}
<syntaxhighlight lang="zxbasic">10 DIM s(2000,3)
20 LET s(1,1)=3: REM M
30 LET s(1,2)=7: REM N
Line 9,929 ⟶ 9,926:
{{out}}
<pre>A(3,7) = 1021</pre>
▲{{omit from|LaTeX}}
▲{{omit from|Make}}
▲{{omit from|PlainTeX}}
| |||