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