Course-of-values Recursion - Definition and Examples

Definition and Examples

The factorial function n! is recursively defined by the rules

0! = 1,

(n+1)! = (n+1)*(n!).

This recursion is a primitive recursion because it computes the next value (n+1)! of the function based on the value of n and the previous value n! of the function. On the other hand, the function Fib(n), which returns the nth Fibonacci number, is defined with the recursion equations

Fib(0) = 0,

Fib(1) = 1,

Fib(n+2) = Fib(n+1) + Fib(n).

In order to compute Fib(n+2), the last two values of the Fib function are required. Finally, consider the function g defined with the recursion equations

g(0) = 0,

.

To compute g(n+1) using these equations, all the previous values of g must be computed; no fixed finite number of previous values is sufficient in general for the computation of g. The functions Fib and g are examples of functions defined by course-of-values recursion.

In general, a function f is defined by course-of-values recursion if there is a fixed primitive recursive function h such that for all n,

where is a Gödel number encoding the indicated sequence. In particular

provides the initial value of the recursion. The function h might test its first argument to provide explicit initial values, for instance for Fib one could use the function defined by

where s denotes extraction of the element i from an encoded sequence s; this is easily seen to be a primitive recursive function (assuming an appropriate Gödel numbering is used).