[Overview] [Previous]
[Next]

# Composition and Recursion, Revisited

Just as you can have lots of minor variations on a Turing machine that all turn out to
be equivalent, so too you can have lots of minor variations on the definition of primitive
recursive functions. Here I'm going to try to highlight the important aspects of the
definitions.

## Composition

The important thing here is that each function be defined *only in terms of
previously defined functions.* This restriction prevents unwanted kinds of recursion
from creeping in, such as indirect recursion (A calls B, B calls C, C calls A).

Many programming languages have a restriction that you cannot reference a variable
until after it is defined. This is the same kind of restriction.

## Primitive recursion

Primitive recursive functions may only use a simple form of recursion. In particular,

- The recursion must be guaranteed to terminate. To ensure this, the function must carry
along an extra parameter that is "decremented" each time the function is called
(s(x) is replaced by x), and halts the recursion when it reaches "zero" (z(x)).
That is,
f(..., z(x)) = ...

f(..., s(x)) = ... f(..., x), ...

- The recursive function must appear
*only once* in the definiens (right hand side of
the definition). This restriction prevents various forms of "fancy" recursion.

*General recursive functions,* which don't have these restrictions, are more powerful
than primitive recursive functions.

Copyright © 1996 by David Matuszek

Last modified Apr 18, 1996