Mathematical
Analysis of Recursive Algorithms
In
this section, we will see how to apply the general framework for analysis of
algorithms to recursive algorithms. We start with an example often used to
introduce novices to the idea of a recursive algorithm.
EXAMPLE 1 Compute the factorial function F (n) = n! for an arbitrary nonneg-ative
integer n. Since
n! = 1 . . . . . (n − 1) . n = (n − 1)! . n
for n ≥ 1
and
0! = 1
by definition, we can compute F (n) = F (n − 1) . n with the following recursive
algorithm.
ALGORITHM F(n)
//Computes n! recursively //Input: A nonnegative
integer n //Output: The value of n!
if n = 0 return 1
else
return F (n − 1) ∗ n
For
simplicity, we consider n itself as an indicator of this
algorithm’s input size (rather than the number of bits in its binary
expansion). The basic operation of the algorithm is multiplication,5 whose
number of executions we denote M(n). Since the function F (n) is computed according to the
formula
F
(n) = F
(n − 1) . n
for n > 0,
the
number of multiplications M(n) needed to compute it must
satisfy the equality
Indeed, M(n − 1) multiplications are spent to
compute F (n − 1), and one more multiplication is
needed to multiply the result by n.
The
last equation defines the sequence M(n) that
we need to find. This equa-tion defines M(n) not explicitly, i.e., as a
function of n, but implicitly as a function of
its value at another point, namely n − 1. Such equations are called recurrence relations or,
for brevity, recurrences. Recurrence relations play an
important role not only in analysis of algorithms but also
in some areas of applied mathematics. They are usually studied in detail in
courses on discrete mathematics or discrete structures; a very brief tutorial
on them is provided in Appendix B. Our goal now is to solve the recurrence
relation M(n) = M(n − 1) + 1, i.e., to find an explicit
formula for M(n) in terms of n only.
Note,
however, that there is not one but infinitely many sequences that satisfy this
recurrence. (Can you give examples of, say, two of them?) To determine a
solution uniquely, we need an initial condition that
tells us the value with which the sequence starts. We can obtain this value by
inspecting the condition that makes the algorithm stop its recursive calls:
if n = 0 return 1.
This
tells us two things. First, since the calls stop when n = 0, the smallest value of n for which this algorithm is
executed and hence M(n) defined is 0. Second, by
inspecting the pseudocode’s exiting line, we can see that when n = 0, the algorithm performs no
multiplications. Therefore, the initial condition we are after is
Before
we embark on a discussion of how to solve this recurrence, let us pause to
reiterate an important point. We are dealing here with two recursively defined
functions. The first is the factorial function F (n) itself; it is defined by the
recurrence
The
second is the number of multiplications M(n) needed to compute F (n) by the recursive algorithm
whose pseudocode was given at the beginning of the section.
As
we just showed, M(n) is defined by recurrence (2.2).
And it is recurrence (2.2) that we need to solve now.
Though
it is not difficult to “guess” the solution here (what sequence starts with 0
when n = 0 and increases by 1 on each
step?), it will be more useful to arrive at it in a systematic fashion. From
the several techniques available for solving recurrence relations, we use what
can be called the method of backward substitutions.
The method’s idea (and the reason for the name) is immediately clear
from the way it applies to solving our particular recurrence:
After
inspecting the first three lines, we see an emerging pattern, which makes it
possible to predict not only the next line (what would it be?) but also a
general formula for the pattern: M(n) = M(n − i) + i. Strictly speaking, the
correctness of this formula should be proved by mathematical induction, but it
is easier to get to the solution as follows and then verify its correctness.
What
remains to be done is to take advantage of the initial condition given. Since
it is specified for n = 0, we have to substitute i = n in the pattern’s formula to get
the ultimate result of our backward substitutions:
You
should not be disappointed after exerting so much effort to get this “obvious”
answer. The benefits of the method illustrated in this simple example will
become clear very soon, when we have to solve more difficult recurrences. Also,
note that the simple iterative algorithm that accumulates the product of n consecutive integers requires
the same number of multiplications, and it does so without the overhead of time
and space used for maintaining the recursion’s stack.
The
issue of time efficiency is actually not that important for the problem of
computing n!, however. As we saw in Section 2.1,
the function’s values get so large so fast that we can realistically compute
exact values of n! only for very small n’s. Again, we use this example just
as a simple and convenient vehicle to introduce the standard approach to
analyzing recursive algorithms.
Generalizing
our experience with investigating the recursive algorithm for computing n!, we can now outline a general plan
for investigating recursive algo-rithms.
General
Plan for Analyzing the Time Efficiency of Recursive Algorithms
Decide
on a parameter (or parameters) indicating an input’s size.
Identify
the algorithm’s basic operation.
Check whether the number of times
the basic operation is executed can vary on different inputs of the same size;
if it can, the worst-case, average-case, and best-case efficiencies must be
investigated separately.
Set up a recurrence relation, with
an appropriate initial condition, for the number of times the basic operation
is executed.
Solve the recurrence or, at least,
ascertain the order of growth of its solution.
EXAMPLE
2 As our next
example, we consider another educational workhorse of recursive algorithms: the Tower
of Hanoi puzzle. In this puzzle, we (or mythical monks, if you do
not like to move disks) have n disks of different sizes that
can slide onto any of three pegs. Initially, all the disks are on the first peg
in order of size, the largest on the bottom and the smallest on top. The goal
is to move all the disks to the third peg, using the second one as an
auxiliary, if necessary. We can move only one disk at a time, and it is
forbidden to place a larger disk on top of a smaller one.
The
problem has an elegant recursive solution, which is illustrated in Fig-ure 2.4.
To move n > 1 disks from peg 1 to peg 3
(with peg 2 as auxiliary), we first move recursively n − 1 disks from
peg 1 to peg 2 (with peg 3 as auxiliary), then move the largest disk directly
from peg 1 to peg 3, and, finally, move recursively n − 1 disks from peg 2 to peg 3 (using
peg 1 as auxiliary). Of course, if n = 1, we simply move the single disk directly
from the source peg to the destination peg.
Let
us apply the general plan outlined above to the Tower of Hanoi problem. The
number of disks n is the obvious choice for the
input’s size indicator, and so is moving one disk as the algorithm’s basic
operation. Clearly, the number of moves M(n) depends on n only, and we get the following
recurrence equation for it:
Thus,
we have an exponential algorithm, which will run for an unimaginably long time
even for moderate values of n (see Problem 5 in this
section’s exercises). This is not due to the fact that this particular
algorithm is poor; in fact, it is not difficult to prove that this is the most
efficient algorithm possible for this problem. It is the problem’s intrinsic
difficulty that makes it so computationally hard. Still, this example makes an
important general point:
One
should be careful with recursive algorithms because their succinctness may mask
their inefficiency.
When
a recursive algorithm makes more than a single call to itself, it can be useful
for analysis purposes to construct a tree of its recursive calls. In this tree,
nodes correspond to recursive calls, and we can label them with the value of
the parameter (or, more generally, parameters) of the calls. For the Tower of
Hanoi example, the tree is given in Figure 2.5. By counting the number of nodes
in the tree, we can get the total number of calls made by the Tower of Hanoi
algorithm:
The
number agrees, as it should, with the move count obtained earlier.
EXAMPLE
3 As our next
example, we investigate a recursive version of the algorithm discussed at the end of
Section 2.3.
ALGORITHM BinRec(n)
//Input:
A positive decimal integer n
//Output:
The number of binary digits in n’s binary representation if n = 1 return 1
else
return BinRec( n/2 ) + 1
Let
us set up a recurrence and an initial condition for the number of
addi-tions A(n) made by the algorithm. The
number of additions made in computing BinRec( n/2 ) is A( n/2 ), plus one more addition is made by
the algorithm to increase the returned value by 1. This leads to
the recurrence
Since
the recursive calls end when n is equal to 1 and there are no
additions made then, the initial condition is
The
presence of n/2 in the function’s argument makes
the method of back-ward substitutions stumble on values of n that are not powers of 2.
Therefore, the standard approach to solving such a recurrence is to solve it
only for n = 2k and then take advantage of the
theorem called the smoothness rule (see Appendix B),
which claims that under very broad assumptions the order of growth observed
for n = 2k gives a correct answer about the
order of growth for all values of n. (Alter-natively, after getting a
solution for powers of 2, we can sometimes fine-tune this solution to get a
formula valid for an arbitrary n.) So let us apply this recipe to
our recurrence, which for n = 2k takes the form
Thus,
we end up with
A(2k) = A(1) + k = k,
or,
after returning to the original variable n = 2k and hence k = log2 n,
A(n) = log2 n ∈ (log n).
In
fact, one can prove (Problem 7 in this section’s exercises) that the exact
solution for an arbitrary value of n is
given by just a slightly more refined formula A(n) = log2 n
This
section provides an introduction to the analysis of recursive algorithms. These
techniques will be used throughout the book and expanded further as necessary.
In the next section, we discuss the Fibonacci numbers; their analysis involves
more difficult recurrence relations to be solved by a method different from
backward substitutions.
Exercises
2.4
1. Solve the following recurrence
relations.
a.
x(n) = x(n − 1) + 5
for n > 1, x(1) = 0
b. x(n) = 3x(n − 1) for n > 1, x(1) = 4
c. x(n) = x(n − 1) + n for n > 0, x(0) = 0
d. x(n) = x(n/2) + n for n > 1, x(1) = 1 (solve for n = 2k)
e. x(n) = x(n/3) + 1
for n > 1, x(1) = 1 (solve for n = 3k)
Set
up and solve a recurrence relation for the number of calls made by F (n), the recursive algorithm for
computing n!.
Consider
the following recursive algorithm for computing the sum of the first n cubes: S(n) = 13 + 23 + . . . + n3.
ALGORITHM S(n)
//Input:
A positive integer n
//Output:
The sum of the first n cubes if n = 1 return 1
else
return S(n − 1) + n ∗ n ∗ n
Set up and solve a
recurrence relation for the number of times the algo-rithm’s basic operation is
executed.
How
does this algorithm compare with the straightforward nonrecursive algorithm for
computing this sum?
Consider
the following recursive algorithm.
ALGORITHM Q(n)
//Input:
A positive integer n if n = 1 return 1
else
return Q(n − 1) + 2 ∗ n − 1
Set up a recurrence relation for
this function’s values and solve it to deter-mine what this algorithm computes.
Set up a recurrence relation for the
number of multiplications made by this algorithm and solve it.
Set up a recurrence relation for the
number of additions/subtractions made by this algorithm and solve it.
Tower
of Hanoi
In the original version of the Tower of Hanoi puzzle, as it was published in
the 1890s by Edouard Lucas, a French mathematician, the world will end after 64
disks have been moved from a mystical Tower of Brahma. Estimate the number of
years it will take if monks could move one disk per minute. (Assume that monks
do not eat, sleep, or die.)
How many moves are made by the ith largest disk (1 ≤ i ≤ n) in this
algorithm?
Find a nonrecursive algorithm for the Tower of Hanoi puzzle and imple-ment it
in the language of your choice.
Restricted
Tower of Hanoi Consider the version of the Tower of Hanoi puzzle in which n
disks have to be moved from peg A to peg C using peg B so that any move should
either place a disk on peg B or move a disk from that peg. (Of course, the
prohibition of placing a larger disk on top of a smaller one remains in place,
too.) Design a recursive algorithm for this problem and find the number of
moves made by it.
a. Prove that the exact number of additions made by the recursive algorithm
BinRec(n) for an arbitrary positive decimal integer n is log2 n .
Set up a recurrence relation for the number of additions made by the
nonrecursive version of this algorithm (see Section 2.3, Example 4) and solve
it.
a. Design a recursive algorithm for computing 2n for any nonnegative integer n
that is based on the formula 2n = 2n−1 + 2n−1.
Set up a recurrence relation for the number of additions made by the algorithm
and solve it.
Draw a tree of recursive calls for this algorithm and count the number of calls
made by the algorithm.
Is it a good algorithm for solving this problem?
Consider the following recursive algorithm.
ALGORITHM Riddle(A[0..n − 1])
//Input:
An array A[0..n − 1] of real
numbers if n = 1 return A[0]
else temp ← Riddle(A[0..n − 2]) if temp ≤ A[n − 1] return temp else
return A[n − 1]
What
does this algorithm compute?
Set
up a recurrence relation for the algorithm’s basic operation count and solve
it.
Consider
the following algorithm to check whether a graph defined by its adjacency
matrix is complete.
ALGORITHM GraphComplete(A[0..n − 1, 0..n − 1])
//Input:
Adjacency matrix A[0..n − 1, 0..n − 1]) of an undirected graph G //Output: 1 (true) if G is complete and 0 (false)
otherwise
if n = 1 return 1
//one-vertex graph is complete by definition
else
if not GraphComplete(A[0..n − 2, 0..n − 2]) return 0 else
for j ← 0 to n − 2 do
if A[n − 1, j ] = 0 return 0 return 1
What
is the algorithm’s efficiency class in the worst case?
11. The determinant of an n × n matrix
where sj is +1 if j is even and −1 if j is odd, a0 j is
the element in row 0 and column j , and Aj is the (n − 1) × (n − 1) matrix obtained from
matrix A by deleting its row 0 and
column j .
Set
up a recurrence relation for the number of multiplications made by the
algorithm implementing this recursive definition.
Without
solving the recurrence, what can you say about the solution’s order of growth
as compared to n!?
12. von
Neumann’s neighborhood revisited Find the number of cells in the von Neumann
neighborhood of range n (Problem 12 in Exercises 2.3)
by setting up and solving a recurrence relation.
Frying
hamburgers There
are n hamburgers to be fried on a small
grill that can hold only two hamburgers at a time. Each hamburger
has to be fried on both sides; frying one side of a hamburger takes 1 minute,
regardless of whether one or two hamburgers are fried at the same time.
Consider the following recursive algorithm for executing this task in the
minimum amount of time. If n ≤ 2, fry the hamburger or the two
hamburgers together on each side. If n > 2, fry any two hamburgers together
on each side and then apply the same procedure recursively to the
remaining n − 2 hamburgers.
Set
up and solve the recurrence for the amount of time this algorithm needs to
fry n hamburgers.
Explain
why this algorithm does not fry the hamburgers in the minimum
amount of time for all n > 0.
Give a
correct recursive algorithm that executes the task in the minimum amount of
time.