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

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

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

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