4.5.

Exercises 183
1 /∗∗ Returns the sum of the integers in given array. ∗/
2 public static int example1(int[ ] arr) {
3 int n = arr.length, total = 0;
4 for (int j=0; j < n; j++) // loop from 0 to n-1
5 total += arr[j];
6 return total;
7 }
8
9 /∗∗ Returns the sum of the integers with even index in given array. ∗/
10 public static int example2(int[ ] arr) {
11 int n = arr.length, total = 0;
12 for (int j=0; j < n; j += 2) // note the increment of 2
13 total += arr[j];
14 return total;
15 }
16
17 /∗∗ Returns the sum of the prefix sums of given array. ∗/
18 public static int example3(int[ ] arr) {
19 int n = arr.length, total = 0;
20 for (int j=0; j < n; j++) // loop from 0 to n-1
21 for (int k=0; k <= j; k++) // loop from 0 to j
22 total += arr[j];
23 return total;
24 }
25
26 /∗∗ Returns the sum of the prefix sums of given array. ∗/
27 public static int example4(int[ ] arr) {
28 int n = arr.length, prefix = 0, total = 0;
29 for (int j=0; j < n; j++) { // loop from 0 to n-1
30 prefix += arr[j];
31 total += prefix;
32 }
33 return total;
34 }
35
36 /∗∗ Returns the number of times second array stores sum of prefix sums from first. ∗/
37 public static int example5(int[ ] first, int[ ] second) { // assume equal-length arrays
38 int n = first.length, count = 0;
39 for (int i=0; i < n; i++) { // loop from 0 to n-1
40 int total = 0;
41 for (int j=0; j < n; j++) // loop from 0 to n-1
42 for (int k=0; k <= j; k++) // loop from 0 to j
43 total += first[k];
44 if (second[i] == total) count++;
45 }
46 return count;
47 }
Code Fragment 4.12: Some sample algorithms for analysis.

www.it-ebooks.info
184 Chapter 4. Algorithm Analysis
R-4.17 Show that if d(n) is O( f (n)) and e(n) is O(g(n)), then d(n) − e(n) is not neces-
sarily O( f (n) − g(n)).
R-4.18 Show that if d(n) is O( f (n)) and f (n) is O(g(n)), then d(n) is O(g(n)).
R-4.19 Show that O(max{ f (n), g(n)}) = O( f (n) + g(n)).
R-4.20 Show that f (n) is O(g(n)) if and only if g(n) is Ω( f (n)).
R-4.21 Show that if p(n) is a polynomial in n, then log p(n) is O(log n).
R-4.22 Show that (n + 1)5 is O(n5 ).
R-4.23 Show that 2n+1 is O(2n ).
R-4.24 Show that n is O(n log n).
R-4.25 Show that n2 is Ω(n log n).
R-4.26 Show that n log n is Ω(n).
R-4.27 Show that ⌈ f (n)⌉ is O( f (n)), if f (n) is a positive nondecreasing function that is
always greater than 1.
R-4.28 For each function f (n) and time t in the following table, determine the largest
size n of a problem P that can be solved in time t if the algorithm for solving P
takes f (n) microseconds (one entry is already completed).

1 Second 1 Hour 1 Month 1 Century

log n ≈ 10300000
n
n log n
n2
2n

R-4.29 Algorithm A executes an O(log n)-time computation for each entry of an array
storing n elements. What is its worst-case running time?
R-4.30 Given an n-element array X, Algorithm B chooses log n elements in X at random
and executes an O(n)-time calculation for each. What is the worst-case running
time of Algorithm B?
R-4.31 Given an n-element array X of integers, Algorithm C executes an O(n)-time com-
putation for each even number in X, and an O(log n)-time computation for each
odd number in X . What are the best-case and worst-case running times of Algo-
rithm C?
R-4.32 Given an n-element array X, Algorithm D calls Algorithm E on each element
X [i]. Algorithm E runs in O(i) time when it is called on element X [i]. What is
the worst-case running time of Algorithm D?

www.it-ebooks.info
4.5. Exercises 185
R-4.33 Al and Bob are arguing about their algorithms. Al claims his O(n log n)-time
method is always faster than Bob’s O(n2 )-time method. To settle the issue, they
perform a set of experiments. To Al’s dismay, they find that if n < 100, the
O(n2 )-time algorithm runs faster, and only when n ≥ 100 is the O(n log n)-time
one better. Explain how this is possible.
R-4.34 There is a well-known city (which will go nameless here) whose inhabitants have
the reputation of enjoying a meal only if that meal is the best they have ever
experienced in their life. Otherwise, they hate it. Assuming meal quality is
distributed uniformly across a person’s life, describe the expected number of
times inhabitants of this city are happy with their meals?

Creativity
C-4.35 Assuming it is possible to sort n numbers in O(n log n) time, show that it is pos-
sible to solve the three-way set disjointness problem in O(n log n) time.
C-4.36 Describe an efficient algorithm for finding the ten largest elements in an array of
size n. What is the running time of your algorithm?
C-4.37 Give an example of a positive function f (n) such that f (n) is neither O(n) nor
Ω(n).
C-4.38 Show that ∑ni=1 i2 is O(n3 ).
C-4.39 Show that ∑ni=1 i/2i < 2.
C-4.40 Determine the total number of grains of rice requested by the inventor of chess.
C-4.41 Show that logb f (n) is Θ(log f (n)) if b > 1 is a constant.
C-4.42 Describe an algorithm for finding both the minimum and maximum of n numbers
using fewer than 3n/2 comparisons.
C-4.43 Bob built a website and gave the URL only to his n friends, which he numbered
from 1 to n. He told friend number i that he/she can visit the website at most
i times. Now Bob has a counter, C, keeping track of the total number of visits
to the site (but not the identities of who visits). What is the minimum value for
C such that Bob can know that one of his friends has visited his/her maximum
allowed number of times?
C-4.44 Draw a visual justification of Proposition 4.3 analogous to that of Figure 4.3(b)
for the case when n is odd.
C-4.45 An array A contains n − 1 unique integers in the range [0, n − 1], that is, there is
one number from this range that is not in A. Design an O(n)-time algorithm for
finding that number. You are only allowed to use O(1) additional space besides
the array A itself.
C-4.46 Perform an asymptotic analysis of the insertion-sort algorithm given in Sec-
tion 3.1.2. What are the worst-case and best-case running times?

www.it-ebooks.info
186 Chapter 4. Algorithm Analysis
C-4.47 Communication security is extremely important in computer networks, and one
way many network protocols achieve security is to encrypt messages. Typical
cryptographic schemes for the secure transmission of messages over such net-
works are based on the fact that no efficient algorithms are known for factoring
large integers. Hence, if we can represent a secret message by a large prime
number p, we can transmit, over the network, the number r = p · q, where q > p
is another large prime number that acts as the encryption key. An eavesdropper
who obtains the transmitted number r on the network would have to factor r in
order to figure out the secret message p.
Using factoring to figure out a message is hard without knowing the encryption
key q. To understand why, consider the following naive factoring algorithm:
for (int p=2; p < r; p++)
if (r % p == 0)
return "The secret message is p!";
a. Suppose the eavesdropper’s computer can divide two 100-bit integers in
µs (1 millionth of a second). Estimate the worst-case time to decipher the
secret message p if the transmitted message r has 100 bits.
b. What is the worst-case time complexity of the above algorithm? Since the
input to the algorithm is just one large number r, assume that the input size
n is the number of bytes needed to store r, that is, n = ⌊(log2 r)/8⌋ + 1, and
that each division takes time O(n).
C-4.48 Al says he can prove that all sheep in a flock are the same color:
Base case: One sheep. It is clearly the same color as itself.
Induction step: A flock of n sheep. Take a sheep, a, out. The remaining n − 1
are all the same color by induction. Now put sheep a back in and take out a
different sheep, b. By induction, the n − 1 sheep (now with a) are all the same
color. Therefore, all the sheep in the flock are the same color. What is wrong
with Al’s “justification”?
C-4.49 Consider the following “justification” that the Fibonacci function, F(n) is O(n):
Base case (n ≤ 2): F(1) = 1 and F(2) = 2.
Induction step (n > 2): Assume claim true for n′ < n. Consider n. F(n) =
F(n − 2)+ F(n − 1). By induction, F(n − 2) is O(n − 2) and F(n − 1) is O(n − 1).
Then, F(n) is O((n − 2) + (n − 1)), by the identity presented in Exercise R-4.16.
Therefore, F(n) is O(n).
What is wrong with this “justification”?
C-4.50 Consider the Fibonacci function, F(n) (see Proposition 4.20). Show by induction
that F(n) is Ω((3/2)n ).
C-4.51 Let S be a set of n lines in the plane such that no two are parallel and no three
meet in the same point. Show, by induction, that the lines in S determine Θ(n2 )
intersection points.
C-4.52 Show that the summation ∑ni=1 log i is O(n log n).
C-4.53 Show that the summation ∑ni=1 log i is Ω(n log n).

www.it-ebooks.info
4.5. Exercises 187
C-4.54 Let p(x) be a polynomial of degree n, that is, p(x) = ∑ni=0 ai xi .

a. Describe a simple O(n2 )-time algorithm for computing p(x).

b. Describe an O(n log n)-time algorithm for computing p(x), based upon a
more efficient calculation of xi .
c. Now consider a rewriting of p(x) as

p(x) = a0 + x(a1 + x(a2 + x(a3 + · · · + x(an−1 + xan ) · · · ))),

which is known as Horner’s method. Using the big-Oh notation, charac-

terize the number of arithmetic operations this method executes.

C-4.55 An evil king has n bottles of wine, and a spy has just poisoned one of them.
Unfortunately, they do not know which one it is. The poison is very deadly; just
one drop diluted even a billion to one will still kill. Even so, it takes a full month
for the poison to take effect. Design a scheme for determining exactly which
one of the wine bottles was poisoned in just one month’s time while expending
O(log n) taste testers.

C-4.56 An array A contains n integers taken from the interval [0, 4n], with repetitions
allowed. Describe an efficient algorithm for determining an integer value k that
occurs the most often in A. What is the running time of your algorithm?

C-4.57 Given an array A of n positive integers, each represented with k = ⌈log n⌉ + 1

bits, describe an O(n)-time method for finding a k-bit integer not in A.

C-4.58 Argue why any solution to the previous problem must run in Ω(n) time.

C-4.59 Given an array A of n arbitrary integers, design an O(n)-time method for finding
an integer that cannot be formed as the sum of two integers in A.

Projects
P-4.60 Perform an experimental analysis of the two algorithms prefixAverage1 and pre-
fixAverage2, from Section 4.3.3. Visualize their running times as a function of
the input size with a log-log chart.

P-4.61 Perform an experimental analysis that compares the relative running times of the
methods shown in Code Fragment 4.12.

P-4.62 Perform an experimental analysis to test the hypothesis that Java’s Array.sort
method runs in O(n log n) time on average.

P-4.63 For each of the algorithms unique1 and unique2, which solve the element unique-
ness problem, perform an experimental analysis to determine the largest value of
n such that the given algorithm runs in one minute or less.

www.it-ebooks.info
188 Chapter 4. Algorithm Analysis

Chapter Notes
The big-Oh notation has prompted several comments about its proper use [18, 43, 59].
Knuth [60, 59] defines it using the notation f (n) = O(g(n)), but says this “equality” is only
“one way.” We have chosen to take a more standard view of equality and view the big-Oh
notation as a set, following Brassard [18]. The reader interested in studying average-case
analysis is referred to the book chapter by Vitter and Flajolet [93].

www.it-ebooks.info
Chapter

5 Recursion

Contents

5.1 Illustrative Examples . . . . . . . . . . . . . . . . . . . . . . 191

5.1.1 The Factorial Function . . . . . . . . . . . . . . . . . . . 191
5.1.2 Drawing an English Ruler . . . . . . . . . . . . . . . . . . 193
5.1.3 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . 196
5.1.4 File Systems . . . . . . . . . . . . . . . . . . . . . . . . . 198
5.2 Analyzing Recursive Algorithms . . . . . . . . . . . . . . . 202
5.3 Further Examples of Recursion . . . . . . . . . . . . . . . . 206
5.3.1 Linear Recursion . . . . . . . . . . . . . . . . . . . . . . . 206
5.3.2 Binary Recursion . . . . . . . . . . . . . . . . . . . . . . 211
5.3.3 Multiple Recursion . . . . . . . . . . . . . . . . . . . . . 212
5.4 Designing Recursive Algorithms . . . . . . . . . . . . . . . 214
5.5 Recursion Run Amok . . . . . . . . . . . . . . . . . . . . . 215
5.5.1 Maximum Recursive Depth in Java . . . . . . . . . . . . . 218
5.6 Eliminating Tail Recursion . . . . . . . . . . . . . . . . . . 219
5.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221

www.it-ebooks.info
190 Chapter 5. Recursion
One way to describe repetition within a computer program is the use of loops,
such as Java’s while-loop and for-loop constructs described in Section 1.5.2. An
entirely different way to achieve repetition is through a process known as recursion.
Recursion is a technique by which a method makes one or more calls to itself
during execution, or by which a data structure relies upon smaller instances of
the very same type of structure in its representation. There are many examples of
recursion in art and nature. For example, fractal patterns are naturally recursive. A
physical example of recursion used in art is in the Russian Matryoshka dolls. Each
doll is either made of solid wood, or is hollow and contains another Matryoshka
doll inside it.
In computing, recursion provides an elegant and powerful alternative for per-
forming repetitive tasks. In fact, a few programming languages (e.g., Scheme,
Smalltalk) do not explicitly support looping constructs and instead rely directly
on recursion to express repetition. Most modern programming languages support
functional recursion using the identical mechanism that is used to support tradi-
tional forms of method calls. When one invocation of the method makes a recursive
call, that invocation is suspended until the recursive call completes.
Recursion is an important technique in the study of data structures and algo-
rithms. We will use it prominently in several later chapters of this book (most
notably, Chapters 8 and 12). In this chapter, we begin with the following four illus-
trative examples of the use of recursion, providing a Java implementation for each.

• The factorial function (commonly denoted as n!) is a classic mathematical

function that has a natural recursive definition.

• An English ruler has a recursive pattern that is a simple example of a fractal

structure.

• Binary search is among the most important computer algorithms. It allows

us to efficiently locate a desired value in a data set with upwards of billions
of entries.

• The file system for a computer has a recursive structure in which directories
can be nested arbitrarily deeply within other directories. Recursive algo-
rithms are widely used to explore and manage these file systems.

We then describe how to perform a formal analysis of the running time of a

recursive algorithm, and we discuss some potential pitfalls when defining recur-
sions. In the balance of the chapter, we provide many more examples of recursive
algorithms, organized to highlight some common forms of design.

www.it-ebooks.info
5.1. Illustrative Examples 191

5.1 Illustrative Examples

5.1.1 The Factorial Function
To demonstrate the mechanics of recursion, we begin with a simple mathematical
example of computing the value of the factorial function. The factorial of a posi-
tive integer n, denoted n!, is defined as the product of the integers from 1 to n. If
n = 0, then n! is defined as 1 by convention. More formally, for any integer n ≥ 0,

1 if n = 0
n! =
n · (n − 1) · (n − 2) · · · 3 · 2 · 1 if n ≥ 1.

For example, 5! = 5 · 4 · 3 · 2 · 1 = 120. The factorial function is important because

it is known to equal the number of ways in which n distinct items can be arranged
into a sequence, that is, the number of permutations of n items. For example, the
three characters a, b, and c can be arranged in 3! = 3 · 2 · 1 = 6 ways: abc, acb,
bac, bca, cab, and cba.
There is a natural recursive definition for the factorial function. To see this,
observe that 5! = 5 · (4 · 3 · 2 · 1) = 5 · 4!. More generally, for a positive integer n,
we can define n! to be n · (n − 1)!. This recursive definition can be formalized as

1 if n = 0
n! =
n · (n − 1)! if n ≥ 1.
This definition is typical of many recursive definitions of functions. First, we
have one or more base cases, which refer to fixed values of the function. The above
definition has one base case stating that n! = 1 for n = 0. Second, we have one
or more recursive cases, which define the function in terms of itself. In the above
definition, there is one recursive case, which indicates that n! = n·(n−1)! for n ≥ 1.

A Recursive Implementation of the Factorial Function

