title: Course-of-values recursion
text: # Course-of-values recursion
  
  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 $\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
  
      $0!=1,$
      $(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
  
      $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,$
      $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,
  
      $f(n)=h(n,\langle f(0),f(1),\ldots ,f(n-1)\rangle )$
  
  where $\langle f(0),f(1),\ldots ,f(n-1)\rangle$ is a Gödel number encoding the indicated sequence. In particular
  
      $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
  
      $h(n,s)={\begin{cases}n&{\text{if }}n<2\\s[n-2]+s[n-1]&{\text{if }}n\geq 2\end{cases}}$
  
  where s[i] 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).
  
  ## Equivalence to primitive recursion
  
  In order to convert a definition by course-of-values recursion into a primitive recursion, an auxiliary (helper) function is used. Suppose that one wants to have
  
      $f(n)=h(n,\langle f(0),f(1),\ldots ,f(n-1)\rangle )$.
  
  To define f using primitive recursion, first define the auxiliary course-of-values function that should satisfy
  
      ${\bar {f}}(n)=\langle f(0),f(1),\ldots ,f(n-1)\rangle$
  
  where the right hand side is taken to be a Gödel numbering for sequences.
  
  Thus ${\bar {f}}(n)$ encodes the first n values of f. The function ${\bar {f}}$ can be defined by primitive recursion because ${\bar {f}}(n+1)$ is obtained by appending to ${\bar {f}}(n)$ the new element $h(n,{\bar {f}}(n))$:
  
      ${\bar {f}}(0)=\langle \rangle$,
      ${\bar {f}}(n+1)={\mathit {append}}(n,{\bar {f}}(n),h(n,{\bar {f}}(n))),$
  
  where append(n,s,x) computes, whenever s encodes a sequence of length n, a new sequence t of length n + 1 such that t[n] = x and t[i] = s[i] for all i < n. This is a primitive recursive function, under the assumption of an appropriate Gödel numbering; h is assumed primitive recursive to begin with. Thus the recursion relation can be written as primitive recursion:
  
      ${\bar {f}}(n+1)=g(n,{\bar {f}}(n))$
  
  where g is itself primitive recursive, being the composition of two such functions:
  
      $g(i,j)={\mathit {append}}(i,j,h(i,j)),$
  
  Given ${\bar {f}}$, the original function f can be defined by $f(n)={\bar {f}}(n+1)[n]$, which shows that it is also a primitive recursive function.
  
  ## Application to primitive recursive functions
  
  In the context of primitive recursive functions, it is convenient to have a means to represent finite sequences of natural numbers as single natural numbers. One such method, Gödel's encoding, represents a sequence of positive integers $\langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangle$ as
  
      $\prod _{i=0}^{k}p_{i}^{n_{i}}$,
  
  where $p_i$ represent the ith prime. It can be shown that, with this representation, the ordinary operations on sequences are all primitive recursive. These operations include
  
  * Determining the length of a sequence,
  * Extracting an element from a sequence given its index,
  * Concatenating two sequences.
  
  Using this representation of sequences, it can be seen that if h(m) is primitive recursive then the function
  
      $f(n)=h(\langle f(0),f(1),f(2),\ldots ,f(n-1)\rangle )$.
  
  is also primitive recursive.
  
  When the sequence $\langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangle$ is allowed to include zeros, it is instead represented as
  
      $\prod _{i=0}^{k}p_{i}^{(n_{i}+1)}$,
  
  which makes it possible to distinguish the codes for the sequences $\langle 0\rangle$ and $\langle 0,0\rangle$.
  
  ## Limitations
  
  Not every recursive definition can be transformed into a primitive recursive definition. One known example is Ackermann's function, which is of the form A(m,n) and is provably not primitive recursive.
  
  Indeed, every new value A(m+1, n) depends on the sequence of previously defined values A(i, j), but the i-s and j-s for which values should be included in this sequence depend themselves on previously computed values of the function; namely (i, j) = (m, A(m+1, n)). Thus one cannot encode the previously computed sequence of values in a primitive recursive way in the manner suggested above (or at all, as it turns out this function is not primitive recursive).
  
  