180
Recursion, Recurrence Relations, and Analysis of Algorithms
been submitted and studied by many people. (See oeis.org). There is even a YouTube movie about the OEIS!
Recaman’s sequence (number A005132 in the OEIS catalog) is a recursive sequence defined as follows:
a(1) = 1
For n > 1,
a(n) = •
a(n − 1) − n if that number is positive and not already in the sequence,
otherwise
a(n − 1) + n
a. Confirm that the first few terms of this sequence are 1, 3, 6, 2, 7, 13.
b. It has been conjectured that every nonnegative integer will eventually appear in this sequence. Find the
index of this sequence at which the following numbers appear: 10, 12, 23.
S e c t I o n 3 . 2 ReCuRRenCe Rel ations
We developed two algorithms, one iterative and one recursive, to compute a
value S(n) for the sequence S of Example 1. However, there is a still easier way to
compute S(n). Recall that
S(1) = 2
(1)
S(n) = 2S(n − 1) for n ≥ 2
(2)
Because
S(1) = 2 = 2
1
S(2) = 4 = 2
2
S(3) = 8 = 2
3
S(4) = 16 = 2
4
and so on, we can see that
S(n) = 2
n
(3)
Using Equation (3), we can plug in a value for n and compute S(n) without having to compute—either explicitly, or, through recursion, implicitly—all the lower
values of S first. An equation such as (3), where we can substitute a value and get
the output value back directly, is called a closed-form solution to the recurrence
relation (2) subject to the basis step (1). Finding a closed-form solution is called
solving the recurrence relation.
Recurrence relations can be used to describe a variety of things, from chemical degradation (see the opening problem for this chapter) to the amount in an
interest-bearing account, from the growth of species to the spread of a computer
virus. Clearly, it is nice to find a closed-form solution to a recurrence relation
whenever possible.
Linear First-Order Recurrence Relations
Expand, Guess, and Verify
One technique for solving recurrence relations is an “expand, guess, and verify”
approach that repeatedly uses the recurrence relation to expand the expression for
the nth term until the general pattern can be guessed. Finally the guess is verified
by mathematical induction.
Recursion, Recurrence Relations, and Analysis of Algorithms
been submitted and studied by many people. (See oeis.org). There is even a YouTube movie about the OEIS!
Recaman’s sequence (number A005132 in the OEIS catalog) is a recursive sequence defined as follows:
a(1) = 1
For n > 1,
a(n) = •
a(n − 1) − n if that number is positive and not already in the sequence,
otherwise
a(n − 1) + n
a. Confirm that the first few terms of this sequence are 1, 3, 6, 2, 7, 13.
b. It has been conjectured that every nonnegative integer will eventually appear in this sequence. Find the
index of this sequence at which the following numbers appear: 10, 12, 23.
S e c t I o n 3 . 2 ReCuRRenCe Rel ations
We developed two algorithms, one iterative and one recursive, to compute a
value S(n) for the sequence S of Example 1. However, there is a still easier way to
compute S(n). Recall that
S(1) = 2
(1)
S(n) = 2S(n − 1) for n ≥ 2
(2)
Because
S(1) = 2 = 2
1
S(2) = 4 = 2
2
S(3) = 8 = 2
3
S(4) = 16 = 2
4
and so on, we can see that
S(n) = 2
n
(3)
Using Equation (3), we can plug in a value for n and compute S(n) without having to compute—either explicitly, or, through recursion, implicitly—all the lower
values of S first. An equation such as (3), where we can substitute a value and get
the output value back directly, is called a closed-form solution to the recurrence
relation (2) subject to the basis step (1). Finding a closed-form solution is called
solving the recurrence relation.
Recurrence relations can be used to describe a variety of things, from chemical degradation (see the opening problem for this chapter) to the amount in an
interest-bearing account, from the growth of species to the spread of a computer
virus. Clearly, it is nice to find a closed-form solution to a recurrence relation
whenever possible.
Linear First-Order Recurrence Relations
Expand, Guess, and Verify
One technique for solving recurrence relations is an “expand, guess, and verify”
approach that repeatedly uses the recurrence relation to expand the expression for
the nth term until the general pattern can be guessed. Finally the guess is verified
by mathematical induction.