5 Recursion

5.6 Partial Recursive Functions

We've covered primitive recursive functions in the previous section; now we'll take a brief look at what are called "partial recursive functions". These are functions that provide an output for given input but which may not be defined for every possible input.

Partial recursive functions are also referred to as "computable functions" and can be defined using Turing machines or the λ-calculus (among others). In fact, an equivalent definition of partial recursive function is actually a function that can be computed by a Turing machine.

5.7 Total Recursive Functions

As opposed to a partial recursive function, a total recursive function is one that is defined for all possible function inputs. Every primitive recursive function is total recursive. There are, however, total recursive functions that are not primitive recursive. The Ackermann function is one such.

5.7.1 The Ackermann Function

The Ackermann function is one of the simplest and earliest-discovered examples of a total recursive function that is not primitive recursive. The variant of the function that we present below is the two-variable version developed by Rózsa Péter and Raphael Robinson (the original was more verbose and with three variables).

Here is the function in LFE

(defun ackermann
  ((0 n) (+ n 1))
  ((m 0) (ackermann (- m 1) 1))
  ((m n) (ackermann (- m 1) (ackermann m (- n 1)))))

As we can see, this function quite clearly calls itself ;-)

Here's some example usage:

> (c "prf")
#(module prf)
> (prf:ackermann 0 0)
1
> (prf:ackermann 0 1)
2
> (prf:ackermann 1 0)
2
> (prf:ackermann 1 1)
3
> (prf:ackermann 1 2)
4
> (prf:ackermann 2 2)
7
> (prf:ackermann 2 4)
11
> (prf:ackermann 4 1)
65533
>