Mathematical Analysis of Recursive Algorithms

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,⁵ 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 = 2^k 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 = 2^k 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 = 2^k takes the form

Thus, we end up with

A(2^k) = A(1) + k = k,

or, after returning to the original variable n = 2^k and hence k = log₂ n,

A(n) = log₂ 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) = log₂ 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 = 2^k)

e.  x(n) = x(n/3) + 1 for n > 1,                x(1) = 1 (solve for n = 3^k)

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) = 1³ + 2³ + ^{. . .} + n³.

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.