Ackermann function (Erlang)

From LiteratePrograms

Jump to: navigation, search
Other implementations: Alice ML | C | Erlang | Forth | Haskell | Java | OCaml | Prolog | Python

The Ackermann function or Ackermann-Péter function is defined recursively for non-negative integers m and n as follows:

A(m, n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases}

In the theory of computation, the Ackermann function is a simple example of a recursive function that is not primitively recursive. Note that this function grows very quickly -- even A(4, 3) cannot be feasibly computed on ordinary computers.


Using recursion and pattern matching this function is extreamly easy to impliment in Erlang. 

<<ackermann function>>=
ackermann(0, N) ->
    N + 1;
ackermann(M, 0) ->
    ackermann(M-1, 1);
ackermann(M, N) ->
    ackermann(M-1, ackermann(M, N - 1)).

Then all that is needed is some glue code to allow the function to be accessed as a script. 

<<ackermann>>=
#!/usr/bin/env escript

main([A, P]) ->
    io:fwrite("~p~n", [xackermann(string:to_integer(A), string:to_integer(P))]).

xackermann({A, _}, {B, _}) ->
    ackermann(A, B).

ackermann function
Download code
Retrieved from "http://en.literateprograms.org/Ackermann_function_%28Erlang%29"
Personal tools