Recursion is not just a mathematical notation; we can use recursion to design a Java
implementation of the factorial function, as shown in Code Fragment 5.1.
1 public static int factorial(int n) throws IllegalArgumentException {
2 if (n < 0)
3 throw new IllegalArgumentException( ); // argument must be nonnegative
4 else if (n == 0)
5 return 1; // base case
6 else
7 return n ∗ factorial(n−1); // recursive case
8 }
Code Fragment 5.1: A recursive implementation of the factorial function.

www.it-ebooks.info
192 Chapter 5. Recursion
This method does not use any explicit loops. Repetition is achieved through
repeated recursive invocations of the method. The process is finite because each
time the method is invoked, its argument is smaller by one, and when a base case
is reached, no further recursive calls are made.
We illustrate the execution of a recursive method using a recursion trace. Each
entry of the trace corresponds to a recursive call. Each new recursive method call
is indicated by a downward arrow to a new invocation. When the method returns,
an arrow showing this return is drawn and the return value may be indicated along-
side this arrow. An example of such a trace for the factorial function is shown in
Figure 5.1.

return 5 ∗ 24 = 120
factorial(5)
return 4 ∗ 6 = 24
factorial(4)
return 3 ∗ 2 = 6
factorial(3)
return 2 ∗ 1 = 2
factorial(2)
return 1 ∗ 1 = 1
factorial(1)
return 1
factorial(0)

Figure 5.1: A recursion trace for the call factorial(5).

A recursion trace closely mirrors a programming language’s execution of the

recursion. In Java, each time a method (recursive or otherwise) is called, a structure
known as an activation record or activation frame is created to store information
about the progress of that invocation of the method. This frame stores the parame-
ters and local variables specific to a given call of the method, and information about
which command in the body of the method is currently executing.
When the execution of a method leads to a nested method call, the execution
of the former call is suspended and its frame stores the place in the source code at
which the flow of control should continue upon return of the nested call. A new
frame is then created for the nested method call. This process is used both in the
standard case of one method calling a different method, or in the recursive case
where a method invokes itself. The key point is to have a separate frame for each
active call.

www.it-ebooks.info
5.1. Illustrative Examples 193

5.1.2 Drawing an English Ruler

In the case of computing the factorial function, there is no compelling reason for
preferring recursion over a direct iteration with a loop. As a more complex example
of the use of recursion, consider how to draw the markings of a typical English
ruler. For each inch, we place a tick with a numeric label. We denote the length
of the tick designating a whole inch as the major tick length. Between the marks
for whole inches, the ruler contains a series of minor ticks, placed at intervals of
1/2 inch, 1/4 inch, and so on. As the size of the interval decreases by half, the tick
length decreases by one. Figure 5.2 demonstrates several such rulers with varying
major tick lengths (although not drawn to scale).

---- 0 ----- 0 --- 0

- - -
-- -- --
- - -
--- --- --- 1
- - -
-- -- --
- - -
---- 1 ---- --- 2
- - -
-- -- --
- - -
--- --- --- 3
- -
-- --
- -
---- 2 ----- 1
(a) (b) (c)

Figure 5.2: Three sample outputs of an English ruler drawing: (a) a 2-inch ruler
with major tick length 4; (b) a 1-inch ruler with major tick length 5; (c) a 3-inch
ruler with major tick length 3.

A Recursive Approach to Ruler Drawing

The English ruler pattern is a simple example of a fractal, that is, a shape that has
a self-recursive structure at various levels of magnification. Consider the rule with
major tick length 5 shown in Figure 5.2(b). Ignoring the lines containing 0 and 1,
let us consider how to draw the sequence of ticks lying between these lines. The
central tick (at 1/2 inch) has length 4. Observe that the two patterns of ticks above
and below this central tick are identical, and each has a central tick of length 3.

www.it-ebooks.info
194 Chapter 5. Recursion
In general, an interval with a central tick length L ≥ 1 is composed of:
• An interval with a central tick length L − 1
• A single tick of length L
• An interval with a central tick length L − 1
Although it is possible to draw such a ruler using an iterative process (see Ex-
ercise P-5.29), the task is considerably easier to accomplish with recursion. Our
implementation consists of three methods, as shown in Code Fragment 5.2.
The main method, drawRuler, manages the construction of the entire ruler. Its
arguments specify the total number of inches in the ruler and the major tick length.
The utility method, drawLine, draws a single tick with a specified number of dashes
(and an optional integer label that is printed to the right of the tick).
The interesting work is done by the recursive drawInterval method. This method
draws the sequence of minor ticks within some interval, based upon the length of
the interval’s central tick. We rely on the intuition shown at the top of this page,
and with a base case when L = 0 that draws nothing. For L ≥ 1, the first and last
steps are performed by recursively calling drawInterval(L − 1). The middle step is
performed by calling method drawLine(L).
1 /∗∗ Draws an English ruler for the given number of inches and major tick length. ∗/
2 public static void drawRuler(int nInches, int majorLength) {
3 drawLine(majorLength, 0); // draw inch 0 line and label
4 for (int j = 1; j <= nInches; j++) {
5 drawInterval(majorLength − 1); // draw interior ticks for inch
6 drawLine(majorLength, j); // draw inch j line and label
7 }
8 }
9 private static void drawInterval(int centralLength) {
10 if (centralLength >= 1) { // otherwise, do nothing
11 drawInterval(centralLength − 1); // recursively draw top interval
12 drawLine(centralLength); // draw center tick line (without label)
13 drawInterval(centralLength − 1); // recursively draw bottom interval
14 }
15 }
16 private static void drawLine(int tickLength, int tickLabel) {
17 for (int j = 0; j < tickLength; j++)
18 System.out.print("-");
19 if (tickLabel >= 0)
20 System.out.print(" " + tickLabel);
21 System.out.print("\n");
22 }
23 /∗∗ Draws a line with the given tick length (but no label). ∗/
24 private static void drawLine(int tickLength) {
25 drawLine(tickLength, −1);
26 }
Code Fragment 5.2: A recursive implementation of a method that draws a ruler.

www.it-ebooks.info
5.1. Illustrative Examples 195

Illustrating Ruler Drawing Using a Recursion Trace

The execution of the recursive drawInterval method can be visualized using a re-
cursion trace. The trace for drawInterval is more complicated than in the factorial
example, however, because each instance makes two recursive calls. To illustrate
this, we will show the recursion trace in a form that is reminiscent of an outline for
a document. See Figure 5.3.

Output
drawInterval(3)

drawInterval(2)

drawInterval(1)

drawInterval(0)

drawLine(1)

drawInterval(0)

drawLine(2)

drawInterval(1)

drawInterval(0)

drawLine(1)

drawInterval(0)

drawLine(3)

drawInterval(2)
(previous pattern repeats)

Figure 5.3: A partial recursion trace for the call drawInterval(3). The second pattern
of calls for drawInterval(2) is not shown, but it is identical to the first.

www.it-ebooks.info
196 Chapter 5. Recursion

5.1.3 Binary Search

In this section, we describe a classic recursive algorithm, binary search, used to
efficiently locate a target value within a sorted sequence of n elements stored in
an array. This is among the most important of computer algorithms, and it is the
reason that we so often store data in sorted order (as in Figure 5.4).

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 4 5 7 8 9 12 14 17 19 22 25 27 28 33 37

Figure 5.4: Values stored in sorted order within an array. The numbers at top are
the indices.

When the sequence is unsorted, the standard approach to search for a target
value is to use a loop to examine every element, until either finding the target or
exhausting the data set. This algorithm is known as linear search, or sequential
search, and it runs in O(n) time (i.e., linear time) since every element is inspected
in the worst case.
When the sequence is sorted and indexable, there is a more efficient algorithm.
(For intuition, think about how you would accomplish this task by hand!) If we
consider an arbitrary element of the sequence with value v, we can be sure that all
elements prior to that in the sequence have values less than or equal to v, and that all
elements after that element in the sequence have values greater than or equal to v.
This observation allows us to quickly “home in” on a search target using a variant
of the children’s game “high-low.” We call an element of the sequence a candidate
if, at the current stage of the search, we cannot rule out that this item matches the
target. The algorithm maintains two parameters, low and high, such that all the
candidate elements have index at least low and at most high. Initially, low = 0 and
high = n − 1. We then compare the target value to the median candidate, that is,
the element with index
mid = ⌊(low + high)/2⌋ .
We consider three cases:
• If the target equals the median candidate, then we have found the item we are
looking for, and the search terminates successfully.
• If the target is less than the median candidate, then we recur on the first half
of the sequence, that is, on the interval of indices from low to mid − 1.
• If the target is greater than the median candidate, then we recur on the second
half of the sequence, that is, on the interval of indices from mid + 1 to high.
An unsuccessful search occurs if low > high, as the interval [low, high] is empty.

www.it-ebooks.info
5.1. Illustrative Examples 197
This algorithm is known as binary search. We give a Java implementation in
Code Fragment 5.3, and an illustration of the execution of the algorithm in Fig-
ure 5.5. Whereas sequential search runs in O(n) time, the more efficient binary
search runs in O(log n) time. This is a significant improvement, given that if n is
1 billion, log n is only 30. (We defer our formal analysis of binary search’s running
time to Proposition 5.2 in Section 5.2.)
1 /∗∗
2 ∗ Returns true if the target value is found in the indicated portion of the data array.
3 ∗ This search only considers the array portion from data[low] to data[high] inclusive.
4 ∗/
5 public static boolean binarySearch(int[ ] data, int target, int low, int high) {
6 if (low > high)
7 return false; // interval empty; no match
8 else {
9 int mid = (low + high) / 2;
10 if (target == data[mid])
11 return true; // found a match
12 else if (target < data[mid])
13 return binarySearch(data, target, low, mid − 1); // recur left of the middle
14 else
15 return binarySearch(data, target, mid + 1, high); // recur right of the middle
16 }
17 }
Code Fragment 5.3: An implementation of the binary search algorithm on a sorted
array.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 4 5 7 8 9 12 14 17 19 22 25 27 28 33 37

low mid high

2 4 5 7 8 9 12 14 17 19 22 25 27 28 33 37

low mid high

2 4 5 7 8 9 12 14 17 19 22 25 27 28 33 37

low mid high

2 4 5 7 8 9 12 14 17 19 22 25 27 28 33 37

low=mid=high

Figure 5.5: Example of a binary search for target value 22 on a sorted array with 16
elements.

www.it-ebooks.info
198 Chapter 5. Recursion

5.1.4 File Systems

Modern operating systems define file-system directories (also called “folders”) in

a recursive way. Namely, a file system consists of a top-level directory, and the
contents of this directory consists of files and other directories, which in turn can
contain files and other directories, and so on. The operating system allows directo-
ries to be nested arbitrarily deeply (as long as there is enough memory), although
by necessity there must be some base directories that contain only files, not fur-
ther subdirectories. A representation of a portion of such a file system is given in
Figure 5.6.

/user/rt/courses/

cs016/ cs252/

grades grades
homeworks/ programs/ projects/

hw1 hw2 hw3 pr1 pr2 pr3

papers/ demos/

buylow sellhigh market

Figure 5.6: A portion of a file system demonstrating a nested organization.

Given the recursive nature of the file-system representation, it should not come
as a surprise that many common behaviors of an operating system, such as copying
a directory or deleting a directory, are implemented with recursive algorithms. In
this section, we consider one such algorithm: computing the total disk usage for all
files and directories nested within a particular directory.

For illustration, Figure 5.7 portrays the disk space being used by all entries in
our sample file system. We differentiate between the immediate disk space used by
each entry and the cumulative disk space used by that entry and all nested features.
For example, the cs016 directory uses only 2K of immediate space, but a total of
249K of cumulative space.

www.it-ebooks.info
5.1. Illustrative Examples 199
5124K
/user/rt/courses/
1K
249K 4874K
cs016/ cs252/
2K 1K

10K 229K 4870K

grades homeworks/ programs/ projects/ grades
8K 1K 1K 1K 3K

82K 4787K
hw1 hw2 hw3 pr1 pr2 pr3 papers/ demos/
3K 2K 4K 57K 97K 74K 1K 1K

buylow sellhigh market

26K 55K 4786K

Figure 5.7: The same portion of a file system given in Figure 5.6, but with additional
annotations to describe the amount of disk space that is used. Within the icon for
each file or directory is the amount of space directly used by that artifact. Above
the icon for each directory is an indication of the cumulative disk space used by
that directory and all its (recursive) contents.

The cumulative disk space for an entry can be computed with a simple recursive
algorithm. It is equal to the immediate disk space used by the entry plus the sum
of the cumulative disk space usage of any entries that are stored directly within
the entry. For example, the cumulative disk space for cs016 is 249K because it
uses 2K itself, 8K cumulatively in grades, 10K cumulatively in homeworks, and
229K cumulatively in programs. Pseudocode for this algorithm is given in Code
Fragment 5.4.

Algorithm DiskUsage( path):

Input: A string designating a path to a file-system entry
Output: The cumulative disk space used by that entry and any nested entries
total = size( path) {immediate disk space used by the entry}
if path represents a directory then
for each child entry stored within directory path do
total = total + DiskUsage( child) {recursive call}
return total

Code Fragment 5.4: An algorithm for computing the cumulative disk space usage
nested at a file-system entry. We presume that method size returns the immediate
disk space of an entry.

www.it-ebooks.info
200 Chapter 5. Recursion
The java.io.File Class
To implement a recursive algorithm for computing disk usage in Java, we rely on
the java.io.File class. An instance of this class represents an abstract pathname in
the operating system and allows for properties of that operating system entry to be
queried. We will rely on the following methods of the class:
• new File(pathString) or new File(parentFile, childString)
A new File instance can be constructed either by providing the full path as
a string, or by providing an existing File instance that represents a directory
and a string that designates the name of a child entry within that directory.
• file.length( )
Returns the immediate disk usage (measured in bytes) for the operating sys-
tem entry represented by the File instance (e.g., /user/rt/courses).
• file.isDirectory( )
Returns true if the File instance represents a directory; false otherwise.
• file.list( )
Returns an array of strings designating the names of all entries within the
given directory. In our sample file system, if we call this method on the
File associated with path /user/rt/courses/cs016, it returns an array with
contents: {"grades", "homeworks", "programs"}.

Java Implementation
With use of the File class, we now convert the algorithm from Code Fragment 5.4
into the Java implementation of Code Fragment 5.5.

1 /∗∗
2 ∗ Calculates the total disk usage (in bytes) of the portion of the file system rooted
3 ∗ at the given path, while printing a summary akin to the standard 'du' Unix tool.
4 ∗/
5 public static long diskUsage(File root) {
6 long total = root.length( ); // start with direct disk usage
7 if (root.isDirectory( )) { // and if this is a directory,
8 for (String childname : root.list( )) { // then for each child
9 File child = new File(root, childname); // compose full path to child
10 total += diskUsage(child); // add child’s usage to total
11 }
12 }
13 System.out.println(total + "\t" + root); // descriptive output
14 return total; // return the grand total
15 }
Code Fragment 5.5: A recursive method for reporting disk usage of a file system.

www.it-ebooks.info
5.1. Illustrative Examples 201
Recursion Trace
To produce a different form of a recursion trace, we have included an extraneous
print statement within our Java implementation (line 13 of Code Fragment 5.5).
The precise format of that output intentionally mirrors the output that is produced
by a classic Unix/Linux utility named du (for “disk usage”). It reports the amount
of disk space used by a directory and all contents nested within, and can produce a
verbose report, as given in Figure 5.8.
When executed on the sample file system portrayed in Figure 5.7, our imple-
mentation of the diskUsage method produces the result given in Figure 5.8. During
the execution of the algorithm, exactly one recursive call is made for each entry in
the portion of the file system that is considered. Because each line is printed just
before returning from a recursive call, the lines of output reflect the order in which
the recursive calls are completed. Notice that it computes and reports the cumula-
tive disk space for a nested entry before computing and reporting the cumulative
disk space for the directory that contains it. For example, the recursive calls regard-
ing entries grades, homeworks, and programs are computed before the cumulative
total for the directory /user/rt/courses/cs016 that contains them.

