In a definition of a function f by course-of-values recursion, the value of f(n) is computed from the sequence
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!
On the other hand, the function Fib(n), which returns the nth Fibonacci number, is defined with the recursion equations 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 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, where
is a Gödel number encoding the indicated sequence.
In particular 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 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).
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 To define f using primitive recursion, first define the auxiliary course-of-values function that should satisfy where the right hand side is taken to be a Gödel numbering for sequences.
: 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.
, which shows that it is also a primitive recursive function.
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
as where pi represent the ith prime.
It can be shown that, with this representation, the ordinary operations on sequences are all primitive recursive.
is allowed to include zeros, it is instead represented as which makes it possible to distinguish the codes for the sequences
One known example is Ackermann's function, which is of the form A(m,n) and is provably not primitive recursive.
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).