158
Recursion, Recurrence Relations, and Analysis of Algorithms
S e c t I o n 3 . 1 ReCuRsive Definitions
A definition in which the item being defined appears as part of the definition
is called a recursive definition. At first this seems like nonsense—how can we
define something in terms of itself? This works because there are two parts to a
recursive definition:
1. A basis, where some simple cases of the item being defined are explicitly
given
2. An inductive or recursive step, where new cases of the item being defined
are given in terms of previous cases
Part 1 gives us a place to start by providing some simple, concrete cases;
part 2 allows us to construct new cases from these simple ones and then to construct still other cases from these new ones, and so forth. (This seems analogous
to proofs by mathematical induction. In a proof by induction, there is a basis step,
namely, to show that P(1)—or P at some other initial value—holds, and there is
an inductive step where the truth of P(k + 1) is deduced from the truth of P at previous values. This similarity is why the term inductive definition is sometimes
used instead of recursive definition.)
Recursion is an important idea that can be used to define sequences of objects, more general collections of objects, and operations on objects. (The Prolog
predicate in-food-chain of Section 1.5 was defined recursively.) Even algorithms
can be recursive.
Recursively Defined Sequences
A sequence S (an infinite sequence) is a list of objects that are enumerated in
some order; there is a first such object, then a second, and so on. S(k) denotes
the k th object in the sequence. The list goes on forever, so a sequence therefore
consists of
S(1), S(2), … , S(k), …
Subscript notation is often used to denote the elements in a sequence, as in
S 1 , S 2 , … , S k , …
The letter S is just a “dummy variable,” so a sequence could also be denoted by
a 1 , a 2 , … , a k , …
or
w 1 , w 2 , … , w k …
and so forth.
1
A sequence is defined recursively by explicitly naming the first value (or the
first few values) in the sequence and then defining later values in the sequence in
terms of earlier values.
1 A more formal definition of a sequence is given in Chapter 5, Example 27.
Recursion, Recurrence Relations, and Analysis of Algorithms
S e c t I o n 3 . 1 ReCuRsive Definitions
A definition in which the item being defined appears as part of the definition
is called a recursive definition. At first this seems like nonsense—how can we
define something in terms of itself? This works because there are two parts to a
recursive definition:
1. A basis, where some simple cases of the item being defined are explicitly
given
2. An inductive or recursive step, where new cases of the item being defined
are given in terms of previous cases
Part 1 gives us a place to start by providing some simple, concrete cases;
part 2 allows us to construct new cases from these simple ones and then to construct still other cases from these new ones, and so forth. (This seems analogous
to proofs by mathematical induction. In a proof by induction, there is a basis step,
namely, to show that P(1)—or P at some other initial value—holds, and there is
an inductive step where the truth of P(k + 1) is deduced from the truth of P at previous values. This similarity is why the term inductive definition is sometimes
used instead of recursive definition.)
Recursion is an important idea that can be used to define sequences of objects, more general collections of objects, and operations on objects. (The Prolog
predicate in-food-chain of Section 1.5 was defined recursively.) Even algorithms
can be recursive.
Recursively Defined Sequences
A sequence S (an infinite sequence) is a list of objects that are enumerated in
some order; there is a first such object, then a second, and so on. S(k) denotes
the k th object in the sequence. The list goes on forever, so a sequence therefore
consists of
S(1), S(2), … , S(k), …
Subscript notation is often used to denote the elements in a sequence, as in
S 1 , S 2 , … , S k , …
The letter S is just a “dummy variable,” so a sequence could also be denoted by
a 1 , a 2 , … , a k , …
or
w 1 , w 2 , … , w k …
and so forth.
1
A sequence is defined recursively by explicitly naming the first value (or the
first few values) in the sequence and then defining later values in the sequence in
terms of earlier values.
1 A more formal definition of a sequence is given in Chapter 5, Example 27.