8 /user/rt/courses/cs016/grades
3 /user/rt/courses/cs016/homeworks/hw1
2 /user/rt/courses/cs016/homeworks/hw2
4 /user/rt/courses/cs016/homeworks/hw3
10 /user/rt/courses/cs016/homeworks
57 /user/rt/courses/cs016/programs/pr1
97 /user/rt/courses/cs016/programs/pr2
74 /user/rt/courses/cs016/programs/pr3
229 /user/rt/courses/cs016/programs
249 /user/rt/courses/cs016
26 /user/rt/courses/cs252/projects/papers/buylow
55 /user/rt/courses/cs252/projects/papers/sellhigh
82 /user/rt/courses/cs252/projects/papers
4786 /user/rt/courses/cs252/projects/demos/market
4787 /user/rt/courses/cs252/projects/demos
4870 /user/rt/courses/cs252/projects
3 /user/rt/courses/cs252/grades
4874 /user/rt/courses/cs252
5124 /user/rt/courses/

Figure 5.8: A report of the disk usage for the file system shown in Figure 5.7, as
generated by our diskUsage method from Code Fragment 5.5, or equivalently by
the Unix/Linux command du with option -a (which lists both directories and files).

www.it-ebooks.info
202 Chapter 5. Recursion

5.2 Analyzing Recursive Algorithms

In Chapter 4, we introduced mathematical techniques for analyzing the efficiency
of an algorithm, based upon an estimate of the number of primitive operations that
are executed by the algorithm. We use notations such as big-Oh to summarize the
relationship between the number of operations and the input size for a problem. In
this section, we demonstrate how to perform this type of running-time analysis to
recursive algorithms.
With a recursive algorithm, we will account for each operation that is performed
based upon the particular activation of the method that manages the flow of control
at the time it is executed. Stated another way, for each invocation of the method,
we only account for the number of operations that are performed within the body of
that activation. We can then account for the overall number of operations that are
executed as part of the recursive algorithm by taking the sum, over all activations,
of the number of operations that take place during each individual activation. (As
an aside, this is also the way we analyze a nonrecursive method that calls other
methods from within its body.)
To demonstrate this style of analysis, we revisit the four recursive algorithms
presented in Sections 5.1.1 through 5.1.4: factorial computation, drawing an En-
glish ruler, binary search, and computation of the cumulative size of a file system.
In general, we may rely on the intuition afforded by a recursion trace in recogniz-
ing how many recursive activations occur, and how the parameterization of each
activation can be used to estimate the number of primitive operations that occur
within the body of that activation. However, each of these recursive algorithms has
a unique structure and form.

Computing Factorials

It is relatively easy to analyze the efficiency of our method for computing factorials,
as described in Section 5.1.1. A sample recursion trace for our factorial method was
given in Figure 5.1. To compute factorial(n), we see that there are a total of n + 1
activations, as the parameter decreases from n in the first call, to n − 1 in the second
call, and so on, until reaching the base case with parameter 0.
It is also clear, given an examination of the method body in Code Fragment 5.1,
that each individual activation of factorial executes a constant number of opera-
tions. Therefore, we conclude that the overall number of operations for computing
factorial(n) is O(n), as there are n + 1 activations, each of which accounts for O(1)
operations.

www.it-ebooks.info
5.2. Analyzing Recursive Algorithms 203
Drawing an English Ruler
In analyzing the English ruler application from Section 5.1.2, we consider the fun-
damental question of how many total lines of output are generated by an initial call
to drawInterval(c), where c denotes the center length. This is a reasonable bench-
mark for the overall efficiency of the algorithm as each line of output is based upon
a call to the drawLine utility, and each recursive call to drawInterval with nonzero
parameter makes exactly one direct call to drawLine.
Some intuition may be gained by examining the source code and the recur-
sion trace. We know that a call to drawInterval(c) for c > 0 spawns two calls to
drawInterval(c − 1) and a single call to drawLine. We will rely on this intuition to
prove the following claim.

Proposition 5.1: For c ≥ 0, a call to drawInterval(c) results in precisely 2c − 1

lines of output.

Justification: We provide a formal proof of this claim by induction (see Sec-

tion 4.4.3). In fact, induction is a natural mathematical technique for proving the
correctness and efficiency of a recursive process. In the case of the ruler, we note
that an application of drawInterval(0) generates no output, and that 20 −1 = 1−1 =
0. This serves as a base case for our claim.
More generally, the number of lines printed by drawInterval(c) is one more
than twice the number generated by a call to drawInterval(c − 1), as one center line
is printed between two such recursive calls. By induction, we have that the number
of lines is thus 1 + 2 · (2c−1 − 1) = 1 + 2c − 2 = 2c − 1.
This proof is indicative of a more mathematically rigorous tool, known as a
recurrence equation, that can be used to analyze the running time of a recursive
algorithm. That technique is discussed in Section 12.1.4, in the context of recursive
sorting algorithms.

Performing a Binary Search

When considering the running time of the binary search algorithm, as presented
in Section 5.1.3, we observe that a constant number of primitive operations are
executed during each recursive call of the binary search method. Hence, the running
time is proportional to the number of recursive calls performed. We will show that
at most ⌊log n⌋ + 1 recursive calls are made during a binary search of a sequence
having n elements, leading to the following claim.
Proposition 5.2: The binary search algorithm runs in O(log n) time for a sorted
array with n elements.

www.it-ebooks.info
204 Chapter 5. Recursion
Justification: To prove this claim, a crucial fact is that with each recursive call
the number of candidate elements still to be searched is given by the value
high − low + 1.
Moreover, the number of remaining candidates is reduced by at least one-half with
each recursive call. Specifically, from the definition of mid, the number of remain-
ing candidates is either
 
low + high high − low + 1
(mid − 1) − low + 1 = − low ≤
2 2
or  
low + high high − low + 1
high − (mid + 1) + 1 = high − ≤ .
2 2
Initially, the number of candidates is n; after the first call in a binary search, it is
at most n/2; after the second call, it is at most n/4; and so on. In general, after
the j th call in a binary search, the number of candidate elements remaining is at
most n/2 j . In the worst case (an unsuccessful search), the recursive calls stop when
there are no more candidate elements. Hence, the maximum number of recursive
calls performed, is the smallest integer r such that
n
< 1.
2r
In other words (recalling that we omit a logarithm’s base when it is 2), r is the
smallest integer such that r > log n. Thus, we have
r = ⌊log n⌋ + 1,

which implies that binary search runs in O(log n) time.

Computing Disk Space Usage

Our final recursive algorithm from Section 5.1 was that for computing the overall
disk space usage in a specified portion of a file system. To characterize the “prob-
lem size” for our analysis, we let n denote the number of file-system entries in the
portion of the file system that is considered. (For example, the file system portrayed
in Figure 5.6 has n = 19 entries.)
To characterize the cumulative time spent for an initial call to diskUsage, we
must analyze the total number of recursive invocations that are made, as well as the
number of operations that are executed within those invocations.
We begin by showing that there are precisely n recursive invocations of the
method, in particular, one for each entry in the relevant portion of the file system.
Intuitively, this is because a call to diskUsage for a particular entry e of the file
system is only made from within the for loop of Code Fragment 5.5 when process-
ing the entry for the unique directory that contains e, and that entry will only be
explored once.

www.it-ebooks.info
5.2. Analyzing Recursive Algorithms 205
To formalize this argument, we can define the nesting level of each entry such
that the entry on which we begin has nesting level 0, entries stored directly within
it have nesting level 1, entries stored within those entries have nesting level 2, and
so on. We can prove by induction that there is exactly one recursive invocation of
diskUsage upon each entry at nesting level k. As a base case, when k = 0, the only
recursive invocation made is the initial one. As the inductive step, once we know
there is exactly one recursive invocation for each entry at nesting level k, we can
claim that there is exactly one invocation for each entry e at nesting level k + 1,
made within the for loop for the entry at level k that contains e.
Having established that there is one recursive call for each entry of the file
system, we return to the question of the overall computation time for the algorithm.
It would be great if we could argue that we spend O(1) time in any single invocation
of the method, but that is not the case. While there is a constant number of steps
reflected in the call to root.length( ) to compute the disk usage directly at that entry,
when the entry is a directory, the body of the diskUsage method includes a for loop
that iterates over all entries that are contained within that directory. In the worst
case, it is possible that one entry includes n − 1 others.
Based on this reasoning, we could conclude that there are O(n) recursive calls,
each of which runs in O(n) time, leading to an overall running time that is O(n2 ).
While this upper bound is technically true, it is not a tight upper bound. Remark-
ably, we can prove the stronger bound that the recursive algorithm for diskUsage
completes in O(n) time! The weaker bound was pessimistic because it assumed
a worst-case number of entries for each directory. While it is possible that some
directories contain a number of entries proportional to n, they cannot all contain
that many. To prove the stronger claim, we choose to consider the overall number
of iterations of the for loop across all recursive calls. We claim there are precisely
n − 1 such iterations of that loop overall. We base this claim on the fact that each
iteration of that loop makes a recursive call to diskUsage, and yet we have already
concluded that there are a total of n calls to diskUsage (including the original call).
We therefore conclude that there are O(n) recursive calls, each of which uses O(1)
time outside the loop, and that the overall number of operations due to the loop
is O(n). Summing all of these bounds, the overall number of operations is O(n).
The argument we have made is more advanced than with the earlier examples
of recursion. The idea that we can sometimes get a tighter bound on a series of
operations by considering the cumulative effect, rather than assuming that each
achieves a worst case is a technique called amortization; we will see another ex-
ample of such analysis in Section 7.2.3. Furthermore, a file system is an implicit
example of a data structure known as a tree, and our disk usage algorithm is really
a manifestation of a more general algorithm known as a tree traversal. Trees will
be the focus of Chapter 8, and our argument about the O(n) running time of the
disk usage algorithm will be generalized for tree traversals in Section 8.4.

www.it-ebooks.info
206 Chapter 5. Recursion

5.3 Further Examples of Recursion

In this section, we provide additional examples of the use of recursion. We organize
our presentation by considering the maximum number of recursive calls that may
be started from within the body of a single activation.
• If a recursive call starts at most one other, we call this a linear recursion.
• If a recursive call may start two others, we call this a binary recursion.
• If a recursive call may start three or more others, this is multiple recursion.

5.3.1 Linear Recursion

If a recursive method is designed so that each invocation of the body makes at
most one new recursive call, this is know as linear recursion. Of the recursions
we have seen so far, the implementation of the factorial method (Section 5.1.1) is a
clear example of linear recursion. More interestingly, the binary search algorithm
(Section 5.1.3) is also an example of linear recursion, despite the term “binary”
in the name. The code for binary search (Code Fragment 5.3) includes a case
analysis, with two branches that lead to a further recursive call, but only one branch
is followed during a particular execution of the body.
A consequence of the definition of linear recursion is that any recursion trace
will appear as a single sequence of calls, as we originally portrayed for the factorial
method in Figure 5.1 of Section 5.1.1. Note that the linear recursion terminol-
ogy reflects the structure of the recursion trace, not the asymptotic analysis of the
running time; for example, we have seen that binary search runs in O(log n) time.

Summing the Elements of an Array Recursively

Linear recursion can be a useful tool for processing a sequence, such as a Java array.
Suppose, for example, that we want to compute the sum of an array of n integers.
We can solve this summation problem using linear recursion by observing that if
n = 0 the sum is trivially 0, and otherwise it is the sum of the first n − 1 integers in
the array plus the last value in the array. (See Figure 5.9.)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
4 3 6 2 8 9 3 2 8 5 1 7 2 8 3 7

Figure 5.9: Computing the sum of a sequence recursively, by adding the last number
to the sum of the first n − 1.

www.it-ebooks.info
5.3. Further Examples of Recursion 207
A recursive algorithm for computing the sum of an array of integers based on
this intuition is implemented in Code Fragment 5.6.

1 /∗∗ Returns the sum of the first n integers of the given array. ∗/
2 public static int linearSum(int[ ] data, int n) {
3 if (n == 0)
4 return 0;
5 else
6 return linearSum(data, n−1) + data[n−1];
7 }

Code Fragment 5.6: Summing an array of integers using linear recursion.

A recursion trace of the linearSum method for a small example is given in

Figure 5.10. For an input of size n, the linearSum algorithm makes n + 1 method
calls. Hence, it will take O(n) time, because it spends a constant amount of time
performing the nonrecursive part of each call. Moreover, we can also see that the
memory space used by the algorithm (in addition to the array) is also O(n), as we
use a constant amount of memory space for each of the n + 1 frames in the trace at
the time we make the final recursive call (with n = 0).

return 15 + data[4] = 15 + 8 = 23
linearSum(data, 5)
return 13 + data[3] = 13 + 2 = 15
linearSum(data, 4)
return 7 + data[2] = 7 + 6 = 13
linearSum(data, 3)
return 4 + data[1] = 4 + 3 = 7
linearSum(data, 2)
return 0 + data[0] = 0 + 4 = 4
linearSum(data, 1)
return 0
linearSum(data, 0)

Figure 5.10: Recursion trace for an execution of linearSum(data, 5) with input

parameter data = 4, 3, 6, 2, 8.

www.it-ebooks.info
208 Chapter 5. Recursion
Reversing a Sequence with Recursion

Next, let us consider the problem of reversing the n elements of an array, so that
the first element becomes the last, the second element becomes second to the last,
and so on. We can solve this problem using linear recursion, by observing that the
reversal of a sequence can be achieved by swapping the first and last elements and
then recursively reversing the remaining elements. We present an implementation
of this algorithm in Code Fragment 5.7, using the convention that the first time we
call this algorithm we do so as reverseArray(data, 0, n−1).

1 /∗∗ Reverses the contents of subarray data[low] through data[high] inclusive. ∗/

2 public static void reverseArray(int[ ] data, int low, int high) {
3 if (low < high) { // if at least two elements in subarray
4 int temp = data[low]; // swap data[low] and data[high]
5 data[low] = data[high];
6 data[high] = temp;
7 reverseArray(data, low + 1, high − 1); // recur on the rest
8 }
9 }
Code Fragment 5.7: Reversing the elements of an array using linear recursion.

We note that whenever a recursive call is made, there will be two fewer elements
in the relevant portion of the array. (See Figure 5.11.) Eventually a base case is
reached when the condition low < high fails, either because low == high in the
case that n is odd, or because low == high + 1 in the case that n is even.
The above argument implies that the recursive
  algorithm of Code Fragment 5.7
is guaranteed to terminate after a total of 1 + 2n recursive calls. Because each call
involves a constant amount of work, the entire process runs in O(n) time.
0 1 2 3 4 5 6 7
4 3 6 2 7 8 9 5

5 3 6 2 7 8 9 4

5 9 6 2 7 8 3 4

5 9 8 2 7 6 3 4

5 9 8 7 2 6 3 4

Figure 5.11: A trace of the recursion for reversing a sequence. The highlighted
portion has yet to be reversed.

www.it-ebooks.info
5.3. Further Examples of Recursion 209
Recursive Algorithms for Computing Powers
As another interesting example of the use of linear recursion, we consider the prob-
lem of raising a number x to an arbitrary nonnegative integer n. That is, we wish
to compute the power function, defined as power(x, n) = xn . (We use the name
“power” for this discussion, to differentiate from the pow method of the Math class,
which provides such functionality.) We will consider two different recursive for-
mulations for the problem that lead to algorithms with very different performance.
A trivial recursive definition follows from the fact that xn = x · xn−1 for n > 0.

1 if n = 0
power(x, n) =
x · power(x, n − 1) otherwise.
This definition leads to a recursive algorithm shown in Code Fragment 5.8.
1 /∗∗ Computes the value of x raised to the nth power, for nonnegative integer n. ∗/
2 public static double power(double x, int n) {
3 if (n == 0)
4 return 1;
5 else
6 return x ∗ power(x, n−1);
7 }
Code Fragment 5.8: Computing the power function using trivial recursion.

A recursive call to this version of power(x, n) runs in O(n) time. Its recursion
trace has structure very similar to that of the factorial function from Figure 5.1,
with the parameter decreasing by one with each call, and constant work performed
at each of n + 1 levels.
However, there is a much faster way to compute the power function   using an
alternative definition that employs a squaring technique. Let k = n2 denote the
floor of the integer division (equivalent to n/2 in Java when n is an int). We consider

2  
2  n  2
the expression xk . When n is even, n2 = 2n and therefore xk = x 2 = xn .
 n  n−1


k 2 = xn−1 , and therefore xn = xk 2 · x, just as
When n is odd,
2 = 2 and x
213 = 26 · 26 · 2. This analysis leads to the following recursive definition:


 1 if n = 0
 n 

2
power(x, n) = power x, 2 · x if n > 0 is odd
 power x,  n 

2

