Definition and Examples
The factorial function n! is recursively defined by the rules
- 0! = 1,
- (n+1)! = (n+1)*(n!).
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,
- .
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 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).
Read more about this topic: Course-of-values Recursion
Famous quotes containing the words definition and/or examples:
“Mothers often are too easily intimidated by their childrens negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)
“There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
—Bernard Mandeville (16701733)