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.

**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**!

and 0! = 1 by definition, we can compute ** F (n)** =

**ALGORITHM** *F**(n)*

//Computes
** n**! recursively //Input: A nonnegative
integer

**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,

** F (n) **=

the
number of multiplications ** M(n)** needed
to compute it must satisfy the equality

Indeed, ** M(n** − 1

The last
equation defines the sequence ** M(n)** that we
need to find. This equa-tion defines

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

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

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

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)** =

What
remains to be done is to take advantage of the initial condition given. Since
it is specified for ** n** = 0

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

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**

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

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

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

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

**else return ***BinRec*** ( n/**2

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

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

Thus, we
end up with

** A(**2

or, after
returning to the original variable ** n** = 2

** A(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

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

**b. ***x(n)*** **=** **3*x(n*** **−** **1*)*** **for** ***n >*** **1*,*** x(**1

**c. ***x(n)*** **=** ***x(n*** **−** **1*)*** **+** ***n*** **for** ***n
>*** **0*,*** x(**0

**d. ***x(n)*** **=** **** x(n/**2

**e. ***x(n)*** **=** **** x(n/**3

Set up
and solve a recurrence relation for the number of calls made by ** F (n),** the recursive algorithm for
computing

Consider
the following recursive algorithm for computing the sum of the first ** n **cubes:

**ALGORITHM** *S(n)*

//Input:
A positive integer *n*

//Output:
The sum of the first ** n** cubes

**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.

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

//Input:
An array ** A**[0

**else ***temp*** **←** ***Riddle (A*[0

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

//Input:
Adjacency matrix ** A**[0

**if ***n*** **=** **1** return **1 //one-vertex
graph is complete by definition

**else**

if **not** *GraphComplete*** (A**[0

**if **** A**[

What is
the algorithm’s efficiency class in the worst case?

**11. **The determinant of an** ***n*** **×** ***n*** **matrix

where ** s_{j}** is +1 if

**
**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

**
**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.

*Celebrity problem *A
celebrity among a group of* **n** *people is
a person who* *knows nobody but is
known by everybody else. The task is to identify a celebrity by only asking
questions to people of the form “Do you know him/her?” Design an efficient
algorithm to identify a celebrity or determine that the group has no such
person. How many questions does your algorithm need in the worst case?

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Fundamentals of the Analysis of Algorithm Efficiency : Mathematical Analysis of Recursive Algorithms |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.