if n > 0 is even
2

If we were
 to implement   this recursion making two recursive calls to compute
power(x, 2n ) · power(x, n2 ), a trace of the recursion would demonstrate O(n)  
calls. We can perform significantly fewer operations by computing power(x, n2 )
and storing it in a variable as a partial result, and then multiplying it by itself. An
implementation based on this recursive definition is given in Code Fragment 5.9.

www.it-ebooks.info
210 Chapter 5. Recursion
1 /∗∗ Computes the value of x raised to the nth power, for nonnegative integer n. ∗/
2 public static double power(double x, int n) {
3 if (n == 0)
4 return 1;
5 else {
6 double partial = power(x, n/2); // rely on truncated division of n
7 double result = partial ∗ partial;
8 if (n % 2 == 1) // if n odd, include extra factor of x
9 result ∗= x;
10 return result;
11 }
12 }
Code Fragment 5.9: Computing the power function using repeated squaring.

To illustrate the execution of our improved algorithm, Figure 5.12 provides a

recursion trace of the computation power(2, 13).

return 64 ∗ 64 ∗ 2 = 8192
power(2, 13)
return 8 ∗ 8 = 64
power(2, 6)
return 2 ∗ 2 ∗ 2 = 8
power(2, 3)
return 1 ∗ 1 ∗ 2 = 2
power(2, 1)
return 1
power(2, 0)

Figure 5.12: Recursion trace for an execution of power(2, 13).

To analyze the running time of the revised algorithm, we observe that the ex-
ponent in each recursive call of method power(x,n) is at most half of the preceding
exponent. As we saw with the analysis of binary search, the number of times that
we can divide n by two before getting to one or less is O(log n). Therefore, our new
formulation of power results in O(log n) recursive calls. Each individual activation
of the method uses O(1) operations (excluding the recursive call), and so the total
number of operations for computing power(x,n) is O(log n). This is a significant
improvement over the original O(n)-time algorithm.
The improved version also provides significant saving in reducing the memory
usage. The first version has a recursive depth of O(n), and therefore, O(n) frames
are simultaneously stored in memory. Because the recursive depth of the improved
version is O(log n), its memory usage is O(log n) as well.

www.it-ebooks.info
5.3. Further Examples of Recursion 211

5.3.2 Binary Recursion

When a method makes two recursive calls, we say that it uses binary recursion.
We have already seen an example of binary recursion when drawing the English
ruler (Section 5.1.2). As another application of binary recursion, let us revisit the
problem of summing the n integers of an array. Computing the sum of one or zero
values is trivial. With two or more values, we can recursively compute the sum of
the first half, and the sum of the second half, and add those sums together. Our
implementation of such an algorithm, in Code Fragment 5.10, is initially invoked
as binarySum(data, 0, n−1).

1 /∗∗ Returns the sum of subarray data[low] through data[high] inclusive. ∗/

2 public static int binarySum(int[ ] data, int low, int high) {
3 if (low > high) // zero elements in subarray
4 return 0;
5 else if (low == high) // one element in subarray
6 return data[low];
7 else {
8 int mid = (low + high) / 2;
9 return binarySum(data, low, mid) + binarySum(data, mid+1, high);
10 }
11 }
Code Fragment 5.10: Summing the elements of a sequence using binary recursion.

To analyze algorithm binarySum, we consider, for simplicity, the case where

n is a power of two. Figure 5.13 shows the recursion trace of an execution of
binarySum(data, 0, 7). We label each box with the values of parameters low and
high for that call. The size of the range is divided in half at each recursive call,
and so the depth of the recursion is 1 + log2 n. Therefore, binarySum uses O(log n)
amount of additional space, which is a big improvement over the O(n) space used
by the linearSum method of Code Fragment 5.6. However, the running time of
binarySum is O(n), as there are 2n − 1 method calls, each requiring constant time.

0,7

0,3 4,7

0,1 2,3 4,5 6,7

0,0 1,1 2,2 3,3 4,4 5,5 6,6 7,7

Figure 5.13: Recursion trace for the execution of binarySum(data, 0, 7).

www.it-ebooks.info
212 Chapter 5. Recursion

5.3.3 Multiple Recursion

Generalizing from binary recursion, we define multiple recursion as a process in
which a method may make more than two recursive calls. Our recursion for an-
alyzing the disk space usage of a file system (see Section 5.1.4) is an example of
multiple recursion, because the number of recursive calls made during one invoca-
tion was equal to the number of entries within a given directory of the file system.
Another common application of multiple recursion is when we want to enumer-
ate various configurations in order to solve a combinatorial puzzle. For example,
the following are all instances of what are known as summation puzzles:

pot + pan = bib

dog + cat = pig
boy + girl = baby

To solve such a puzzle, we need to assign a unique digit (that is, 0, 1, . . . , 9) to each
letter in the equation, in order to make the equation true. Typically, we solve such
a puzzle by using our human observations of the particular puzzle we are trying to
solve to eliminate configurations (that is, possible partial assignments of digits to
letters) until we can work through the feasible configurations that remain, testing
for the correctness of each one.
If the number of possible configurations is not too large, however, we can use
a computer to simply enumerate all the possibilities and test each one, without em-
ploying any human observations. Such an algorithm can use multiple recursion
to work through the configurations in a systematic way. To keep the description
general enough to be used with other puzzles, we consider an algorithm that enu-
merates and tests all k-length sequences, without repetitions, chosen from a given
universe U . We show pseudocode for such an algorithm in Code Fragment 5.11,
building the sequence of k elements with the following steps:
1. Recursively generating the sequences of k − 1 elements
2. Appending to each such sequence an element not already contained in it.
Throughout the execution of the algorithm, we use a set U to keep track of the
elements not contained in the current sequence, so that an element e has not been
used yet if and only if e is in U .
Another way to look at the algorithm of Code Fragment 5.11 is that it enumer-
ates every possible size-k ordered subset of U , and tests each subset for being a
possible solution to our puzzle.
For summation puzzles, U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} and each position in the
sequence corresponds to a given letter. For example, the first position could stand
for b, the second for o, the third for y, and so on.

www.it-ebooks.info
5.3. Further Examples of Recursion 213

Algorithm PuzzleSolve(k, S, U ):
Input: An integer k, sequence S, and set U
Output: An enumeration of all k-length extensions to S using elements in U
without repetitions
for each e in U do
Add e to the end of S
Remove e from U {e is now being used}
if k == 1 then
Test whether S is a configuration that solves the puzzle
if S solves the puzzle then
add S to output {a solution}
else
PuzzleSolve(k − 1, S, U ) {a recursive call}
Remove e from the end of S
Add e back to U {e is now considered as unused}

Code Fragment 5.11: Solving a combinatorial puzzle by enumerating and testing

all possible configurations.

In Figure 5.14, we show a recursion trace of a call to PuzzleSolve(3, S, U ),

where S is empty and U = {a, b, c}. During the execution, all the permutations
of the three characters are generated and tested. Note that the initial call makes
three recursive calls, each of which in turn makes two more. If we had executed
PuzzleSolve(3, S, U ) on a set U consisting of four elements, the initial call would
have made four recursive calls, each of which would have a trace looking like the
one in Figure 5.14.

initial call

PuzzleSolve(3, ( ), {a,b,c})

PuzzleSolve(2, a, {b,c}) PuzzleSolve(2, b, {a,c}) PuzzleSolve(2, c, {a,b})

PuzzleSolve(1, ab, {c}) PuzzleSolve(1, ba, {c}) PuzzleSolve(1, ca, {b})

abc bac cab

PuzzleSolve(1, ac, {b}) PuzzleSolve(1, bc, {a}) PuzzleSolve(1, cb, {a})

acb bca cba

Figure 5.14: Recursion trace for an execution of PuzzleSolve(3, S, U ), where S is

empty and U = {a, b, c}. This execution generates and tests all permutations of a, b,
and c. We show the permutations generated directly below their respective boxes.

www.it-ebooks.info
214 Chapter 5. Recursion

5.4 Designing Recursive Algorithms

An algorithm that uses recursion typically has the following form:

• Test for base cases. We begin by testing for a set of base cases (there should
be at least one). These base cases should be defined so that every possible
chain of recursive calls will eventually reach a base case, and the handling of
each base case should not use recursion.

• Recur. If not a base case, we perform one or more recursive calls. This recur-
sive step may involve a test that decides which of several possible recursive
calls to make. We should define each possible recursive call so that it makes
progress towards a base case.

Parameterizing a Recursion

To design a recursive algorithm for a given problem, it is useful to think of the

different ways we might define subproblems that have the same general structure
as the original problem. If one has difficulty finding the repetitive structure needed
to design a recursive algorithm, it is sometimes useful to work out the problem on
a few concrete examples to see how the subproblems should be defined.
A successful recursive design sometimes requires that we redefine the origi-
nal problem to facilitate similar-looking subproblems. Often, this involved repa-
rameterizing the signature of the method. For example, when performing a bi-
nary search in an array, a natural method signature for a caller would appear as
binarySearch(data, target). However, in Section 5.1.3, we defined our method
with calling signature binarySearch(data, target, low, high), using the additional
parameters to demarcate subarrays as the recursion proceeds. This change in pa-
rameterization is critical for binary search. Several other examples in this chapter
(e.g., reverseArray, linearSum, binarySum) also demonstrated the use of additional
parameters in defining recursive subproblems.
If we wish to provide a cleaner public interface to an algorithm without expos-
ing the user to the recursive parameterization, a standard technique is to make the
recursive version private, and to introduce a cleaner public method (that calls the
private one with appropriate parameters). For example, we might offer the follow-
ing simpler version of binarySearch for public use:
/∗∗ Returns true if the target value is found in the data array. ∗/
public static boolean binarySearch(int[ ] data, int target) {
return binarySearch(data, target, 0, data.length − 1); // use parameterized version
}

www.it-ebooks.info
5.5. Recursion Run Amok 215

5.5 Recursion Run Amok

Although recursion is a very powerful tool, it can easily be misused in various
ways. In this section, we examine several cases in which a poorly implemented re-
cursion causes drastic inefficiency, and we discuss some strategies for recognizing
and avoid such pitfalls.
We begin by revisiting the element uniqueness problem, defined on page 174
of Section 4.3.3. We can use the following recursive formulation to determine if
all n elements of a sequence are unique. As a base case, when n = 1, the elements
are trivially unique. For n ≥ 2, the elements are unique if and only if the first n − 1
elements are unique, the last n − 1 items are unique, and the first and last elements
are different (as that is the only pair that was not already checked as a subcase). A
recursive implementation based on this idea is given in Code Fragment 5.12, named
unique3 (to differentiate it from unique1 and unique2 from Chapter 4).
1 /∗∗ Returns true if there are no duplicate values from data[low] through data[high].∗/
2 public static boolean unique3(int[ ] data, int low, int high) {
3 if (low >= high) return true; // at most one item
4 else if (!unique3(data, low, high−1)) return false; // duplicate in first n−1
5 else if (!unique3(data, low+1, high)) return false; // duplicate in last n−1
6 else return (data[low] != data[high]); // do first and last differ?
7 }

Code Fragment 5.12: Recursive unique3 for testing element uniqueness.

Unfortunately, this is a terribly inefficient use of recursion. The nonrecursive

part of each call uses O(1) time, so the overall running time will be proportional to
the total number of recursive invocations. To analyze the problem, we let n denote
the number of entries under consideration, that is, let n = 1 + high − low.
If n = 1, then the running time of unique3 is O(1), since there are no recursive
calls for this case. In the general case, the important observation is that a single call
to unique3 for a problem of size n may result in two recursive calls on problems of
size n − 1. Those two calls with size n − 1 could in turn result in four calls (two
each) with a range of size n − 2, and thus eight calls with size n − 3 and so on.
Thus, in the worst case, the total number of method calls is given by the geometric
summation
1 + 2 + 4 + · · · + 2n−1 ,

which is equal to 2n − 1 by Proposition 4.5. Thus, the running time of method

unique3 is O(2n ). This is an incredibly inefficient method for solving the ele-
ment uniqueness problem. Its inefficiency comes not from the fact that it uses
recursion—it comes from the fact that it uses recursion poorly, which is something
we address in Exercise C-5.12.

www.it-ebooks.info
216 Chapter 5. Recursion
An Inefficient Recursion for Computing Fibonacci Numbers
In Section 2.2.3, we introduced a process for generating the progression of Fi-
bonacci numbers, which can be defined recursively as follows:

F0 = 0
F1 = 1
Fn = Fn−2 + Fn−1 for n > 1.
Ironically, a recursive implementation based directly on this definition results in the
method fibonacciBad shown in Code Fragment 5.13, which computes a Fibonacci
number by making two recursive calls in each non-base case.

1 /∗∗ Returns the nth Fibonacci number (inefficiently). ∗/

2 public static long fibonacciBad(int n) {
3 if (n <= 1)
4 return n;
5 else
6 return fibonacciBad(n−2) + fibonacciBad(n−1);
7 }
Code Fragment 5.13: Computing the n th Fibonacci number using binary recursion.

Unfortunately, such a direct implementation of the Fibonacci formula results

in a terribly inefficient method. Computing the n th Fibonacci number in this way
requires an exponential number of calls to the method. Specifically, let cn denote
the number of calls performed in the execution of fibonacciBad(n). Then, we have
the following values for the cn ’s:

c0 = 1
c1 = 1
c2 = 1 + c0 + c1 = 1 + 1 + 1 = 3
c3 = 1 + c1 + c2 = 1 + 1 + 3 = 5
c4 = 1 + c2 + c3 = 1 + 3 + 5 = 9
c5 = 1 + c3 + c4 = 1 + 5 + 9 = 15
c6 = 1 + c4 + c5 = 1 + 9 + 15 = 25
c7 = 1 + c5 + c6 = 1 + 15 + 25 = 41
c8 = 1 + c6 + c7 = 1 + 25 + 41 = 67

If we follow the pattern forward, we see that the number of calls more than doubles
for each two consecutive indices. That is, c4 is more than twice c2 , c5 is more than
twice c3 , c6 is more than twice c4 , and so on. Thus, cn > 2n/2 , which means that
fibonacciBad(n) makes a number of calls that is exponential in n.

www.it-ebooks.info
5.5. Recursion Run Amok 217
An Efficient Recursion for Computing Fibonacci Numbers

We were tempted into using the bad recursive formulation because of the way the
n th Fibonacci number, Fn , depends on the two previous values, Fn−2 and Fn−1 . But
notice that after computing Fn−2 , the call to compute Fn−1 requires its own recursive
call to compute Fn−2 , as it does not have knowledge of the value of Fn−2 that was
computed at the earlier level of recursion. That is duplicative work. Worse yet, both
of those calls will need to (re)compute the value of Fn−3 , as will the computation
of Fn−1 . This snowballing effect is what leads to the exponential running time of
fibonacciBad.

We can compute Fn much more efficiently using a recursion in which each

invocation makes only one recursive call. To do so, we need to redefine the expec-
tations of the method. Rather than having the method return a single value, which
is the n th Fibonacci number, we define a recursive method that returns an array with
two consecutive Fibonacci numbers {Fn , Fn−1 }, using the convention F−1 = 0. Al-
though it seems to be a greater burden to report two consecutive Fibonacci numbers
instead of one, passing this extra information from one level of the recursion to the
next makes it much easier to continue the process. (It allows us to avoid having
to recompute the second value that was already known within the recursion.) An
implementation based on this strategy is given in Code Fragment 5.14.

1 /∗∗ Returns array containing the pair of Fibonacci numbers, F(n) and F(n−1). ∗/
2 public static long[ ] fibonacciGood(int n) {
3 if (n <= 1) {
4 long[ ] answer = {n, 0};
5 return answer;
6 } else {
7 long[ ] temp = fibonacciGood(n − 1); // returns {Fn−1, Fn−2 }
8 long[ ] answer = {temp[0] + temp[1], temp[0]}; // we want {Fn , Fn−1 }
9 return answer;
10 }
11 }
Code Fragment 5.14: Computing the n th Fibonacci number using linear recursion.

In terms of efficiency, the difference between the bad and good recursions for
this problem is like night and day. The fibonacciBad method uses exponential
time. We claim that the execution of method fibonacciGood(n) runs in O(n) time.
Each recursive call to fibonacciGood decreases the argument n by 1; therefore, a
recursion trace includes a series of n method calls. Because the nonrecursive work
for each call uses constant time, the overall computation executes in O(n) time.

