• 1 Definition and examples
• 2 Equivalence to primitive recursion
• 3 Application to primitive recursive functions
• 4 Limitations
• 5 References

Definition and examples

The factorial function n! is recursively defined by the rules

${\displaystyle 0!=1,}$

${\displaystyle (n+1)!=n!(n+1).}$

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

${\displaystyle Fib(0)=0,}$

${\displaystyle Fib(1)=1,}$

${\displaystyle Fib(n+2)=Fib(n+1)+Fib(n).}$primitive recursive. Contrary to course-of-values recursion, in primitive recursion the computation of a value of a function requires only the previous value; for example, for a 1-ary primitive recursive function g the value of g(n+1) is computed only from g(n) and n.

The factorial function n! is recursively defined by the rules

${\displaystyle 0!=1,}$

${\displaystyle (n+1)!=n!(n+1).}$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

${\displaystyle Fib(0)=0,}$

${\displaystyle Fib(1)=1,}$

${\displaystyle g(0)=0,}$

${\displaystyle g(n+1)=\sum _{i=0}^{n}g(i)^{n-i}.}$

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,

$$

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,

${\displaystyle f(n)=h(n,\langle f(0),f(1),\ldots ,f(n-1)\rangle )}$

where ${\displaystyle ⟨<!--\; ⟨\; -->f(0),f}$

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 ${\displaystyle \langle f(0),f(1),\ldots ,f(n-1)\rangle }$ is a Gödel number encoding the indicated sequence. In particular

${\displaystyle f(0)=h(0,\langle \rangle )}$

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

${\displaystyle f(n)=h(n,\langle f(0),f(1),\ldots ,f(n-1)\rangle )}$