Example: Which of the following two recursive definition is valid ?
  1. Let x0 = x1 = 1 and define xn = xn - 1 + xn - 2 for all n > 1.
  2. Select the following subset from the natural numbers:
  1. Suppose we let x0 = x1 = 1 and define xn = xn - 1 + xn - 2 for all n > 1. Then the first element is uniquely determined, and each following element to be selected depends only on the ones that have already been selected. Hence, this is a valid recursive definition. Note that to compute, say, x5 , we need to compute all previous numbers first. The numbers defined in this way are called Fibonacci numbers.
  2. This is not a valid recursive definition, because to find the element x2, say, we need to find the smallest element of the set N - {x0 , x1 , x2 , x3}. Since this definition involves the element x2 itself (and also x3) which we do not know at this stage, this recursive definition is not valid.
To Theory | Glossary | Map
(bgw)