www.it-ebooks.info
218 Chapter 5. Recursion

5.5.1 Maximum Recursive Depth in Java

Another danger in the misuse of recursion is known as infinite recursion. If each
recursive call makes another recursive call, without ever reaching a base case, then
we have an infinite series of such calls. This is a fatal error. An infinite recursion
can quickly swamp computing resources, not only due to rapid use of the CPU,
but because each successive call creates a frame requiring additional memory. A
blatant example of an ill-formed recursion is the following:
1 /∗∗ Don't call this (infinite) version. ∗/
2 public static int fibonacci(int n) {
3 return fibonacci(n); // After all Fn does equal Fn
4 }
However, there are far more subtle errors that can lead to an infinite recursion.
Revisiting our implementation of binary search (Code Fragment 5.3), when we
make a recursive call on the right portion of the sequence (line 15), we specify the
subarray from index mid+1 to high. Had that line instead been written as
return binarySearch(data, target, mid, high); // sending mid, not mid+1
this could result in an infinite recursion. In particular, when searching a range of
two elements, it becomes possible to make a recursive call on the identical range.
A programmer should ensure that each recursive call is in some way progress-
ing toward a base case (for example, by having a parameter value that decreases
with each call). To combat against infinite recursions, the designers of Java made
an intentional decision to limit the overall space used to store activation frames
for simultaneously active method calls. If this limit is reached, the Java Virtual
Machine throws a StackOverflowError. (We will further discuss the “stack” data
structure in Section 6.1.) The precise value of this limit depends upon the Java
installation, but a typical value might allow upward of 1000 simultaneous calls.
For many applications of recursion, allowing up to 1000 nested calls suffices.
For example, our binarySearch method (Section 5.1.3) has O(log n) recursive depth,
and so for the default recursive limit to be reached, there would need to be 21000
elements (far, far more than the estimated number of atoms in the universe). How-
ever, we have seen several linear recursions that have recursive depth proportional
to n. Java’s limit on the recursive depth might disrupt such computations.
It is possible to reconfigure the Java Virtual Machine so that it allows for greater
space to be devoted to nested method calls. This is done by setting the -Xss runtime
option when starting Java, either as a command-line option or through the settings
of an IDE. But it often possible to rely upon the intuition of a recursive algorithm,
yet to reimplement it more directly using traditional loops rather than method calls
to express the necessary repetition. We discuss just such an approach to conclude
the chapter.

www.it-ebooks.info
5.6. Eliminating Tail Recursion 219

5.6 Eliminating Tail Recursion

The main benefit of a recursive approach to algorithm design is that it allows us to
succinctly take advantage of a repetitive structure present in many problems. By
making our algorithm description exploit the repetitive structure in a recursive way,
we can often avoid complex case analyses and nested loops. This approach can
lead to more readable algorithm descriptions, while still being quite efficient.
However, the usefulness of recursion comes at a modest cost. In particular,
the Java Virtual Machine must maintain frames that keep track of the state of each
nested call. When computer memory is at a premium, it can be beneficial to derive
nonrecursive implementations of recursive algorithms.
In general, we can use the stack data structure, which we will introduce in
Section 6.1, to convert a recursive algorithm into a nonrecursive algorithm by man-
aging the nesting of the recursive structure ourselves, rather than relying on the
interpreter to do so. Although this only shifts the memory usage from the inter-
preter to our stack, we may be able to further reduce the memory usage by storing
the minimal information necessary.
Even better, some forms of recursion can be eliminated without any use of aux-
iliary memory. One such form is known as tail recursion. A recursion is a tail
recursion if any recursive call that is made from one context is the very last opera-
tion in that context, with the return value of the recursive call (if any) immediately
returned by the enclosing recursion. By necessity, a tail recursion must be a lin-
ear recursion (since there is no way to make a second recursive call if you must
immediately return the result of the first).
Of the recursive methods demonstrated in this chapter, the binarySearch method
of Code Fragment 5.3 and the reverseArray method of Code Fragment 5.7 are ex-
amples of tail recursion. Several others of our linear recursions are almost like
tail recursion, but not technically so. For example, our factorial method of Code
Fragment 5.1 is not a tail recursion. It concludes with the command:
return n ∗ factorial(n−1);
This is not a tail recursion because an additional multiplication is performed after
the recursive call is completed, and the result returned is not the same. For similar
reasons, the linearSum method of Code Fragment 5.6, both power methods from
Code Fragments 5.8 and 5.9, and the fibonacciGood method of Code Fragment 5.13
fail to be tail recursions.
Tail recursions are special, as they can be automatically reimplemented nonre-
cursively by enclosing the body in a loop for repetition, and replacing a recursive
call with new parameters by a reassignment of the existing parameters to those
values. In fact, many programming language implementations may convert tail
recursions in this way as an optimization.

www.it-ebooks.info
220 Chapter 5. Recursion
1 /∗∗ Returns true if the target value is found in the data array. ∗/
2 public static boolean binarySearchIterative(int[ ] data, int target) {
3 int low = 0;
4 int high = data.length − 1;
5 while (low <= high) {
6 int mid = (low + high) / 2;
7 if (target == data[mid]) // found a match
8 return true;
9 else if (target < data[mid])
10 high = mid − 1; // only consider values left of mid
11 else
12 low = mid + 1; // only consider values right of mid
13 }
14 return false; // loop ended without success
15 }
Code Fragment 5.15: A nonrecursive implementation of binary search.

As a tangible example, our binarySearch method can be reimplemented as

shown in Code Fragment 5.15. We initialize variables low and high to represent
the full extent of the array just prior to our while loop. Then, during each pass of
the loop, we either find the target, or we narrow the range of the candidate subar-
ray. Where we made the recursive call binarySearch(data, target, low, mid −1)
in the original version, we simply replace high = mid − 1 in our new version
and then continue to the next iteration of the loop. Our original base case con-
dition of low > high has simply been replaced by the opposite loop condition,
while low <= high. In our new implementation, we return false to designate a
failed search if the while loop ends without having ever returned true from within.
Most other linear recursions can be expressed quite efficiently with iteration,
even if they were not formally tail recursions. For example, there are trivial nonre-
cursive implementations for computing factorials, computing Fibonacci numbers,
summing elements of an array, or reversing the contents of an array. For example,
Code Fragment 5.16 provides a nonrecursive method to reverse the contents of an
array (as compared to the earlier recursive method from Code Fragment 5.7).

1 /∗∗ Reverses the contents of the given array. ∗/

2 public static void reverseIterative(int[ ] data) {
3 int low = 0, high = data.length − 1;
4 while (low < high) { // swap data[low] and data[high]
5 int temp = data[low];
6 data[low++] = data[high]; // post-increment of low
7 data[high−−] = temp; // post-decrement of high
8 }
9 }
Code Fragment 5.16: Reversing the elements of a sequence using iteration.

www.it-ebooks.info
5.7. Exercises 221

5.7 Exercises
Reinforcement
R-5.1 Describe a recursive algorithm for finding the maximum element in an array, A,
of n elements. What is your running time and space usage?
R-5.2 Explain how to modify the recursive binary search algorithm so that it returns the
index of the target in the sequence or −1 (if the target is not found).
R-5.3 Draw the recursion trace for the computation of power(2, 5), using the traditional
algorithm implemented in Code Fragment 5.8.
R-5.4 Draw the recursion trace for the computation of power(2, 18), using the repeated
squaring algorithm, as implemented in Code Fragment 5.9.
R-5.5 Draw the recursion trace for the execution of reverseArray(data, 0, 4), from
Code Fragment 5.7, on array data = 4, 3, 6, 2, 6.
R-5.6 Draw the recursion trace for the execution of method PuzzleSolve(3, S,U), from
Code Fragment 5.11, where S is empty and U = {a, b, c, d}.
R-5.7 Describe a recursive algorithm for computing the n th Harmonic number, defined
as Hn = ∑nk=1 1/k.
R-5.8 Describe a recursive algorithm for converting a string of digits into the integer it
represents. For example, '13531' represents the integer 13, 531.
R-5.9 Develop a nonrecursive implementation of the version of the power method from
Code Fragment 5.9 that uses repeated squaring.
R-5.10 Describe a way to use recursion to compute the sum of all the elements in an
n × n (two-dimensional) array of integers.

Creativity
C-5.11 Describe a recursive algorithm to compute the integer part of the base-two loga-
rithm of n using only addition and integer division.
C-5.12 Describe an efficient recursive algorithm for solving the element uniqueness
problem, which runs in time that is at most O(n2 ) in the worst case without using
sorting.
C-5.13 Give a recursive algorithm to compute the product of two positive integers, m and
n, using only addition and subtraction.
C-5.14 In Section 5.2 we prove by induction that the number of lines printed by a call to
drawInterval(c) is 2c − 1. Another interesting question is how many dashes are
printed during that process. Prove by induction that the number of dashes printed
by drawInterval(c) is 2c+1 − c − 2.

www.it-ebooks.info
222 Chapter 5. Recursion
C-5.15 Write a recursive method that will output all the subsets of a set of n elements
(without repeating any subsets).
C-5.16 In the Towers of Hanoi puzzle, we are given a platform with three pegs, a, b, and
c, sticking out of it. On peg a is a stack of n disks, each larger than the next, so
that the smallest is on the top and the largest is on the bottom. The puzzle is to
move all the disks from peg a to peg c, moving one disk at a time, so that we
never place a larger disk on top of a smaller one. See Figure 5.15 for an example
of the case n = 4. Describe a recursive algorithm for solving the Towers of Hanoi
puzzle for arbitrary n. (Hint: Consider first the subproblem of moving all but
the n th disk from peg a to another peg using the third as “temporary storage.”)

Figure 5.15: An illustration of the Towers of Hanoi puzzle.

C-5.17 Write a short recursive Java method that takes a character string s and outputs its
reverse. For example, the reverse of 'pots&pans' would be 'snap&stop'.
C-5.18 Write a short recursive Java method that determines if a string s is a palindrome,
that is, it is equal to its reverse. Examples of palindromes include 'racecar'
and 'gohangasalamiimalasagnahog'.
C-5.19 Use recursion to write a Java method for determining if a string s has more vowels
than consonants.
C-5.20 Write a short recursive Java method that rearranges an array of integer values so
that all the even values appear before all the odd values.
C-5.21 Given an unsorted array, A, of integers and an integer k, describe a recursive
algorithm for rearranging the elements in A so that all elements less than or equal
to k come before any elements larger than k. What is the running time of your
algorithm on an array of n values?
C-5.22 Suppose you are given an array, A, containing n distinct integers that are listed
in increasing order. Given a number k, describe a recursive algorithm to find two
integers in A that sum to k, if such a pair exists. What is the running time of your
algorithm?
C-5.23 Describe a recursive algorithm that will check if an array A of integers contains
an integer A[i] that is the sum of two integers that appear earlier in A, that is, such
that A[i] = A[ j] + A[k] for j, k < i.

www.it-ebooks.info
Chapter Notes 223
C-5.24 Isabel has an interesting way of summing up the values in an array A of n integers,
where n is a power of two. She creates an array B of half the size of A and sets
B[i] = A[2i] + A[2i + 1], for i = 0, 1, . . . , (n/2) − 1. If B has size 1, then she
outputs B[0]. Otherwise, she replaces A with B, and repeats the process. What is
the running time of her algorithm?
C-5.25 Describe a fast recursive algorithm for reversing a singly linked list L, so that the
ordering of the nodes becomes opposite of what it was before.
C-5.26 Give a recursive definition of a singly linked list class that does not use any Node
class.

Projects
P-5.27 Implement a recursive method with calling signature find(path, filename) that
reports all entries of the file system rooted at the given path having the given file
name.
P-5.28 Write a program for solving summation puzzles by enumerating and testing all
possible configurations. Using your program, solve the three puzzles given in
Section 5.3.3.
P-5.29 Provide a nonrecursive implementation of the drawInterval method for the En-
glish ruler project of Section 5.1.2. There should be precisely 2c − 1 lines of
output if c represents the length of the center tick. If incrementing a counter from
0 to 2c − 2, the number of dashes for each tick line should be exactly one more
than the number of consecutive 1’s at the end of the binary representation of the
counter.
P-5.30 Write a program that can solve instances of the Tower of Hanoi problem (from
Exercise C-5.16).

Chapter Notes
The use of recursion in programs belongs to the folklore of computer science (for example,
see the article of Dijkstra [31]). It is also at the heart of functional programming languages
(for example, see the book by Abelson, Sussman, and Sussman [1]). Interestingly, binary
search was first published in 1946, but was not published in a fully correct form until 1962.
For further discussions on lessons learned, see papers by Bentley [13] and Lesuisse [64].

www.it-ebooks.info
www.it-ebooks.info
Chapter

6 Stacks, Queues, and Deques

Contents

6.1 Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

6.1.1 The Stack Abstract Data Type . . . . . . . . . . . . . . . 227
6.1.2 A Simple Array-Based Stack Implementation . . . . . . . 230
6.1.3 Implementing a Stack with a Singly Linked List . . . . . . 233
6.1.4 Reversing an Array Using a Stack . . . . . . . . . . . . . 234
6.1.5 Matching Parentheses and HTML Tags . . . . . . . . . . 235
6.2 Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
6.2.1 The Queue Abstract Data Type . . . . . . . . . . . . . . 239
6.2.2 Array-Based Queue Implementation . . . . . . . . . . . . 241
6.2.3 Implementing a Queue with a Singly Linked List . . . . . . 245
6.2.4 A Circular Queue . . . . . . . . . . . . . . . . . . . . . . 246
6.3 Double-Ended Queues . . . . . . . . . . . . . . . . . . . . . 248
6.3.1 The Deque Abstract Data Type . . . . . . . . . . . . . . 248
6.3.2 Implementing a Deque . . . . . . . . . . . . . . . . . . . 250
6.3.3 Deques in the Java Collections Framework . . . . . . . . . 251
6.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

www.it-ebooks.info
226 Chapter 6. Stacks, Queues, and Deques

6.1 Stacks
A stack is a collection of objects that are inserted and removed according to the
last-in, first-out (LIFO) principle. A user may insert objects into a stack at any
time, but may only access or remove the most recently inserted object that remains
(at the so-called “top” of the stack). The name “stack” is derived from the metaphor
of a stack of plates in a spring-loaded, cafeteria plate dispenser. In this case, the
fundamental operations involve the “pushing” and “popping” of plates on the stack.
When we need a new plate from the dispenser, we “pop” the top plate off the stack,
and when we add a plate, we “push” it down on the stack to become the new top
plate. Perhaps an even more amusing example is a PEZ ® candy dispenser, which
stores mint candies in a spring-loaded container that “pops” out the topmost candy
in the stack when the top of the dispenser is lifted (see Figure 6.1).

Figure 6.1: A schematic drawing of a PEZ ® dispenser; a physical implementation

of the stack ADT. (PEZ ® is a registered trademark of PEZ Candy, Inc.)

Stacks are a fundamental data structure. They are used in many applications,
including the following.

Example 6.1: Internet Web browsers store the addresses of recently visited sites
on a stack. Each time a user visits a new site, that site’s address is “pushed” onto the
stack of addresses. The browser then allows the user to “pop” back to previously
visited sites using the “back” button.

Example 6.2: Text editors usually provide an “undo” mechanism that cancels re-
cent editing operations and reverts to former states of a document. This undo oper-
ation can be accomplished by keeping text changes in a stack.

www.it-ebooks.info
6.1. Stacks 227

6.1.1 The Stack Abstract Data Type

Stacks are the simplest of all data structures, yet they are also among the most
important, as they are used in a host of different applications, and as a tool for
many more sophisticated data structures and algorithms. Formally, a stack is an
abstract data type (ADT) that supports the following two update methods:

push(e): Adds element e to the top of the stack.

pop( ): Removes and returns the top element from the stack
(or null if the stack is empty).

Additionally, a stack supports the following accessor methods for convenience:

top( ): Returns the top element of the stack, without removing it

(or null if the stack is empty).
size( ): Returns the number of elements in the stack.
isEmpty( ): Returns a boolean indicating whether the stack is empty.
By convention, we assume that elements added to the stack can have arbitrary type
and that a newly created stack is empty.

Example 6.3: The following table shows a series of stack operations and their
effects on an initially empty stack S of integers.

Method Return Value Stack Contents

