Recursively Defined Sequences
A sequence can be defined in a
variety of different ways. One informal way
is to write the first few terms with the expectation that the general
pattern will be obvious. For instance, "consider the sequence 3, 5
,7,
...". The next term of the sequence could be 9 if we mean the
sequence of
odd integers or it could be 11 if we mean the sequence of odd prime
numbers.
A second way to define a sequence is to give an explicit formula for
its
nth term. For example, a sequence a0, a1, a2, ... can be
specified by writing
|
an = |
(-1)n
¾¾¾¾
n + 1
|
, for all integers n
³ 0. |
|
the advantage of defining a sequence by such an explicit formula
is that each term of the sequence is uniquely determined and any term
can be computed in a fixed, finite number of steps.
A third way to define a sequence is to use recursion. This
requires
giving both an equation, called a recurrence relation, that
relates
later terms in the sequence of earlier terms and a specification,
called
initial conditions, of the values of the first few terms
of the sequence. For instance, a sequence b0, b1, b2, ...
can be
defined recursively as follows: For all integers k ³ 2,
|
bk = bk-1 + bk-2 recurrence relation |
|
|
b0 = 1, b2 = 3 initial conditions. |
|
Sometimes, it is very difficult or impossible to find an explicit
formula
for a sequence, but it is possible to define it using recursion.
Note that defining sequences recursively is similar to proving
theorems by mathematical induction. The recurrence relation is like
the inductive step and the initial conditions are like the basis step.
Recursion is one of the central ideas of computer science. To solve a
problem recursively means to find a way to break it down into smaller
subproblems each having the same form as the original problem and to
do
this in such way that when the process is repeated many times the
last of
the subproblems are small and easy to solve and the solutions of the
subproblems can be woven together to form a solution to the original
problem.
Probably the most difficult part of solving problems recursively is to
figure out how knowing the solution to smaller subproblems of the
same
type as the original problem will give you a solution to the problem
as
a whole. You suppose you know the solutions to smaller subproblems
and ask
yourself how you would best make use of that knowledge to solve the
larger
problem. The supposition that the smaller subproblems have already
been solved has been called recursive leap of faith. Once you take
this
leap, you are right in the middle of the most difficult part of the
problem, but generally through difficult, the path to a solution from
this point is short. The recursive leap of faith is similar to the
inductive hypothesis in a proof by mathematical induction.
|
