# Ackermann function (OCaml)

### From LiteratePrograms

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

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

This page explains how to implement the **Ackermann function** in OCaml.
For this example, we will be using OCaml's "function" syntax for defining functions. We choose this style as it most closely resembles the problem definition.

## Source code

We begin the code by defining a recursive value named `ackermann`

and indicate that this value will be a function

<<ackermann.ml>>=letrecackermann =function

First, we add a case to catch the cases when either argument is negative, because the Ackermann function is only defined for non-negative integers. While that may be fine in math, when it comes to programming, one should be aware that invalid inputs may be used. These cases should be caught and handled. Here we raise an exception with an informative message that can be handled by the caller of `ackermann`

.

<<ackermann.ml>>=| m,nwhenm < 0 || n < 0 -> invalid_arg "Ackermann's function is only defined over the non-negative integers"

We then use pattern matching on the function's parameter to handle the three cases given in the definition of the Ackermann function. The first case we handle is the base case of the recursion, when m = 0. Note that because of the way we are doing the pattern matching, our function takes a single tuple as input.

<<ackermann.ml>>=| 0,n -> n+1

For the second case, when m > 0 and n = 0, we make a simple recursive call to the `ackermann`

function.

<<ackermann.ml>>=| m,0 -> ackermann(m-1,1)

In the third case, when m, n > 0, a pair of recursive calls are made. The first call determines the new value of n, and the second call which uses this new value along with the new value of m (a simple decrement).

<<ackermann.ml>>=| m,n -> ackermann(m-1,ackermann(m,n-1))

## Execution result

In this section we show the output of a few applications of `ackermann`

:

# ackermann(0,0);; - : int = 1 # ackermann(1,1);; - : int = 3 # ackermann(2,13);; - : int = 29 # ackermann(3,1);; - : int = 13 # ackermann(3,7);; - : int = 1021 # ackermann(3,9);; - : int = 4093 # ackermann(-1,9);; Exception: Invalid_argument "Ackermann's function is only defined over the non-negative integers".

Note, however, that due to the tremendous growth rate of Ackermann's function, the number of recursive calls to `ackermann`

quickly becomes too much to handle, even for relatively small values of m and n.

# ackermann(4,1);; Stack overflow during evaluation(looping recursion?).

We can resolve this problem in the usual way in OCaml which is to rewrite the code in a tail-recursive way:

letrecfind_option h v =trySome(Hashtbl.find h v)withNot_found -> Noneletreca bounds caller todo m n =matchm, nwith| 0, n ->letr =(n+1)in(matchtodowith|[]-> r |(m,n)::todo -> List.iter(funk ->ifnot(Hashtbl.mem bounds k)thenHashtbl.add bounds k r)caller; a bounds[]todo m n)| m, 0 -> a bounds caller todo(m-1)1 | m, n ->matchfind_option bounds(m, n-1)with| Some a_rec ->letcaller =(m,n)::callerina bounds caller todo(m-1)a_rec | None ->lettodo =(m,n)::todoandcaller =[(m, n-1)]ina bounds caller todo m(n-1)leta = a(Hashtbl.create 42 (* arbitrary *))[][];;

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

openBig_intletone = unit_big_intletzero = zero_big_intletsucc = succ_big_intletpred = pred_big_intletadd = add_big_intletsub = sub_big_intleteq = eq_big_intletthree = succ(succ one)letpower = power_int_positive_big_intleteq2(a1,a2)(b1,b2)=(eq a1 b1)&&(eq a2 b2)moduleH = Hashtbl.Make(structtypet = Big_int.big_int * Big_int.big_intletequal = eq2lethash(x,y)= Hashtbl.hash(Big_int.string_of_big_int x ^ "," ^ Big_int.string_of_big_int y)(* probably not a very good hash function *)end)letrecfind_option h v =trySome(H.find h v)withNot_found -> Noneletreca bounds caller todo m n =letmay_tail r =letk =(m,n)inmatchtodowith|[]-> r |(m,n)::todo -> List.iter(funk ->ifnot(H.mem bounds k)thenH.add bounds k r)(k::caller); a bounds[]todo m ninmatchm, nwith| m, nwheneq m zero ->letr =(succ n)inmay_tail r | m, nwheneq n zero ->letcaller =(m,n)::callerina bounds caller todo(pred m)one | m, nwheneq m three ->letr = sub(power 2(add n three))threeinmay_tail r | m, n ->matchfind_option bounds(m, pred n)with| Some a_rec ->letcaller =(m,n)::callerina bounds caller todo(pred m)a_rec | None ->lettodo =(m,n)::todoinletcaller =[(m, pred n)]ina bounds caller todo m(pred n)leta = a(H.create 42 (* arbitrary *))[][];;

We can use this last version this way:

let()=letm, n =trybig_int_of_string Sys.argv.(1), big_int_of_string Sys.argv.(2)with_ -> Printf.eprintf "usage: %s <int> <int>\n" Sys.argv.(0); exit 1inletr = a m ninPrintf.printf "(a %s %s) = %s\n"(string_of_big_int m)(string_of_big_int n)(string_of_big_int r); ;;

compile with:

ocamlopt -o acker nums.cmxa acker.ml