push(5) – (5)
push(3) – (5, 3)
size( ) 2 (5, 3)
pop( ) 3 (5)
isEmpty( ) false (5)
pop( ) 5 ()
isEmpty( ) true ()
pop( ) null ()
push(7) – (7)
push(9) – (7, 9)
top( ) 9 (7, 9)
push(4) – (7, 9, 4)
size( ) 3 (7, 9, 4)
pop( ) 4 (7, 9)
push(6) – (7, 9, 6)
push(8) – (7, 9, 6, 8)
pop( ) 8 (7, 9, 6)

www.it-ebooks.info
228 Chapter 6. Stacks, Queues, and Deques
A Stack Interface in Java
In order to formalize our abstraction of a stack, we define what is known as its
application programming interface (API) in the form of a Java interface, which
describes the names of the methods that the ADT supports and how they are to be
declared and used. This interface is defined in Code Fragment 6.1.
We rely on Java’s generics framework (described in Section 2.5.2), allow-
ing the elements stored in the stack to belong to any object type <E>. For ex-
ample, a variable representing a stack of integers could be declared with type
Stack<Integer>. The formal type parameter is used as the parameter type for
the push method, and the return type for both pop and top.
Recall, from the discussion of Java interfaces in Section 2.3.1, that the interface
serves as a type definition but that it cannot be directly instantiated. For the ADT
to be of any use, we must provide one or more concrete classes that implement the
methods of the interface associated with that ADT. In the following subsections, we
will give two such implementations of the Stack interface: one that uses an array
for storage and another that uses a linked list.

The java.util.Stack Class

Because of the importance of the stack ADT, Java has included, since its original
version, a concrete class named java.util.Stack that implements the LIFO seman-
tics of a stack. However, Java’s Stack class remains only for historic reasons, and
its interface is not consistent with most other data structures in the Java library.
In fact, the current documentation for the Stack class recommends that it not be
used, as LIFO functionality (and more) is provided by a more general data struc-
ture known as a double-ended queue (which we describe in Section 6.3).
For the sake of comparison, Table 6.1 provides a side-by-side comparison of
the interface for our stack ADT and the java.util.Stack class. In addition to
some differences in method names, we note that methods pop and peek of the
java.util.Stack class throw a custom EmptyStackException if called when the stack
is empty (whereas null is returned in our abstraction).

Our Stack ADT Class java.util.Stack

size( ) size( )
isEmpty( ) empty( ) ⇐
push(e) push(e)
pop( ) pop( )
top( ) peek( ) ⇐

Table 6.1: Methods of our stack ADT and corresponding methods of the class
java.util.Stack, with differences highlighted in the right margin.

www.it-ebooks.info
6.1. Stacks 229

1 /∗∗
2 ∗ A collection of objects that are inserted and removed according to the last-in
3 ∗ first-out principle. Although similar in purpose, this interface differs from
4 ∗ java.util.Stack.
5 ∗
6 ∗ @author Michael T. Goodrich
7 ∗ @author Roberto Tamassia
8 ∗ @author Michael H. Goldwasser
9 ∗/
10 public interface Stack<E> {
11
12 /∗∗
13 ∗ Returns the number of elements in the stack.
14 ∗ @return number of elements in the stack
15 ∗/
16 int size( );
17
18 /∗∗
19 ∗ Tests whether the stack is empty.
20 ∗ @return true if the stack is empty, false otherwise
21 ∗/
22 boolean isEmpty( );
23
24 /∗∗
25 ∗ Inserts an element at the top of the stack.
26 ∗ @param e the element to be inserted
27 ∗/
28 void push(E e);
29
30 /∗∗
31 ∗ Returns, but does not remove, the element at the top of the stack.
32 ∗ @return top element in the stack (or null if empty)
33 ∗/
34 E top( );
35
36 /∗∗
37 ∗ Removes and returns the top element from the stack.
38 ∗ @return element removed (or null if empty)
39 ∗/
40 E pop( );
41 }
Code Fragment 6.1: Interface Stack documented with comments in Javadoc style
(Section 1.9.4). Note also the use of the generic parameterized type, E, which
allows a stack to contain elements of any specified (reference) type.

www.it-ebooks.info
230 Chapter 6. Stacks, Queues, and Deques

6.1.2 A Simple Array-Based Stack Implementation

As our first implementation of the stack ADT, we store elements in an array, named
data, with capacity N for some fixed N. We oriented the stack so that the bottom
element of the stack is always stored in cell data[0], and the top element of the
stack in cell data[t] for index t that is equal to one less than the current size of the
stack. (See Figure 6.2.)

data: A B C D E F G K L M
0 1 2 t N−1
Figure 6.2: Representing a stack with an array; the top element is in cell data[t].
Recalling that arrays start at index 0 in Java, when the stack holds elements
from data[0] to data[t] inclusive, it has size t + 1. By convention, when the stack is
empty it will have t equal to −1 (and thus has size t + 1, which is 0). A complete
Java implementation based on this strategy is given in Code Fragment 6.2 (with
Javadoc comments omitted due to space considerations).
1 public class ArrayStack<E> implements Stack<E> {
2 public static final int CAPACITY=1000; // default array capacity
3 private E[ ] data; // generic array used for storage
4 private int t = −1; // index of the top element in stack
5 public ArrayStack( ) { this(CAPACITY); } // constructs stack with default capacity
6 public ArrayStack(int capacity) { // constructs stack with given capacity
7 data = (E[ ]) new Object[capacity]; // safe cast; compiler may give warning
8 }
9 public int size( ) { return (t + 1); }
10 public boolean isEmpty( ) { return (t == −1); }
11 public void push(E e) throws IllegalStateException {
12 if (size( ) == data.length) throw new IllegalStateException("Stack is full");
13 data[++t] = e; // increment t before storing new item
14 }
15 public E top( ) {
16 if (isEmpty( )) return null;
17 return data[t];
18 }
19 public E pop( ) {
20 if (isEmpty( )) return null;
21 E answer = data[t];
22 data[t] = null; // dereference to help garbage collection
23 t−−;
24 return answer;
25 }
26 }
Code Fragment 6.2: Array-based implementation of the Stack interface.

www.it-ebooks.info
6.1. Stacks 231
A Drawback of This Array-Based Stack Implementation
The array implementation of a stack is simple and efficient. Nevertheless, this
implementation has one negative aspect—it relies on a fixed-capacity array, which
limits the ultimate size of the stack.
For convenience, we allow the user of a stack to specify the capacity as a pa-
rameter to the constructor (and offer a default constructor that uses capacity of
1, 000). In cases where a user has a good estimate on the number of items needing
to go in the stack, the array-based implementation is hard to beat. However, if the
estimate is wrong, there can be grave consequences. If the application needs much
less space than the reserved capacity, memory is wasted. Worse yet, if an attempt
is made to push an item onto a stack that has already reached its maximum ca-
pacity, the implementation of Code Fragment 6.2 throws an IllegalStateException,
refusing to store the new element. Thus, even with its simplicity and efficiency, the
array-based stack implementation is not necessarily ideal.
Fortunately, we will later demonstrate two approaches for implementing a stack
without such a size limitation and with space always proportional to the actual num-
ber of elements stored in the stack. One approach, given in the next subsection uses
a singly linked list for storage; in Section 7.2.1, we will provide a more advanced
array-based approach that overcomes the limit of a fixed capacity.

Analyzing the Array-Based Stack Implementation

The correctness of the methods in the array-based implementation follows from
our definition of index t. Note well that when pushing an element, t is incremented
before placing the new element, so that it uses the first available cell.
Table 6.2 shows the running times for methods of this array-based stack im-
plementation. Each method executes a constant number of statements involving
arithmetic operations, comparisons, and assignments, or calls to size and isEmpty,
which both run in constant time. Thus, in this implementation of the stack ADT,
each method runs in constant time, that is, they each run in O(1) time.

Method Running Time

size O(1)
isEmpty O(1)
top O(1)
push O(1)
pop O(1)

Table 6.2: Performance of a stack realized by an array. The space usage is O(N),
where N is the size of the array, determined at the time the stack is instantiated, and
independent from the number n ≤ N of elements that are actually in the stack.

www.it-ebooks.info
232 Chapter 6. Stacks, Queues, and Deques
Garbage Collection in Java
We wish to draw attention to one interesting aspect involving the implementation of
the pop method in Code Fragment 6.2. We set a local variable, answer, to reference
the element that is being popped, and then we intentionally reset data[t] to null at
line 22, before decrementing t. The assignment to null was not technically required,
as our stack would still operate correctly without it.
Our reason for returning the cell to a null reference is to assist Java’s garbage
collection mechanism, which searches memory for objects that are no longer ac-
tively referenced and reclaims their space for future use. (For more details, see
Section 15.1.3.) If we continued to store a reference to the popped element in our
array, the stack class would ignore it (eventually overwriting the reference if more
elements get added to the stack). But, if there were no other active references to the
element in the user’s application, that spurious reference in the stack’s array would
stop Java’s garbage collector from reclaiming the element.

Sample Usage
We conclude this section by providing a demonstration of code that creates and uses
an instance of the ArrayStack class. In this example, we declare the parameterized
type of the stack as the Integer wrapper class. This causes the signature of the push
method to accept an Integer instance as a parameter, and for the return type of both
top and pop to be an Integer. Of course, with Java’s autoboxing and unboxing (see
Section 1.3), a primitive int can be sent as a parameter to push.

Stack<Integer> S = new ArrayStack<>( ); // contents: ()

S.push(5); // contents: (5)
S.push(3); // contents: (5, 3)
System.out.println(S.size( )); // contents: (5, 3) outputs 2
System.out.println(S.pop( )); // contents: (5) outputs 3
System.out.println(S.isEmpty( )); // contents: (5) outputs false
System.out.println(S.pop( )); // contents: () outputs 5
System.out.println(S.isEmpty( )); // contents: () outputs true
System.out.println(S.pop( )); // contents: () outputs null
S.push(7); // contents: (7)
S.push(9); // contents: (7, 9)
System.out.println(S.top( )); // contents: (7, 9) outputs 9
S.push(4); // contents: (7, 9, 4)
System.out.println(S.size( )); // contents: (7, 9, 4) outputs 3
System.out.println(S.pop( )); // contents: (7, 9) outputs 4
S.push(6); // contents: (7, 9, 6)
S.push(8); // contents: (7, 9, 6, 8)
System.out.println(S.pop( )); // contents: (7, 9, 6) outputs 8
Code Fragment 6.3: Sample usage of our ArrayStack class.

www.it-ebooks.info
6.1. Stacks 233

6.1.3 Implementing a Stack with a Singly Linked List

In this section, we demonstrate how the Stack interface can be easily implemented
using a singly linked list for storage. Unlike our array-based implementation, the
linked-list approach has memory usage that is always proportional to the number
of actual elements currently in the stack, and without an arbitrary capacity limit.
In designing such an implementation, we need to decide if the top of the stack
is at the front or back of the list. There is clearly a best choice here, however, since
we can insert and delete elements in constant time only at the front. With the top
of the stack stored at the front of the list, all methods execute in constant time.

The Adapter Pattern

The adapter design pattern applies to any context where we effectively want to
modify an existing class so that its methods match those of a related, but different,
class or interface. One general way to apply the adapter pattern is to define a new
class in such a way that it contains an instance of the existing class as a hidden
field, and then to implement each method of the new class using methods of this
hidden instance variable. By applying the adapter pattern in this way, we have
created a new class that performs some of the same functions as an existing class,
but repackaged in a more convenient way.
In the context of the stack ADT, we can adapt our SinglyLinkedList class of
Section 3.2.1 to define a new LinkedStack class, shown in Code Fragment 6.4.
This class declares a SinglyLinkedList named list as a private field, and uses the
following correspondences:

Stack Method Singly Linked List Method

size( ) list.size( )
isEmpty( ) list.isEmpty( )
push(e) list.addFirst(e)
pop( ) list.removeFirst( )
top( ) list.first( )

1 public class LinkedStack<E> implements Stack<E> {

2 private SinglyLinkedList<E> list = new SinglyLinkedList<>( ); // an empty list
3 public LinkedStack( ) { } // new stack relies on the initially empty list
4 public int size( ) { return list.size( ); }
5 public boolean isEmpty( ) { return list.isEmpty( ); }
6 public void push(E element) { list.addFirst(element); }
7 public E top( ) { return list.first( ); }
8 public E pop( ) { return list.removeFirst( ); }
9 }
Code Fragment 6.4: Implementation of a Stack using a SinglyLinkedList as storage.

www.it-ebooks.info
234 Chapter 6. Stacks, Queues, and Deques

6.1.4 Reversing an Array Using a Stack

As a consequence of the LIFO protocol, a stack can be used as a general toll to
reverse a data sequence. For example, if the values 1, 2, and 3 are pushed onto a
stack in that order, they will be popped from the stack in the order 3, 2, and then 1.
We demonstrate this concept by revisiting the problem of reversing the elements
of an array. (We provided a recursive algorithm for this task in Section 5.3.1.) We
create an empty stack for auxiliary storage, push all of the array elements onto the
stack, and then pop those elements off of the stack while overwriting the cells of the
array from beginning to end. In Code Fragment 6.5, we give a Java implementation
of this algorithm. We show an example use of this method in Code Fragment 6.6.

1 /∗∗ A generic method for reversing an array. ∗/

2 public static <E> void reverse(E[ ] a) {
3 Stack<E> buffer = new ArrayStack<>(a.length);
4 for (int i=0; i < a.length; i++)
5 buffer.push(a[i]);
6 for (int i=0; i < a.length; i++)
7 a[i] = buffer.pop( );
8 }
Code Fragment 6.5: A generic method that reverses the elements in an array with
objects of type E, using a stack declared with the interface Stack<E> as its type.

1 /∗∗ Tester routine for reversing arrays ∗/

2 public static void main(String args[ ]) {
3 Integer[ ] a = {4, 8, 15, 16, 23, 42}; // autoboxing allows this
4 String[ ] s = {"Jack", "Kate", "Hurley", "Jin", "Michael"};
5 System.out.println("a = " + Arrays.toString(a));
6 System.out.println("s = " + Arrays.toString(s));
7 System.out.println("Reversing...");
8 reverse(a);
9 reverse(s);
10 System.out.println("a = " + Arrays.toString(a));
11 System.out.println("s = " + Arrays.toString(s));
12 }

The output from this method is the following:

a = [4, 8, 15, 16, 23, 42]
s = [Jack, Kate, Hurley, Jin, Michael]
Reversing...
a = [42, 23, 16, 15, 8, 4]
s = [Michael, Jin, Hurley, Kate, Jack]
Code Fragment 6.6: A test of the reverse method using two arrays.

www.it-ebooks.info
6.1. Stacks 235

6.1.5 Matching Parentheses and HTML Tags

