TheInfoList

In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion. In a definition of a function f by course-of-values recursion, the value of f(n) is computed from the sequence ${\displaystyle \langle f(0),f(1),\ldots ,f(n-1)\rangle }$.

The fact that such definitions can be converted into definitions using a simpler form of recursion is often used to prove that functions defined by course-of-values recursion are 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.

## 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,