Course-of-values recursion

In <a href="/facts/Computability_theory/cqDfXwdf">computability theory</a>, course-of-values recursion is a technique for defining <a href="/facts/Number-theoretic_function/hULxwsgm">number-theoretic functions</a> by <a href="/facts/Recursion_(computer_science)/2uXo18Gv">recursion</a>. In a definition of a function f by course-of-values recursion, the value of f(n) is computed from the sequence 
 
 
 
 ⟨
 f
 (
 0
 )
 ,
 f
 (
 1
 )
 ,
 …
 ,
 f
 (
 n
 −
 1
 )
 ⟩
 
 
 {\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 <a href="/facts/Primitive_recursive/4z97gRnl">primitive recursive</a>. 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 <a href="/facts/Arity/zSVuwHvP">1-ary</a> primitive recursive function g the value of g(n+1) is computed only from g(n) and n.

Course-of-values recursion open-in-new

Course-of-values recursion