In this subsection, we explore two related applications of stacks, both of which
involve testing for pairs of matching delimiters. In our first application, we consider
arithmetic expressions that may contain various pairs of grouping symbols, such as
• Parentheses: “(” and “)”
• Braces: “{” and “}”
• Brackets: “[” and “]”
Each opening symbol must match its corresponding closing symbol. For example,
a left bracket, “[,” must match a corresponding right bracket, “],” as in the following
expression
[(5 + x) − (y + z)].
The following examples further illustrate this concept:
• Correct: ( )(( )){([( )])}
• Correct: ((( )(( )){([( )])}))
• Incorrect: )(( )){([( )])}
• Incorrect: ({[ ])}
• Incorrect: (
We leave the precise definition of a matching group of symbols to Exercise R-6.6.

An Algorithm for Matching Delimiters

An important task when processing arithmetic expressions is to make sure their
delimiting symbols match up correctly. We can use a stack to perform this task
with a single left-to-right scan of the original string.
Each time we encounter an opening symbol, we push that symbol onto the
stack, and each time we encounter a closing symbol, we pop a symbol from the
stack (assuming it is not empty) and check that these two symbols form a valid
pair. If we reach the end of the expression and the stack is empty, then the original
expression was properly matched. Otherwise, there must be an opening delimiter
on the stack without a matching symbol. If the length of the original expression
is n, the algorithm will make at most n calls to push and n calls to pop. Code
Fragment 6.7 presents a Java implementation of such an algorithm. It specifically
checks for delimiter pairs ( ), { }, and [ ], but could easily be changed to accommo-
date further symbols. Specifically, we define two fixed strings, "({[" and ")}]",
that are intentionally coordinated to reflect the symbol pairs. When examining a
character of the expression string, we call the indexOf method of the String class
on these special strings to determine if the character matches a delimiter and, if so,
which one. Method indexOf returns the the index at which a given character is first
found in a string (or −1 if the character is not found).

www.it-ebooks.info
236 Chapter 6. Stacks, Queues, and Deques
1 /∗∗ Tests if delimiters in the given expression are properly matched. ∗/
2 public static boolean isMatched(String expression) {
3 final String opening = "({["; // opening delimiters
4 final String closing = ")}]"; // respective closing delimiters
5 Stack<Character> buffer = new LinkedStack<>( );
6 for (char c : expression.toCharArray( )) {
7 if (opening.indexOf(c) != −1) // this is a left delimiter
8 buffer.push(c);
9 else if (closing.indexOf(c) != −1) { // this is a right delimiter
10 if (buffer.isEmpty( )) // nothing to match with
11 return false;
12 if (closing.indexOf(c) != opening.indexOf(buffer.pop( )))
13 return false; // mismatched delimiter
14 }
15 }
16 return buffer.isEmpty( ); // were all opening delimiters matched?
17 }

Code Fragment 6.7: Method for matching delimiters in an arithmetic expression.

Matching Tags in a Markup Language

Another application of matching delimiters is in the validation of markup languages
such as HTML or XML. HTML is the standard format for hyperlinked documents
on the Internet and XML is an extensible markup language used for a variety of
structured data sets. We show a sample HTML document in Figure 6.3.
<body>
<center>
<h1> The Little Boat </h1> The Little Boat
</center>
<p> The storm tossed the little The storm tossed the little boat
boat like a cheap sneaker in an like a cheap sneaker in an
old washing machine. The three old washing machine. The three
drunken fishermen were used to
drunken fishermen were used to
such treatment, of course, but
not the tree salesman, who even as such treatment, of course, but not
a stowaway now felt that he the tree salesman, who even as
had overpaid for the voyage. </p> a stowaway now felt that he had
<ol> overpaid for the voyage.
<li> Will the salesman die? </li> 1. Will the salesman die?
<li> What color is the boat? </li> 2. What color is the boat?
<li> And what about Naomi? </li>
3. And what about Naomi?
</ol>
</body>
(a) (b)
Figure 6.3: Illustrating (a) an HTML document and (b) its rendering.

www.it-ebooks.info
6.1. Stacks 237
In an HTML document, portions of text are delimited by HTML tags. A simple
opening HTML tag has the form “<name>” and the corresponding closing tag has
the form “</name>”. For example, we see the <body> tag on the first line of
Figure 6.3a, and the matching </body> tag at the close of that document. Other
commonly used HTML tags that are used in this example include:
• <body>: document body
• <h1>: section header
• <center>: center justify
• <p>: paragraph
• <ol>: numbered (ordered) list
• <li>: list item
Ideally, an HTML document should have matching tags, although most browsers
tolerate a certain number of mismatching tags. In Code Fragment 6.8, we give a
Java method that matches tags in a string representing an HTML document.
We make a left-to-right pass through the raw string, using index j to track
our progress. The indexOf method of the String class, which optionally accepts a
starting index as a second parameter, locates the '<' and '>' characters that define
the tags. Method substring, also of the String class, returns the substring starting
at a given index and optionally ending right before another given index. Opening
tags are pushed onto the stack, and matched against closing tags as they are popped
from the stack, just as we did when matching delimiters in Code Fragment 6.7.
1 /∗∗ Tests if every opening tag has a matching closing tag in HTML string. ∗/
2 public static boolean isHTMLMatched(String html) {
3 Stack<String> buffer = new LinkedStack<>( );
4 int j = html.indexOf('<'); // find first ’<’ character (if any)
5 while (j != −1) {
6 int k = html.indexOf('>', j+1); // find next ’>’ character
7 if (k == −1)
8 return false; // invalid tag
9 String tag = html.substring(j+1, k); // strip away < >
10 if (!tag.startsWith("/")) // this is an opening tag
11 buffer.push(tag);
12 else { // this is a closing tag
13 if (buffer.isEmpty( ))
14 return false; // no tag to match
15 if (!tag.substring(1).equals(buffer.pop( )))
16 return false; // mismatched tag
17 }
18 j = html.indexOf('<', k+1); // find next ’<’ character (if any)
19 }
20 return buffer.isEmpty( ); // were all opening tags matched?
21 }
Code Fragment 6.8: Method for testing if an HTML document has matching tags.

www.it-ebooks.info
238 Chapter 6. Stacks, Queues, and Deques

6.2 Queues
Another fundamental data structure is the queue. It is a close “cousin” of the stack,
but a queue is a collection of objects that are inserted and removed according to the
first-in, first-out (FIFO) principle. That is, elements can be inserted at any time,
but only the element that has been in the queue the longest can be next removed.
We usually say that elements enter a queue at the back and are removed from
the front. A metaphor for this terminology is a line of people waiting to get on an
amusement park ride. People waiting for such a ride enter at the back of the line
and get on the ride from the front of the line. There are many other applications
of queues (see Figure 6.4). Stores, theaters, reservation centers, and other similar
services typically process customer requests according to the FIFO principle. A
queue would therefore be a logical choice for a data structure to handle calls to a
customer service center, or a wait-list at a restaurant. FIFO queues are also used by
many computing devices, such as a networked printer, or a Web server responding
to requests.

Tickets

(a)

er
ent
lC
Cal
Call Queue

(b)
Figure 6.4: Real-world examples of a first-in, first-out queue. (a) People waiting in
line to purchase tickets; (b) phone calls being routed to a customer service center.

www.it-ebooks.info
6.2. Queues 239

6.2.1 The Queue Abstract Data Type

Formally, the queue abstract data type defines a collection that keeps objects in a
sequence, where element access and deletion are restricted to the first element in
the queue, and element insertion is restricted to the back of the sequence. This
restriction enforces the rule that items are inserted and deleted in a queue accord-
ing to the first-in, first-out (FIFO) principle. The queue abstract data type (ADT)
supports the following two update methods:

enqueue(e): Adds element e to the back of queue.

dequeue( ): Removes and returns the first element from the queue
(or null if the queue is empty).

The queue ADT also includes the following accessor methods (with first being
analogous to the stack’s top method):

first( ): Returns the first element of the queue, without removing it

(or null if the queue is empty).

size( ): Returns the number of elements in the queue.

isEmpty( ): Returns a boolean indicating whether the queue is empty.

By convention, we assume that elements added to the queue can have arbitrary
type and that a newly created queue is empty. We formalize the queue ADT with
the Java interface shown in Code Fragment 6.9.

1 public interface Queue<E> {

2 /∗∗ Returns the number of elements in the queue. ∗/
3 int size( );
4 /∗∗ Tests whether the queue is empty. ∗/
5 boolean isEmpty( );
6 /∗∗ Inserts an element at the rear of the queue. ∗/
7 void enqueue(E e);
8 /∗∗ Returns, but does not remove, the first element of the queue (null if empty). ∗/
9 E first( );
10 /∗∗ Removes and returns the first element of the queue (null if empty). ∗/
11 E dequeue( );
12 }
Code Fragment 6.9: A Queue interface defining the queue ADT, with a standard
FIFO protocol for insertions and removals.

www.it-ebooks.info
240 Chapter 6. Stacks, Queues, and Deques
Example 6.4: The following table shows a series of queue operations and their
effects on an initially empty queue Q of integers.

Method Return Value first ← Q ← last

enqueue(5) – (5)
enqueue(3) – (5, 3)
size( ) 2 (5, 3)
dequeue( ) 5 (3)
isEmpty( ) false (3)
dequeue( ) 3 ()
isEmpty( ) true ()
dequeue( ) null ()
enqueue(7) – (7)
enqueue(9) – (7, 9)
first( ) 7 (7, 9)
enqueue(4) – (7, 9, 4)

The java.util.Queue Interface in Java

Java provides a type of queue interface, java.util.Queue, which has functionality
similar to the traditional queue ADT, given above, but the documentation for the
java.util.Queue interface does not insist that it support only the FIFO principle.
When supporting the FIFO principle, the methods of the java.util.Queue interface
have the equivalences with the queue ADT shown in Table 6.3.
The java.util.Queue interface supports two styles for most operations, which
vary in the way that they treat exceptional cases. When a queue is empty, the
remove( ) and element( ) methods throw a NoSuchElementException, while the
corresponding methods poll( ) and peek( ) return null. For implementations with a
bounded capacity, the add method will throw an IllegalStateException when full,
while the offer method ignores the new element and returns false to signal that the
element was not accepted.

Our Queue ADT Interface java.util.Queue

throws exceptions returns special value
enqueue(e) add(e) offer(e)
dequeue( ) remove( ) poll( )
first( ) element( ) peek( )
size( ) size( )
isEmpty( ) isEmpty( )

Table 6.3: Methods of the queue ADT and corresponding methods of the interface
java.util.Queue, when supporting the FIFO principle.

www.it-ebooks.info
6.2. Queues 241

6.2.2 Array-Based Queue Implementation

In Section 6.1.2, we implemented the LIFO semantics of the Stack ADT using an
array (albeit, with a fixed capacity), such that every operation executes in constant
time. In this section, we will consider how to use an array to efficiently support the
FIFO semantics of the Queue ADT.
Let’s assume that as elements are inserted into a queue, we store them in an
array such that the first element is at index 0, the second element at index 1, and so
on. (See Figure 6.5.)

data: A B C D E F G K L M
0 1 2 N−1

Figure 6.5: Using an array to store elements of a queue, such that the first element
inserted, “A”, is at cell 0, the second element inserted, “B”, at cell 1, and so on.

With such a convention, the question is how we should implement the dequeue
operation. The element to be removed is stored at index 0 of the array. One strategy
is to execute a loop to shift all other elements of the queue one cell to the left, so that
the front of the queue is again aligned with cell 0 of the array. Unfortunately, the
use of such a loop would result in an O(n) running time for the dequeue method.
We can improve on the above strategy by avoiding the loop entirely. We will
replace a dequeued element in the array with a null reference, and maintain an
explicit variable f to represent the index of the element that is currently at the
front of the queue. Such an algorithm for dequeue would run in O(1) time. After
several dequeue operations, this approach might lead to the configuration portrayed
in Figure 6.6.

data: F G K L M
0 1 2 f N−1

Figure 6.6: Allowing the front of the queue to drift away from index 0. In this
representation, index f denotes the location of the front of the queue.

However, there remains a challenge with the revised approach. With an array
of capacity N, we should be able to store up to N elements before reaching any
exceptional case. If we repeatedly let the front of the queue drift rightward over
time, the back of the queue would reach the end of the underlying array even when
there are fewer than N elements currently in the queue. We must decide how to
store additional elements in such a configuration.

www.it-ebooks.info
242 Chapter 6. Stacks, Queues, and Deques
Using an Array Circularly
In developing a robust queue implementation, we allow both the front and back
of the queue to drift rightward, with the contents of the queue “wrapping around”
the end of an array, as necessary. Assuming that the array has fixed length N, new
elements are enqueued toward the “end” of the current queue, progressing from the
front to index N − 1 and continuing at index 0, then 1. Figure 6.7 illustrates such a
queue with first element F and last element R.

data: Q R F G K L M N O P
0 1 2 f N−1
Figure 6.7: Modeling a queue with a circular array that wraps around the end.

Implementing such a circular view is relatively easy with the modulo operator,
denoted with the symbol % in Java. Recall that the modulo operator is computed
by taking the remainder after an integral division. For example, 14 divided by 3
has a quotient of 4 with remainder 2, that is, 14 2
3 = 4 3 . So in Java, 14 / 3 evaluates
to the quotient 4, while 14 % 3 evaluates to the remainder 2.
The modulo operator is ideal for treating an array circularly. When we de-
queue an element and want to “advance” the front index, we use the arithmetic
f = ( f + 1) % N. As a concrete example, if we have an array of length 10, and a
front index 7, we can advance the front by formally computing (7+1) % 10, which
is simply 8, as 8 divided by 10 is 0 with a remainder of 8. Similarly, advancing
index 8 results in index 9. But when we advance from index 9 (the last one in the
array), we compute (9+1) % 10, which evaluates to index 0 (as 10 divided by 10
has a remainder of zero).

A Java Queue Implementation

A complete implementation of a queue ADT using an array in circular fashion is
presented in Code Fragment 6.10. Internally, the queue class maintains the follow-
ing three instance variables:
data: a reference to the underlying array.
f: an integer that represents the index, within array data, of the first
element of the queue (assuming the queue is not empty).
sz: an integer representing the current number of elements stored in
the queue (not to be confused with the length of the array).
We allow the user to specify the capacity of the queue as an optional parameter to
the constructor.
The implementations of methods size and isEmpty are trivial, given the sz field,
and the implementation of first is simple, given index f. A discussion of update
methods enqueue and dequeue follows the presentation of the code.

www.it-ebooks.info
6.2. Queues 243

1 /∗∗ Implementation of the queue ADT using a fixed-length array. ∗/

2 public class ArrayQueue<E> implements Queue<E> {
3 // instance variables
4 private E[ ] data; // generic array used for storage
5 private int f = 0; // index of the front element
6 private int sz = 0; // current number of elements
7
8 // constructors
9 public ArrayQueue( ) {this(CAPACITY);} // constructs queue with default capacity
10 public ArrayQueue(int capacity) { // constructs queue with given capacity
11 data = (E[ ]) new Object[capacity]; // safe cast; compiler may give warning
12 }
13
14 // methods
15 /∗∗ Returns the number of elements in the queue. ∗/
16 public int size( ) { return sz; }
17
18 /∗∗ Tests whether the queue is empty. ∗/
19 public boolean isEmpty( ) { return (sz == 0); }
20
21 /∗∗ Inserts an element at the rear of the queue. ∗/
22 public void enqueue(E e) throws IllegalStateException {
23 if (sz == data.length) throw new IllegalStateException("Queue is full");
24 int avail = (f + sz) % data.length; // use modular arithmetic
25 data[avail] = e;
26 sz++;
27 }
28
29 /∗∗ Returns, but does not remove, the first element of the queue (null if empty). ∗/
30 public E first( ) {
31 if (isEmpty( )) return null;
32 return data[f];
33 }
34
35 /∗∗ Removes and returns the first element of the queue (null if empty). ∗/
36 public E dequeue( ) {
37 if (isEmpty( )) return null;
38 E answer = data[f];
39 data[f] = null; // dereference to help garbage collection
40 f = (f + 1) % data.length;
41 sz−−;
42 return answer;
43 }
Code Fragment 6.10: Array-based implementation of a queue.

www.it-ebooks.info
244 Chapter 6. Stacks, Queues, and Deques
Adding and Removing Elements
The goal of the enqueue method is to add a new element to the back of the queue.
We need to determine the proper index at which to place the new element. Although
we do not explicitly maintain an instance variable for the back of the queue, we
compute the index of the next opening based on the formula:
avail = (f + sz) % data.length;
Note that we are using the size of the queue as it exists prior to the addition of
the new element. As a sanity check, for a queue with capacity 10, current size 3,
and first element at index 5, its three elements are stored at indices 5, 6, and 7, and
the next element should be added at index 8, computed as (5+3) % 10. As a case
with wraparound, if the queue has capacity 10, current size 3, and first element at
index 8, its three elements are stored at indices 8, 9, and 0, and the next element
should be added at index 1, computed as (8+3) % 10.
When the dequeue method is called, the current value of f designates the index
of the value that is to be removed and returned. We keep a local reference to the
element that will be returned, before setting its cell of the array back to null, to aid
the garbage collector. Then the index f is updated to reflect the removal of the first
element, and the presumed promotion of the second element to become the new
first. In most cases, we simply want to increment the index by one, but because
of the possibility of a wraparound configuration, we rely on modular arithmetic,
computing f = (f+1) % data.length, as originally described on page 242.

Analyzing the Efficiency of an Array-Based Queue

Table 6.4 shows the running times of methods in a realization of a queue by an
array. As with our array-based stack implementation, each of the queue methods in
the array realization executes a constant number of statements involving arithmetic
operations, comparisons, and assignments. Thus, each method in this implementa-
tion runs in O(1) time.

Method Running Time

size O(1)
isEmpty O(1)
first O(1)
enqueue O(1)
dequeue O(1)

Table 6.4: Performance of a queue realized by an array. The space usage is O(N),
where N is the size of the array, determined at the time the queue is created, and
independent from the number n < N of elements that are actually in the queue.

www.it-ebooks.info
6.2. Queues 245

6.2.3 Implementing a Queue with a Singly Linked List

As we did for the stack ADT, we can easily adapt a singly linked list to imple-
ment the queue ADT while supporting worst-case O(1)-time for all operations, and
without any artificial limit on the capacity. The natural orientation for a queue is to
align the front of the queue with the front of the list, and the back of the queue with
the tail of the list, because the only update operation that singly linked lists support
at the back end is an insertion. Our Java implementation of a LinkedQueue class is
given in Code 6.11.

1 /∗∗ Realization of a FIFO queue as an adaptation of a SinglyLinkedList. ∗/

2 public class LinkedQueue<E> implements Queue<E> {
3 private SinglyLinkedList<E> list = new SinglyLinkedList<>( ); // an empty list
4 public LinkedQueue( ) { } // new queue relies on the initially empty list
5 public int size( ) { return list.size( ); }
6 public boolean isEmpty( ) { return list.isEmpty( ); }
7 public void enqueue(E element) { list.addLast(element); }
8 public E first( ) { return list.first( ); }
9 public E dequeue( ) { return list.removeFirst( ); }
10 }
Code Fragment 6.11: Implementation of a Queue using a SinglyLinkedList.

Analyzing the Efficiency of a Linked Queue

Although we had not yet introduced asymptotic analysis when we presented our
SinglyLinkedList implementation in Chapter 3, it is clear upon reexamination that
each method of that class runs in O(1) worst-case time. Therefore, each method of
our LinkedQueue adaptation also runs in O(1) worst-case time.
We also avoid the need to specify a maximum size for the queue, as was done
in the array-based queue implementation. However, this benefit comes with some
expense. Because each node stores a next reference, in addition to the element
reference, a linked list uses more space per element than a properly sized array of
references.
Also, although all methods execute in constant time for both implementations,
it seems clear that the operations involving linked lists have a large number of
primitive operations per call. For example, adding an element to an array-based
queue consists primarily of calculating an index with modular arithmetic, storing
the element in the array cell, and incrementing the size counter. For a linked list,
an insertion includes the instantiation and initialization of a new node, relinking an
existing node to the new node, and incrementing the size counter. In practice, this
makes the linked-list method more expensive than the array-based method.

www.it-ebooks.info
246 Chapter 6. Stacks, Queues, and Deques

6.2.4 A Circular Queue

In Section 3.3, we implemented a circularly linked list class that supports all be-
haviors of a singly linked list, and an additional rotate( ) method that efficiently
moves the first element to the end of the list. We can generalize the Queue in-
terface to define a new CircularQueue interface with such a behavior, as shown in
Code Fragment 6.12.

1 public interface CircularQueue<E> extends Queue<E> {

2 /∗∗
3 ∗ Rotates the front element of the queue to the back of the queue.
4 ∗ This does nothing if the queue is empty.
5 ∗/
6 void rotate( );
7 }
Code Fragment 6.12: A Java interface, CircularQueue, that extends the Queue ADT
with a new rotate( ) method.

This interface can easily be implemented by adapting the CircularlyLinkedList

class of Section 3.3 to produce a new LinkedCircularQueue class. This class has an
advantage over the traditional LinkedQueue, because a call to Q.rotate( ) is imple-
mented more efficiently than the combination of calls, Q.enqueue(Q.dequeue( )),
because no nodes are created, destroyed, or relinked by the implementation of a
rotate operation on a circularly linked list.
A circular queue is an excellent abstraction for applications in which elements
are cyclically arranged, such as for multiplayer, turn-based games, or round-robin
scheduling of computing processes. In the remainder of this section, we provide a
demonstration of the use of a circular queue.

The Josephus Problem

In the children’s game “hot potato,” a group of n children sit in a circle passing
an object, called the “potato,” around the circle. The potato begins with a starting
child in the circle, and the children continue passing the potato until a leader rings a
bell, at which point the child holding the potato must leave the game after handing
the potato to the next child in the circle. After the selected child leaves, the other
children close up the circle. This process is then continued until there is only one
child remaining, who is declared the winner. If the leader always uses the strategy
of ringing the bell so that every k th person is removed from the circle, for some
fixed value k, then determining the winner for a given list of children is known as the
Josephus problem (named after an ancient story with far more severe consequences
than in the children’s game).

www.it-ebooks.info
6.2. Queues 247
Solving the Josephus Problem Using a Queue
We can solve the Josephus problem for a collection of n elements using a circular
queue, by associating the potato with the element at the front of the queue and stor-
ing elements in the queue according to their order around the circle. Thus, passing
the potato is equivalent to rotating the first element to the back of the queue. After
this process has been performed k − 1 times, we remove the front element by de-
queuing it from the queue and discarding it. We show a complete Java program for
solving the Josephus problem using this approach in Code Fragment 6.13, which
describes a solution that runs in O(nk) time. (We can solve this problem faster
using techniques beyond the scope of this book.)

1 public class Josephus {

2 /∗∗ Computes the winner of the Josephus problem using a circular queue. ∗/
3 public static <E> E Josephus(CircularQueue<E> queue, int k) {
4 if (queue.isEmpty( )) return null;
5 while (queue.size( ) > 1) {
6 for (int i=0; i < k−1; i++) // skip past k-1 elements
7 queue.rotate( );
8 E e = queue.dequeue( ); // remove the front element from the collection
9 System.out.println(" " + e + " is out");
10 }
11 return queue.dequeue( ); // the winner
12 }
13
14 /∗∗ Builds a circular queue from an array of objects. ∗/
15 public static <E> CircularQueue<E> buildQueue(E a[ ]) {
16 CircularQueue<E> queue = new LinkedCircularQueue<>( );
17 for (int i=0; i<a.length; i++)
18 queue.enqueue(a[i]);
19 return queue;
20 }
21
22 /∗∗ Tester method ∗/
23 public static void main(String[ ] args) {
24 String[ ] a1 = {"Alice", "Bob", "Cindy", "Doug", "Ed", "Fred"};
25 String[ ] a2 = {"Gene", "Hope", "Irene", "Jack", "Kim", "Lance"};
26 String[ ] a3 = {"Mike", "Roberto"};
27 System.out.println("First winner is " + Josephus(buildQueue(a1), 3));
28 System.out.println("Second winner is " + Josephus(buildQueue(a2), 10));
29 System.out.println("Third winner is " + Josephus(buildQueue(a3), 7));
30 }
31 }
Code Fragment 6.13: A complete Java program for solving the Josephus problem
using a circular queue.

www.it-ebooks.info
248 Chapter 6. Stacks, Queues, and Deques

6.3 Double-Ended Queues

We next consider a queue-like data structure that supports insertion and deletion
at both the front and the back of the queue. Such a structure is called a double-
ended queue, or deque, which is usually pronounced “deck” to avoid confusion
with the dequeue method of the regular queue ADT, which is pronounced like the
abbreviation “D.Q.”
The deque abstract data type is more general than both the stack and the queue
ADTs. The extra generality can be useful in some applications. For example, we
described a restaurant using a queue to maintain a waitlist. Occasionally, the first
person might be removed from the queue only to find that a table was not available;
typically, the restaurant will reinsert the person at the first position in the queue. It
may also be that a customer at the end of the queue may grow impatient and leave
the restaurant. (We will need an even more general data structure if we want to
model customers leaving the queue from other positions.)

6.3.1 The Deque Abstract Data Type

The deque abstract data type is richer than both the stack and the queue ADTs.
To provide a symmetrical abstraction, the deque ADT is defined to support the
following update methods:

addFirst(e): Insert a new element e at the front of the deque.

addLast(e): Insert a new element e at the back of the deque.
removeFirst( ): Remove and return the first element of the deque
(or null if the deque is empty).
removeLast( ): Remove and return the last element of the deque
(or null if the deque is empty).

Additionally, the deque ADT will include the following accessors:

first( ): Returns the first element of the deque, without removing it
(or null if the deque is empty).
last( ): Returns the last element of the deque, without removing it
(or null if the deque is empty).
size( ): Returns the number of elements in the deque.
isEmpty( ): Returns a boolean indicating whether the deque is empty.

We formalize the deque ADT with the Java interface shown in Code Fragment 6.14.

www.it-ebooks.info
6.3. Double-Ended Queues 249

1 /∗∗
2 ∗ Interface for a double-ended queue: a collection of elements that can be inserted
3 ∗ and removed at both ends; this interface is a simplified version of java.util.Deque.
4 ∗/
5 public interface Deque<E> {
6 /∗∗ Returns the number of elements in the deque. ∗/
7 int size( );
8 /∗∗ Tests whether the deque is empty. ∗/
9 boolean isEmpty( );
10 /∗∗ Returns, but does not remove, the first element of the deque (null if empty). ∗/
11 E first( );
12 /∗∗ Returns, but does not remove, the last element of the deque (null if empty). ∗/
13 E last( );
14 /∗∗ Inserts an element at the front of the deque. ∗/
15 void addFirst(E e);
16 /∗∗ Inserts an element at the back of the deque. ∗/
17 void addLast(E e);
18 /∗∗ Removes and returns the first element of the deque (null if empty). ∗/
19 E removeFirst( );
20 /∗∗ Removes and returns the last element of the deque (null if empty). ∗/
21 E removeLast( );
22 }
Code Fragment 6.14: A Java interface, Deque, describing the double-ended queue
ADT. Note the use of the generic parameterized type, E, allowing a deque to contain
elements of any specified class.

Example 6.5: The following table shows a series of operations and their effects
on an initially empty deque D of integers.

Method Return Value D

addLast(5) – (5)
addFirst(3) – (3, 5)
addFirst(7) – (7, 3, 5)
first( ) 7 (7, 3, 5)
removeLast( ) 5 (7, 3)
size( ) 2 (7, 3)
removeLast( ) 3 (7)
removeFirst( ) 7 ()
addFirst(6) – (6)
last( ) 6 (6)
addFirst(8) – (8, 6)
isEmpty( ) false (8, 6)
last( ) 6 (8, 6)

www.it-ebooks.info
250 Chapter 6. Stacks, Queues, and Deques

6.3.2 Implementing a Deque

We can implement the deque ADT efficiently using either an array or a linked list
for storing elements.

Implementing a Deque with a Circular Array

If using an array, we recommend a representation similar to the ArrayQueue class,
treating the array in circular fashion and storing the index of the first element and
the current size of the deque as fields; the index of the last element can be calcu-
lated, as needed, using modular arithmetic.
One extra concern is avoiding use of negative values with the modulo operator.
When removing the first element, the front index is advanced in circular fashion,
with the assignment f = (f+1) % N. But when an element is inserted at the front,
the first index must effectively be decremented in circular fashion and it is a mistake
to assign f = (f−1) % N. The problem is that when f is 0, the goal should be to
“decrement” it to the other end of the array, and thus to index N−1. However, a
calculation such as −1 % 10 in Java results in the value −1. A standard way to
decrement an index circularly is instead to assign f = (f−1+N) % N. Adding the
additional term of N before the modulus is calculated assures that the result is a
positive value. We leave details of this approach to Exercise P-6.40.

Implementing a Deque with a Doubly Linked List

Because the deque requires insertion and removal at both ends, a doubly linked
list is most appropriate for implementing all operations efficiently. In fact, the
DoublyLinkedList class from Section 3.4.1 already implements the entire Deque
interface; we simply need to add the declaration “implements Deque<E>” to
that class definition in order to use it as a deque.

Performance of the Deque Operations

Table 6.5 shows the running times of methods for a deque implemented with a
doubly linked list. Note that every method runs in O(1) time.

Method Running Time

size, isEmpty O(1)
first, last O(1)
addFirst, addLast O(1)
removeFirst, removeLast O(1)
Table 6.5: Performance of a deque realized by either a circular array or a doubly
linked list. The space usage for the array-based implementation is O(N), where N
is the size of the array, while the space usage of the doubly linked list is O(n) where
n < N is the actual number of elements in the deque.

www.it-ebooks.info
6.3. Double-Ended Queues 251

6.3.3 Deques in the Java Collections Framework

The Java Collections Framework includes its own definition of a deque, as the
java.util.Deque interface, as well as several implementations of the interface in-
cluding one based on use of a circular array (java.util.ArrayDeque) and one based
on use of a doubly linked list (java.util.LinkedList). So, if we need to use a deque
and would rather not implement one from scratch, we can simply use one of those
built-in classes.
As is the case with the java.util.Queue class (see page 240), the java.util.Deque
provides duplicative methods that use different techniques to signal exceptional
cases. A summary of those methods is given in Table 6.6.

Our Deque ADT Interface java.util.Deque

throws exceptions returns special value
first( ) getFirst( ) peekFirst( )
last( ) getLast( ) peekLast( )
addFirst(e) addFirst(e) offerFirst(e)
addLast(e) addLast(e) offerLast(e)
removeFirst( ) removeFirst( ) pollFirst( )
removeLast( ) removeLast( ) pollLast( )
size( ) size( )
isEmpty( ) isEmpty( )

Table 6.6: Methods of our deque ADT and the corresponding methods of the
java.util.Deque interface.

When attempting to access or remove the first or last element of an empty deque,
the methods in the middle column of Table 6.6—that is, getFirst( ), getLast( ),
removeFirst( ), and removeLast( )—throw a NoSuchElementException. The meth-
ods in the rightmost column—that is, peekFirst( ), peekLast( ), pollFirst( ), and
pollLast( )—simply return the null reference when a deque is empty. In similar
manner, when attempting to add an element to an end of a deque with a capacity
limit, the addFirst and addLast methods throw an exception, while the offerFirst
and offerLast methods return false.
The methods that handle bad situations more gracefully (i.e., without throwing
exceptions) are useful in applications, known as producer-consumer scenarios, in
which it is common for one component of software to look for an element that may
have been placed in a queue by another program, or in which it is common to try to
insert an item into a fixed-sized buffer that might be full. However, having methods
return null when empty are not appropriate for applications in which null might
serve as an actual element of a queue.

www.it-ebooks.info
252 Chapter 6. Stacks, Queues, and Deques

6.4 Exercises
Reinforcement
R-6.1 Suppose an initially empty stack S has performed a total of 25 push operations,
12 top operations, and 10 pop operations, 3 of which returned null to indicate an
empty stack. What is the current size of S?
R-6.2 Had the stack of the previous problem been an instance of the ArrayStack class,
from Code Fragment 6.2, what would be the final value of the instance vari-
able t?
R-6.3 What values are returned during the following series of stack operations, if exe-
cuted upon an initially empty stack? push(5), push(3), pop(), push(2), push(8),
pop(), pop(), push(9), push(1), pop(), push(7), push(6), pop(), pop(), push(4),
pop(), pop().
R-6.4 Implement a method with signature transfer(S, T ) that transfers all elements
from stack S onto stack T , so that the element that starts at the top of S is the first
to be inserted onto T , and the element at the bottom of S ends up at the top of T .
R-6.5 Give a recursive method for removing all the elements from a stack.
R-6.6 Give a precise and complete definition of the concept of matching for grouping
symbols in an arithmetic expression. Your definition may be recursive.
R-6.7 Suppose an initially empty queue Q has performed a total of 32 enqueue opera-
tions, 10 first operations, and 15 dequeue operations, 5 of which returned null to
indicate an empty queue. What is the current size of Q?
R-6.8 Had the queue of the previous problem been an instance of the ArrayQueue class,
from Code Fragment 6.10, with capacity 30 never exceeded, what would be the
final value of the instance variable f?
R-6.9 What values are returned during the following sequence of queue operations, if
executed on an initially empty queue? enqueue(5), enqueue(3), dequeue(),
enqueue(2), enqueue(8), dequeue(), dequeue(), enqueue(9), enqueue(1),
dequeue(), enqueue(7), enqueue(6), dequeue(), dequeue(), enqueue(4),
dequeue(), dequeue().
R-6.10 Give a simple adapter that implements the stack ADT while using an instance of
a deque for storage.
R-6.11 Give a simple adapter that implements the queue ADT while using an instance
of a deque for storage.
R-6.12 What values are returned during the following sequence of deque ADT
operations, on an initially empty deque? addFirst(3), addLast(8), addLast(9),
addFirst(1), last( ), isEmpty( ), addFirst(2), removeLast( ), addLast(7), first( ),
last( ), addLast(4), size( ), removeFirst( ), removeFirst( ).

www.it-ebooks.info