19. Recursion
In order to understand recursion, you must first understand recursion.
19.1. Problem: Maze of doom
The evil mastermind from Chapter 13 has returned with a new attempt at world domination. Since he now knows that you can use concurrency to crack his security code, this time he’s hidden his deadly virus in a secret location protected by a complex maze of walls and passageways. Fortunately, you’ve been able to get a copy of the maze floor plan, but now you must write a program to find a path through it so you can steal the deadly virus before the evil mastermind unleashes it on the world.
Finding a path through a maze involves systematically exploring twists
and turns, keeping track of where you’ve been, backtracking out of dead
ends, and producing a resulting path once you make it through. You
already have the basic tools necessary to solve this problem. You can,
for example, represent the maze with a two-dimensional array of
characters, where a plus (''+) represents a wall and a space (' ')
represents a passageway. You could mark a path through the maze by
replacing a contiguous (vertical and horizontal but not diagonal)
sequence of ' ' characters by '*' characters, leading from the
starting square to the final square where the deadly virus is located.
The difficulties are dead ends and, worse, loops. How do you keep track of which paths you’ve tried that didn’t work? While you could use additional data structures to store this information, recursion is a solution technique that makes solving problems like this one surprisingly straightforward.
19.2. Concepts: Recursive problem solving
The idea that we’ll use to solve this maze problem is called recursion. Imagine you’re in a maze and have the choice to go right, left, or straight. No matter which of the three paths you take, you’ll probably be confronted by more choices of going right, left, or straight as you progress. You need to explore them all systematically. The process of systematically exploring the right path is similar to the process of systematically exploring the left path. The choice at this moment between left, right, and straight is in fact part of the same systematic process you want to follow when you’re in the left, right, or straight branches of the maze.
Solutions that can be described in terms of themselves are recursive. But what is recursion? How can describing something in terms of itself be useful? Since recursion sounds circular, how can it be applied to problem solving in Java? How does the computer keep track of these self-references? The following subsections address these questions.
19.2.1. What is recursion?
In the context of computer science and mathematics, recursion means describing some repetitive process in terms of itself. Many complex things can be described elegantly using recursion.
Consider the question, “How old are you now?” If you’re 27, you could answer, “I’m one year older than I was last year.” If then asked, “Well, how old were you last year?” Again, you could answer, “I was one year older than I was the year before.” Assuming that the person who wanted to wanted to know your age was very patient, you could repeat this answer over and over, explaining that each year you’ve been one year older than the previous year. However, after being asked 27 times about your age on the previous year, you’d run out of years of life and be forced to answer, “Zero years old.”
This absurd dialog shows an important feature of useful recursive definitions: They have at least one base case and at least one recursive case. The base case is the part of the definition that’s not described in terms of itself. It’s a concrete answer. Without the base case, the process would never end, and the definition would be meaningless. The recursive case is the part of the definition that is defined in terms of itself. Without the recursive case, the definition could only describe a finite set of things.
In the example above, the base case is being zero years old. You have no age before that. The recursive case is any age greater than zero . We can use mathematical notation to describe your age in a given year. Here age(year) is a function that gives the age you were during year.
To be meaningful, recursive cases should be defined in terms of simpler or smaller values. In English, it’s equally correct to say that you are now a year younger than you’ll be next year. Unfortunately, the age that you’ll be next year is not any closer to a base case, making that recursion useless.
A recursive definition for your age suggests that recursion is all around us. Though recursive definitions written in formal notation might seem artificial, self-similarity is a constant theme in art and nature. The branching of a trunk of a tree is similar to the branching of its limbs, which is similar to the branching of its branches, which in turn is similar to the branching of its twigs. In fact, we borrow the idea of the branching of a tree to define a recursive data structure in Section 19.4. Figure 19.2 starts with a simple Y-shaped branching. By successively replacing the branches with the previous shape, a tree is generated recursively. Fractals are images generated by similar recursive techniques. Although many real trees exhibit recursive tendencies, they don’t follow rules consistently or rigidly.
19.2.2. Recursive definitions
Although recursion crops up throughout the world, certain forms of recursion are more useful for solving problems. As with many aspects of programming, the recursion we use has a strong connection to mathematical principles.
In mathematics, a recursive definition is one that is defined in terms of itself. It’s common to define functions, sequences, and sets recursively. Functions, such as f(n), are usually defined in relation to the same function with a smaller input, such as f(n - 1). Sequences, such as sn, are usually defined in relation to earlier elements in the sequence, such as sn-1.
Even very common functions can be defined recursively. Consider the multiplication x ⋅ y. This multiplication means repeatedly adding x a total of y times. If y is a positive integer, we can describe this multiplication with the following recursive definition. Note the base case and recursive case.
Multiplication seems like such a basic operation that there would be no need to have such a definition. Yet mathematicians often use multiple equivalent definitions to prove results. Furthermore, this elementary definition provides intuition for creating more complex definitions.
Another mathematical function with a natural recursive definition is the factorial function, often written n!. The factorial function is used heavily in probability and counting. The value of n! = n ⋅ (n - 1) ⋅ (n - 2) ⋅ … ⋅ 3 ⋅ 2 ⋅ 1. Mathematicians like recursive definitions because they’re able to describe functions and sequences precisely without using ellipses (…).
Note that the base case gives 1 as the answer when n = 0. By convention 0! = 1. Thus, this definition correctly gives 0! = 1, 1! = 1 ⋅ 0! = 1, 2! = 2 ⋅ 1! = 2, 3! = 3 ⋅ 2! = 6, and so on.
The Fibonacci sequence is an infinite sequence of integers starting with 1, 1, 2, 3, 5, 8, 13, 21, …. Each term after the two initial 1s is the sum of the previous two terms in the sequence. Fibonacci has many interesting properties and crops up in surprisingly diverse areas of mathematics. It was originally developed to model the growth of rabbit populations.
The Fibonacci sequence also has a natural recursive mathematical definition. Indeed, you may have noticed that we described each term as the sum of the two previous terms. We can formally define the nth Fibonacci number Fn as follows, starting with n = 0.
Since the Fn depends on the two previous terms, it’s necessary to have two base cases. The Fibonacci sequence is a special kind of Lucas sequence. Other Lucas sequences specify different values for the two base cases and sometimes coefficients to multiply the previous terms by.
19.2.3. Iteration vs. recursion
These mathematical definitions are interesting, but what’s their
relationship to Java code? So far, we’ve considered algorithms that
are iterative in nature: processing is performed as a sequence of
operations on elements of a sequential data structure. We sum the
elements of an array by iterating through them from first to last. We
multiply two matrices by using nested for loops to sequence through
the matrix contents in the proper order. Similarly, one method might make
a sequence of one or more calls to other methods. We’re confident that
such computations terminate because we start at the beginning and work
to the end of a finite structure. But what if the structure is not a
simple linear or multidimensional array? The path we’re trying to find
through the maze is of unknown length and complexity.
A method might call other methods to complete its operation. For example,
a method that sorts a list of String values calls another method to do
pairwise comparison of the values in the list. A method that calls
itself, either directly or indirectly, is called a recursive method.
A recursive method might seem like a circular argument that never ends. In fact, a recursive method only calls itself under certain circumstances. In other circumstances, it does not. A recursive method has the same two parts that a mathematical recursive definition has.
-
Base case
The operation being computed is done without any recursive calls. -
Recursive case
The operation is broken down into smaller pieces, one or more of which results in a recursive call to the method itself.
Each time a method calls itself recursively it does so on a smaller problem. Eventually, it reaches a base case, and the recursion terminates.
A recursive method is useful when a problem can be broken down into smaller subproblems where each subproblem has the same structure as the original, complete problem. These subproblems can be solved by recursive calls and the results of those calls assembled to create a larger solution.
Recursive methods are often surprisingly small given their complexity. Each recursive call only makes a single step forward in the process of solving the problem. In fact, it can appear that the problem is never solved. The code has something like a “leap of faith” inside of it. Assuming you can solve a smaller subproblem, how do you put the solutions together to solve the full problem? This assumption is the leap of faith, but it works out as long as the subproblems get broken down into smaller and smaller pieces that eventually reach a base case.
From a theoretical standpoint, any problem that can be solved iteratively can be solved recursively, and vice versa. Iteration and recursion are equivalent in computational power. Sometimes it’s more efficient or more elegant to use one approach or the other, and some languages are designed to work better with a particular approach.
19.2.4. Call stack
Many programmers who are new to recursion feel uncomfortable about the syntax. How can a method call itself? What does that even mean?
Recursion in Java is grounded in the idea of a call stack. We discuss the stack abstract data type in Chapter 18. A similar structure is used to control the flow of control of a program as it calls methods.
Recall that a stack is a first in, last out (FILO) data structure. Each time a method is called, its local variables are put on the call stack. As the method executes, a pointer to the current operation it’s executing is kept on the call stack as well. This collection of local variables and execution details for a method call is called the stack frame or activation record. When another method is called, it pushes its own stack frame onto the call stack as well, and its caller remembers what it was executing before the call. When a method returns, it pops its stack frame (the variables and state associated with its execution) off the call stack.
A recursive method is called in exactly the same way. It puts another copy of its stack frame on the call stack. Each call of the method has its own stack frame and operates independently. There’s no way to access the variables from one call to the next, other than by passing in parameters or returning values.
Figure 19.3 shows the stack frames being pushed
onto the call stack as the main() method calls the factorial()
method, starting with the argument 4. The factorial() method
recursively calls itself with successively smaller values.
Figure 19.4 shows the stack frames popping off
the call stack as each call to factorial() returns. As the answers are
returned, they’re incorporated into the answer that’s generated and
returned to the next caller in the sequence until the final answer 24
(4!) is returned to main().
19.3. Syntax: Recursive methods
Unlike many Syntax sections in other chapters, there’s no new Java syntax to introduce here. Any method that calls itself, directly or indirectly, is a recursive method. Recursive methods are simply methods like any others, called in the normal way.
The real difficulty in learning to program recursively lies in breaking out of the way you’re used to thinking about program control flow. All that you’ve learned about solving problems with iteration in previous chapters might make it harder for you to embrace recursion.
Iteration views the whole problem at once and tries to sequence all the pieces of the solution in some organized way. Recursion is only concerned with the current step in the solution. If the current step is one in which the answer is clear, you’re in a base case. Otherwise, the solution takes one step toward the answer and then makes the leap of faith, allowing the recursion to take care of the rest. Programmers who are new to recursion are often tempted to do too much in each recursive call. Don’t rush it!
The use of recursion in languages like Java owes much to the development of functional programming. In many functional languages (such as Scheme), there are no loops, and only recursion is allowed. In a number of these languages, there’s no assignment either. Each variable has one value for its entire lifetime, and that value comes as a parameter from whatever method called the current method.
It may seem odd to you, but this approach is a good one to follow when writing recursive methods. Try not to assign variables inside your methods. See if the work done in each method can be passed on as an argument to the next method rather than changing the state inside the current method. In that way, each recursive method is a frozen snapshot of some part of the process of solving the problem. Of course, this guideline is only a suggestion. Many practical recursive methods need to assign variables internally, but a surprisingly large number do not.
Because the data inside these methods is tied so closely to the input
parameters and the return values given back to the caller, these methods
are often made static. Ideally, recursive methods do not change the
state of fields or class variables. Again, sometimes changing external
state is necessary, but recursive methods are meant to take in only
their input parameters and give back only return values. Recursive code
that reads and writes variables inside of objects or classes can be
difficult to understand and debug since it depends on outside data.
With this information as background, we focus on examples for the rest of this section. Because recursion is a new way of thinking, approach these examples with an open mind. Many students have the experience that recursion makes no sense until they see the right example. Then, the way it works suddenly “clicks.” Don’t be discouraged if recursion seems difficult at first.
In this section, we work through examples of factorial computation, Fibonacci numbers, the classic Tower of Hanoi problem, and exponentiation. These problems are mathematical in nature because mathematical recursion is easy to model in code. The next section applies recursion to processing data structures.
In our first example of a recursive implementation, we return to the factorial function. Recall the recursive definition that describes the function.
By translating this mathematical definition almost directly into Java, we can generate a method that computes the factorial function.
public static long factorial(int n) {
if(n == 0) // Base case
return 1;
else // Recursive case
return n * factorial(n-1);
}Note the base case and recursive case are exactly the same as in the
recursive definition. The return type of the method is long because
factorial grows so quickly that only the first few values are small
enough to fit inside of an int.
Let’s return to the recursive definition of Fibonacci.
Like factorial, this definition translates naturally into a recursive method in Java.
public static int fibonacci(int n) {
if(n == 0 || n == 1) // Base cases
return 1;
else // Recursive case
return fibonacci(n-1) + fibonacci(n-2);
}One significant problem with this implementation is performance. In this case, the double recursion performs a great deal of redundant computation.
One technique for eliminating redundant computation in recursion is called memoization. Whenever the value for a subproblem is computed, we note down the result (like a memo). When we go to compute a value, we first check to see if we have already found it.
To perform memoization for Fibonacci, we can pass an array of int
values of length n + 1. The values in this array all begin with a
value of 0. When computing the Fibonacci value for a particular n,
we first check to see if its value is in the array. If not, we perform
the recursion and store the result in the array.
public static int fibonacci(int n, int[] results) {
if(results[n] == 0) {
if(n == 0 || n == 1)
results[n] = 1;
else
results[n] = fibonacci(n-1) + fibonacci(n-2);
}
return results[n];
}This change makes the computation of the nth Fibonacci number much more efficient; however, even more efficient approaches are described in the exercises.
The famous Tower of Hanoi puzzle is another example commonly used to illustrate recursion. In this puzzle, there are three poles containing a number of different sized disks. The puzzle begins with all disks arranged in a tower on one pole in decreasing size, with the smallest diameter disk on top and the largest on the bottom. Figure 19.5 shows an example of the puzzle. The goal is to move all the disks from the initial pole to the final pole, with two restrictions.
-
Only one disk can be moved at a time.
-
A larger disk can never be placed on top of a smaller disk.
The extra pole is used as a holder for intermediate moves. The idea behind the recursive solution follows.
-
Base Case
Moving one disk is easy. Just move it from the pole it’s on to the destination pole. -
Recursive Case
In order to move n > 1 disks from one pole to another, we can move n - 1 disks to an intermediate pole, move the nth disk to the destination pole, and then move the n - 1 disks from the intermediate pole to the destination pole.
The Tower of Hanoi solution in Java translates this outline into code.
'A', 'B', and 'C'.public class TowerOfHanoi {
public static void main(String[] args) {
move(4, 'A', 'C', 'B');
}
public static void move(int n, char fromPole, char toPole, char viaPole) {
if(n == 1)
System.out.format("Move disk from pole %c to pole %c.\n",
fromPole, toPole);
else {
move(n - 1, fromPole, viaPole, toPole);
move(1, fromPole, toPole, viaPole);
move(n - 1, viaPole, toPole, fromPole);
}
}
}A legend tells of monks that are solving the Tower of Hanoi puzzle with 64 disks. The legend predicts that the world will end when they finish. Run the implementation above with different numbers of disks to see how long the sequence of moves is. Try small numbers of disks, since large numbers of disks take a very long time.
Both Fibonacci and the Tower of Hanoi have natural recursive structures. In the case of Fibonacci, one way to implement its natural recursive definition results in very wasteful computation. In the case of the Tower of Hanoi, the only way to solve the problem takes an excruciatingly long amount of time.
However, we can apply recursion to many practical problems and get efficient solutions. Consider the problem of exponentiation, which looks trivial: Given a rational number a and a positive integer n, find the value of an.
It’s tempting to call Math.pow(a, n) or to use a short for loop to
compute this value, but what if neither tool existed in Java? A simple
recursive formulation can describe exponentiation.
As with factorial and Fibonacci, directly converting the recursive definition into Java syntax yields a method that computes the correct value.
public static double power(double a, int n) {
if(n == 1) // Base case
return a;
else // Recursive case
return a*power(a, n - 1);
}Admittedly, this method only works for positive integer values of
n. Ignoring that limitation, what can we say about its
efficiency? For any legal value of n, the method is called
n times. If n has a small value, like 2 or
3, the process is quick. But if n is 1,000,000 or so, the
method might take a while to finish. Another problem is that stack size
is limited. On most systems, the JVM crashes with a StackOverflowError
if a method tries to call itself recursively 1,000,000 times.
If we limit n to a power of 2, we can do something clever that makes the method much more efficient with many fewer recursive calls. Consider this alternative recursive definition of exponentiation.
Recalling basic rules of exponents, it’s true that an = (an/2)2, but what does that buy us? If we structure our method correctly, we cut the size of n in half at each recursive step instead of only reducing n by 1.
public static double power(double a, int n) {
if(n == 1) // Base case
return a;
else { // Recursive case
double temp = power(a, n/2);
return temp*temp;
}
}Note that we only make the recursive call once and save its result in temp.
If we made two recursive calls, we would no longer be more efficient than
the previous method. That version took n recursive calls.
How efficient is this version? The answer is the number of times you
have to cut n in half before you get 1. Let’s call that
value x. Recall that n is a power of 2,
meaning that n = 2k for some integer
k ≥ 0.
In other words, the number of times you have to divide n
in half to get 1 is the logarithm base 2 of n, written
log2 n. The logarithm function is the inverse of
exponentiation. It cuts any number down to size very quickly (just as
exponentiation blows up the value of a number very quickly). For
example, 220 = 1,048,576. Thus,
log2 1,048,576 = 20. The original version of power()
would have to make 1,048,576 calls to raise a number to that power. This
second version would only have to make 20 calls.
It’s critical that n is a power of 2 (1, 2, 4, 8, …); otherwise, the process of repeatedly cutting n in half loses some data due to integer division. The problem is that, at some point in the recursion, the value of n will become odd unless you start with a power of 2. There’s a way to extend this clever approach to all values of n, even and odd, but we leave it as an exercise.
Recursion offers elegant ways to compute mathematical functions like those we’ve explored in this section. Recursion also offers powerful ways to manipulate data structures. As we show in the next section, recursive methods are especially well suited to use with recursive data structures.
19.4. Syntax: Recursive data structures
Because recursion can be used to do anything that iteration can do, it’s
clear that data structures can be processed recursively. For example,
the following recursive method reverses the contents of an array. It
keeps track of the position it’s swapping in the array with the
position parameter. This method is initially called with a value of
0 passed as an argument for position.
public static void reverse(int[] array, int position) {
if(position < array.length/2) {
int temp = array[position];
array[position] = array[array.length - position - 1];
array[array.length - position - 1] = temp;
reverse(array, position + 1);
}
}Note that nothing is done in the base case for this recursive method.
The recursion swaps the first element of the array (at index 0) with
the last (at index array.length - 1). Recursion continues until
position has reached half the length of array. If execution
continued past the halfway point, it would begin to re-swap elements that
had already been swapped.
Although it’s possible to reverse an array recursively, there’s usually no advantage in doing so. We introduced bubble sort and selection sort in previous chapters, but neither of these algorithms is very fast. Many of the best sorting algorithms are recursive, as in the following example of merge sort.
Merge sort is an efficient sorting algorithm that’s often implemented recursively. The idea of the sort is to break a list of items in half and recursively merge sort each half. Then, these two sorted halves are merged back together into the final sorted list. The base case of the recursion is when there’s only a single item in the list, since a list with only one thing in it is, by definition, sorted.
Here’s a method that recursively sorts an int array using the merge
sort algorithm.
public static void mergeSort(int[] array) {
if(array.length > 1) {
int[] a = new int[array.length/2];
int[] b = new int[array.length - a.length];
for(int i = 0; i < a.length; ++i)
a[i] = array[i];
for(int i = 0; i < b.length; ++i)
b[i] = array[a.length + i];
mergeSort(a);
mergeSort(b);
merge(array, a, b);
}
}The mergeSort() method is quite short and appears to do very little.
It starts by creating arrays a and b and copying roughly half of the
elements in array into each. We make a half the size of array, but
we can’t do the same thing for b because an odd length for array
would leave us without enough space in a and b to hold everything
from array. Instead, we let b hold however much is leftover after
the elements for a have been accounted for.
Then, arrays a and b are recursively sorted. Finally, these two
sorted arrays are merged back into array in sorted order using a
helper method called merge(). This method is non-recursive and does
much of the real work in the algorithm.
public static void merge(int[] array, int[] a, int[] b) {
int aIndex = 0;
int bIndex = 0;
for(int i = 0; i < array.length; ++i) {
if(bIndex >= b.length)
array[i] = a[aIndex++];
else if(aIndex >= a.length)
array[i] = b[bIndex++];
else if(a[aIndex] <= b[bIndex])
array[i] = a[aIndex++];
else
array[i] = b[bIndex++];
}
}The merge() method loops through all the elements in array, filling
them in. We keep two indexes, aIndex and bIndex, that keep track of
our current positions in the a and b arrays, respectively. This
method assumes that a and b are sorted and that the sum of their
lengths is the length of array. We want to compare each element in a
and b, always taking the smaller and putting it into the next
available location in array. Since the next smallest item could be in
either a or b, we never know when we’ll run out of elements in
either array. That’s why the first two if statements in the merge()
method check to see if the bIndex or the aIndex is already past the
last element in its respective array. If so, the next element from the
other array is automatically used. By the time the third if statement
is reached, we’re certain that both indexes are valid and can compare
the elements at those locations to see which is smaller.
Sorting lists using the merge sort algorithm seems more complicated than using bubble sort or selection sort, but this additional complication pays dividends. For large lists, merge sort performs much faster than either of those sorts. In fact, its speed is comparable to the best general sorting algorithms that are possible.
Although recursive sorting algorithms are useful for arrays, recursion
really shines when manipulating recursive data structures. A recursive
data structure is one that’s defined in terms of itself. For example,
class X is recursive if there’s a field inside X with type X.
public class X {
private int a, b;
private X x;
}The linked list examples from
Chapter 18 are recursive
data structures, since a linked list node is defined in terms of itself. You
might not have thought of the linked list Node class as being recursive since
it simply has a reference to another Node inside it. However, this
self-reference is the essence of a recursive data structure.
Data structures are often defined recursively. We typically need to represent an unbounded collection of data, but we always write bounded programs to describe the data. A recursive data structure allows us to bridge the gap between a compile-time, fixed-length definition and a run-time, unbounded collection of objects.
Recursive data structures have a base case to end the recursion.
Typically, the end of the recursion is indicated by a link with a null
value. For example, in the last node of a linked list, the next field is
null. Unsurprisingly, recursive methods are frequently used to
manipulate recursive data structures.
How would you get the size of a linked list? The implementation in
Program 18.5 keeps track of its size as it grows, but
what if it didn’t? A standard way to count the elements in the list
would be to start with a reference to the head of the list and a counter
with value zero. As long as the reference is not null, add one to the
counter and set the reference to the next element on the list.
Program 19.2 counts the elements in this way.
size() method counts its elements iteratively.public class IterativeListSize {
private static class Node {
public String value;
public Node next;
}
private Node head = null;
public void add(String value) {
Node temp = new Node();
temp.value = value;
temp.next = head;
head = temp;
}
public int size() {
Node current = head;
int counter = 0;
while(current != null) {
current = current.next;
counter++;
}
return counter;
}
}An alternative way to count the number of elements in a linked list is
to use the natural recursion of the linked list itself. We can say that
the length of a linked list is 0 if the list is empty (the current link
is null); otherwise, it’s one more than the size of the rest of the
list.
Program 19.3 counts the elements in a linked
list using this recursive procedure. Note that there’s a non-recursive
size() method that calls the recursive size() method. This
non-recursive method is called a proxy method. The recursive method
requires access to the internals of the data structure. The proxy method
calls the recursive method with the appropriate starting point (head),
while providing a public way to get the list’s size without exposing its
internals.
size() method for counting its elements.public class RecursiveListSize {
private static class Node {
public String value;
public Node next;
}
private Node head = null;
public void add(String value) {
Node temp = new Node();
temp.value = value;
temp.next = head;
head = temp;
}
// Proxy method
public int size() {
return size(head);
}
private static int size(Node list) {
if(list == null) // Base case
return 0;
else
return 1 + size(list.next); // Recursive case
}
}19.4.1. Trees
A linked list models a linear, one-to-one relationship between its elements since each item in the list is linked to a maximum of one following item. Another useful relationship to model is a hierarchical, one-to-many relationship: parent to children, boss to employees, directory to files, and so on. These relationships can be modeled using a tree structure, which begins with a single root, and proceeds through branches to the leaves. Typically, the elements of a tree are also called nodes, with the three following special cases.
-
Root node
The root of the tree has no parents. -
Leaf node
A leaf is at the edge of a tree and has no children. -
Interior node
An interior node has a parent and at least one child. It’s neither the root nor a leaf.
Figure 19.6 shows a visualization of a tree. In nature, a tree has its root at the bottom and branches upward. Since the root is the starting point for a tree data structure, it’s almost always drawn at the top.
Abstractly, a tree is either empty (the base case) or contains
references to 0 or more other trees (the recursive case). Trees are
useful for storing and retrieving sorted data efficiently. Some
applications include dictionaries, catalogs, ordered lists, and any
other sorted set of objects. For these purposes, we can define an
abstract data type that includes operations such as add() and
find().
A special case of a tree that’s used frequently is a binary tree, in which each node references at most two other trees.
A binary search tree is a further special case of a binary tree with the following three properties.
-
The value in the left child of the root is smaller than the value in the root.
-
The value in the right child of the root is larger than the value in the root.
-
Both the left and the right subtrees are binary search trees.
This recursive definition describes a tree that makes items with a
natural ordering easy to find. If you’re looking for an item, you first
look at the root of the tree. If the item you want is in the root,
you’ve found it! If the item you want is smaller than the root, go left.
If the item you want is larger than the root, go right. If you ever run
out of tree nodes by hitting a null, the item isn’t in the tree.
This example is a simple binary tree that can store a list of String
values and print them out in alphabetical order. Program 19.4 shows
the Tree class that defines the fields and two public methods, add()
and print(), that operate on the tree. Each is a proxy method that
calls its private recursive version, which takes a reference to a Node
object. The Node static nested class contains three fields.
-
value: theStringvalue stored at the node -
left: a link to the left subtree -
right: a link to the right subtree
Strings values.public class Tree {
private static class Node {
public String value;
public Node left = null;
public Node right = null;
}
private Node root = null;
// Proxy add
public void add(String value) {
root = add(value, root);
}
private static Node add(String value, Node tree) {
if(tree == null) { // Base case (1)
tree = new Node();
tree.value = value;
}
// Left recursive case (2)
else if(value.compareTo(tree.value) < 0)
tree.left = add(value, tree.left);
// Right recursive case (3)
else if(value.compareTo(tree.value) > 0)
tree.right = add(value, tree.right);
return tree; (4)
}
// Proxy print
public void print() {
print(root);
}
private static void print(Node tree) {
if(tree != null) {
print(tree.left); (5)
System.out.println(tree.value); (6)
print(tree.right); (7)
}
}
}| 1 | The recursive add() method first checks to see if the current subtree
is empty (null). If so, it creates a new Node and puts value
inside it. |
| 2 | If the current subtree is not null, it checks to see if
value is smaller or larger than the value at the root of the subtree.
If it’s smaller, it recurses down the left subtree. |
| 3 | If it’s larger, it
recurses down the right subtree. If value is already in the root node,
it does nothing. |
| 4 | Remember that all parameters are pass by value in Java. Thus, assigning
a new Node to tree doesn’t by itself change anything at higher
levels of the tree. What does change the links in the parent of the
current subtree is returning the tree pointer. If the recursive call
to add() was made with a left or a right subtree, the left or
right link, respectively, of the parent Node is assigned the return
value. If the call was made with root, the parent of the entire tree,
the non-recursive add() method sets its value when the recursive
add() returns. |
| 5 | The recursive print() method starts by walking down the left subtree.
Those values are all alphabetically less than the value of the current
node. |
| 6 | When it finishes, it prints the current node value. |
| 7 | Finally, it walks the right subtree to print the values that alphabetically follow the value in the current node. This path through the nodes of the tree is called an inorder traversal. |
Figure 19.7 shows a visualization of the contents of
this implementation of a binary search tree. As with a linked list, an
“X” is used in place of arrows that point to null.
With the power of a binary search tree, it takes virtually no code at
all to store a list of String values and then print them out in sorted
order. Program 19.5 gives an example of this
process using a Tree object for storage.
String values, stores them in a binary search tree, and prints the results in sorted order.import java.util.Scanner;
public class ReadAndSortStrings {
public static void main(String[] args) {
Tree tree = new Tree();
Scanner in = new Scanner(System.in);
while(in.hasNextLine())
tree.add(in.nextLine());
tree.print();
}
}Binary search trees (and other trees, including heaps, tries, B-trees, and more) are fundamental data structures that have been studied heavily. Designing them to have efficient implementations that balance the size of their left and right subtrees is an important topic that’s beyond the scope of this book.
19.4.2. Generic dynamic data structures and recursion
Combining dynamic data structures and generics from the previous chapter and recursion from this chapter gives us the full power of generic dynamic data structures and recursive methods to process them.
Consider Program 19.6, which implements a tree that
stores values of type Integer. Although it would be more efficient to
store int values, we use the Integer wrapper class to ease our
eventual transition into a parameterized generic type.
public class IntegerTree {
private static class Node {
Integer value;
Node left = null;
Node right = null;
}
private Node root = null;
// Proxy add
public void add(Integer value) {
root = add(value, root);
}
private static Node add(Integer value, Node tree) {
if(tree == null) { // Base case
tree = new Node();
tree.value = value;
}
// Left recursive case
else if(value.compareTo(tree.value) < 0)
tree.left = add(value, tree.left);
// Right recursive case
else if(value.compareTo(tree.value) > 0)
tree.right = add(value, tree.right);
return tree;
}
// Proxy print
public void print() {
print(root);
}
private static void print(Node tree) {
if(tree != null) {
print(tree.left);
System.out.println(tree.value);
print(tree.right);
}
}
}It’s a waste to create class IntegerTree, which is identical to
Tree except that the type String has been replaced by Integer. As
in Section 18.5, we want our data
structures, recursive or otherwise, to hold any type. In this way, we
can reuse code across a wide range of applications.
Program 19.7 defines a generic version of the Tree
class. This example is complicated by the fact that we need to be able
to compare the value we want to store with the value in each Node
object. We can’t make a tree with any arbitrary type. Objects of the
type must have the ability to be compared to each other and ordered.
Thus, we use a bounded type parameter specifying that the type T
stored in each Tree must implement the Comparable interface. This
requirement complicates the generic syntax significantly but guarantees
that any type that cannot be compared with itself is rejected at
compile-time.
public class GenericTree<T extends Comparable<T>> {
private class Node {
T value;
Node left = null;
Node right = null;
}
private Node root = null;
// Proxy add
public void add(T value) {
root = add(value, root);
}
private Node add(T value, Node tree) {
if(tree == null) { // Base case
tree = new Node();
tree.value = value;
}
// Left recursive case
else if(value.compareTo(tree.value) < 0)
tree.left = add(value, tree.left);
// Right recursive case
else if(value.compareTo(tree.value) > 0)
tree.right = add(value, tree.right);
return tree;
}
// Proxy print
public void print() {
print(root);
}
private void print(Node tree) {
if(tree != null) {
print(tree.left);
System.out.println(tree.value);
print(tree.right);
}
}
}First, note that the Node class and the recursive methods are no longer
static. The generic syntax for keeping them static without producing
compiler warnings is unnecessarily complex. The type specifier T extends
Comparable<T> guarantees that type T implements the interface
Comparable<T>. The generic Comparable interface defined in the Java API
is as follows.
public interface Comparable<T> {
int compareTo(T object);
}The syntax for generics in Java with type bounds is complicated, and we only scratch the surface here. The good news is that these subtleties are more important for people designing data structures and libraries and come up infrequently for programmers who are only using the libraries.
Program 19.8 uses the generic tree class to
create two kinds of trees, a tree of String objects and a tree of
Integer objects. Java library implementations of binary search trees
are available as the TreeSet and TreeMap classes.
import java.util.Random;
import java.util.Scanner;
public class ReadAndSortGenerics {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
GenericTree<String> stringTree = new GenericTree<>();
GenericTree<Integer> integerTree = new GenericTree<>();
while(in.hasNextLine())
stringTree.add(in.nextLine());
stringTree.print();
Random random = new Random();
for (int i = 0; i < 10; i++)
integerTree.add(random.nextInt());
integerTree.print();
}
}19.5. Solution: Maze of doom
Our algorithm for solving the maze follows the conventional
pencil-and-paper method: trial and error! We mark locations in the maze
with '*' as we explore them. If we come to a dead end, we unmark the
location (by replacing '*' with ' ') and return to our previous
location to try a different direction.
We start at the beginning square of the maze, which must be a passageway.
We mark that location as part of the path by putting '*' in the cell.
Now, what can we do? There are, in general, four possible directions to
head: up, down, left, or right. If that direction doesn’t take us
outside the bounds of the array, then we find either a wall or a
passageway. If we’ve been walking through the maze, we might also find
a part of the current path (often the square we were on before the
current one).
Suppose from our current point in the maze we could send a scout ahead in each of the four directions. If the direction didn’t take the scout out of bounds, he would find either a wall, a part of the current path (the path that led into that space), or an open passageway. If the scout doesn’t find an open passageway, he reports back that that direction doesn’t work.
On the other hand, if the scout finds an open passageway, what does he do? Brace yourself! He does the exact same thing we just did: send out scouts of his own in each of the four possible directions.
With careful, consistent coding, the scout follows the exact same process we did. And the scout’s scouts. And so on. There is, in fact, only one method and instead of calling a scout method to investigate each of the squares in the four directions, we call our own method recursively.
import java.util.Scanner;
public class MazeSolver {
private char[][] maze; (1)
private final int ROWS, COLUMNS; (2)
public static void main(String[] args) {
MazeSolver solver = new MazeSolver(); (3)
if(solver.solve(0, 0))
System.out.println("\nSolved!");
else
System.out.println("\nNot solvable!");
solver.print(); (4)
} | 1 | The MazeSolver class needs a two-dimensional array of char values to
store a representation of the maze. |
| 2 | It’s also convenient to store the number of rows and columns as constant fields. |
| 3 | The main() method creates a new MazeSolver object and then calls its
solve() method with a starting location of (0, 0). It prints an
appropriate message depending on whether or not the maze was solved. |
| 4 | Finally, it prints out the maze, which includes a path marked with '*'
symbols if the maze is solvable. |
public MazeSolver() {
Scanner in = new Scanner(System.in); (1)
ROWS = in.nextInt(); (2)
COLUMNS = in.nextInt();
in.nextLine();
maze = new char[ROWS][COLUMNS]; (3)
for(int row = 0; row < ROWS; row++) { (4)
String line = in.nextLine();
System.out.println(line);
for (int column = 0; column < COLUMNS; column++)
maze[row][column] = line.charAt(column);
}
}| 1 | The constructor for MazeSolver creates a Scanner. It assumes that
the file describing the maze is redirected from standard input, although
it would be easy to modify the constructor to take a file name and read
from there instead. |
| 2 | Next, it reads two integers and sets the ROWS and
COLUMNS to those values, which will be constants moving forward. |
| 3 | It allocates a two-dimensional array of
char values with ROWS rows and COLUMNS columns. |
| 4 | Finally, it reads
through the file, storing each line of char values into this array. As
it reads, it prints out each line to the screen, showing the initial
(unsolved) maze. |
public void print() {
for(int row = 0; row < ROWS; row++) {
for (int column = 0; column < COLUMNS; column++)
System.out.print(maze[row][column]);
System.out.println();
}
}The print() method is a utility method that prints out the maze. It
iterates through each row, printing out the values for the columns in
that row.
public boolean solve(int row, int column) {
if(row < 0 || column < 0 || row >= ROWS || column >= COLUMNS)
return false;
else if(maze[row][column] == 'E')
return true;
else if(maze[row][column] != ' ')
return false;
else {
maze[row][column] = '*';
if(solve(row - 1, column) || solve(row + 1, column) ||
solve(row, column - 1) || solve(row, column + 1))
return true;
else {
maze[row][column] = ' ';
return false;
}
}
}
}The heart of the solution is the recursive method solve(). The
solve() method takes two parameters, row and column, and tries to
find a solution to the maze starting at location maze[row][column]. It
assumes that the maze is filled with '+' for walls, ' ' for
passageways, and may include '*' characters at locations that are part
of the partially completed solution.
If solve() is able to find a solution from the current location, it
returns true, otherwise it returns false. There are three base cases
for the current location in the maze.
-
The current location is outside the maze. Return
false. -
The current location is the ending location (marked with
'E'). We have a winner, returntrue! -
The current location is not a passage (either a wall or a location in the current path that’s already been marked). This call to
solveis not making progress toward the finish. Returnfalse.
If none of the base cases applies, then the current location, which must
contain a ' ' character, might be on a successful path, so solve()
gives it a try. The method tentatively marks the current position with
'*'. Then, it tries to find a path from the current
location to each of the four neighboring cells by recursively calling solve().
If any of those four neighbors returns true, then solve() knows it’s found
a completed path and returns true to its caller.
If none of the four neighbors was on a path to the destination, then the
current location is not on a path. The method unmarks the current
location (by storing a ' ') and returns false. Presumably, its
caller figures out what to do next, perhaps calling a different one of
its neighbors or giving up and returning false to its caller.
The very first call to solve() from the main() method either returns
true if a complete path through the maze is found or false if no
path exists. Note that this solver has no guarantee of finding the
shortest path through the maze, but if there’s at least one path to
the goal, it’ll find one.
19.6. Concurrency: Futures
This section doesn’t deal explicitly with recursion, but it does deal with concurrency and methods in an interesting way. When we call a method in Java, a stack frame for the method is put on the stack, and the thread of execution begins executing code inside the method. When it’s done, it returns a value (or not), and execution resumes in the caller. But what if calling the method began executing an independent thread, and the caller continued on without waiting for the method to return?
This second situation should seem familiar, since it’s exactly what
happens when the start() method is called on a Thread object: the
start() method returns immediately to its caller, but an independent
thread of execution has begun executing the code in the run() method
of the Thread.
What if we only care about the value that’s computed by the new thread of execution? We can think of spawning the thread as an asynchronous method call, a value that’s computed at some point rather than one we have to wait for. The name for such an asynchronous method call is a future. In some languages, particularly functional languages, all concurrency is expressed as a future. In Java, only a little bit of code is needed to create threads that can behave like futures. However, the idea of futures is pervasive enough that Java API tools were created to make the process of creating them simple.
We introduce three interfaces and a factory method call that can allow you to use futures in Java. This section is not a complete introduction to futures, but the tools presented are enough to get you started.
The first interface is the Future interface, which allows you to store
a reference to the asynchronous computation while it’s computing,
before you ask for its value. The second interface is the Callable
interface, which is similar to the Runnable interface in that it
allows you to specify a class whose objects can be started as
independent threads. Both the Future and Callable interfaces are
generic interfaces that require you to specify a type. Remember that futures
are supposed to give back an answer, and that’s the type you supply
as a parameter. For example, when creating a future that returns an
int value, you would create a class that implements the
Callable<Integer> interface, requiring it to contain a method with the
signature Integer call(). Likewise, you would store a reference to the
future you create in a Future<Integer> reference.
And how do you create such a future? Usually, many futures are running
at once to leverage the power of multiple cores. What if you want to
create 100 futures but only have 8 cores? The process of creating
threads is expensive, and it might not be worthwhile to create 100
threads when only 8 are able to run concurrently. To deal with this
problem, the Java API provides classes that implement the
ExecutorService interface, which can maintain a fixed-size pool of
threads. When a thread finishes computing one future, it’s
automatically assigned another. To create an object that can manage
threads this way, call the static factory method newFixedThreadPool()
on the Executors class with the size of the thread pool you want
create. For example, we can create an ExecutorService with a pool of 8
threads as follows.
ExecutorService executor = Executors.newFixedThreadPool(8);Once you have an ExecutorService, you can give it a Callable object
of a particular type (such as Callable<Integer>) as a parameter to its
submit() method, and it will return a Future object of a matching type
(such as Future<Integer>). Then, the future is running (or at least
scheduled to run). At any later point you can call the get() method on
the Future object, which returns the value of its computation. Like
calling join(), calling get() is a blocking call that might have to
wait for the future to finish executing.
All this messy syntax should become clearer in the following example which uses futures to compute the sum of the square roots of the first 100,000,000 integers concurrently.
To use futures to sum the square roots of integers, we first need a
worker class that implements Callable. Since the result of the sum of
square roots is a double, it must implement Callable<Double>. Recall
that primitive types such as double can’t be used as generic type
parameters, requiring us to use wrapper classes in those cases.
import java.util.concurrent.*; (1)
public class RootSummer implements Callable<Double> {
private int min;
private int max;
public RootSummer(int min, int max) { (2)
this.min = min;
this.max = max;
}
public Double call() { (3)
double sum = 0.0;
for(int i = min; i < max; ++i)
sum += Math.sqrt(i);
return sum;
}
}| 1 | First, we import java.util.concurrent.* to have access to the Callable
interface. |
| 2 | RootSummer is a simple worker class that takes a min and a max
value in its constructor. |
| 3 | Its call() method returns the sum of the square roots of all the int
values greater than or equal to min and less than max. |
Of course, we need another class to create the ExecutorService, start
the futures running, and collect the results.
import java.util.concurrent.*; (1)
import java.util.ArrayList;
public class RootFutures {
private static final int THREADS = 10; (2)
private static final int N = 100000000;
private static final int FUTURES = 1000;
public static void main(String[] args) {
ArrayList<Future<Double>> futures = new ArrayList<>(FUTURES); (3)
ExecutorService executor = Executors.newFixedThreadPool(THREADS); (4)
int work = N/FUTURES; (5)| 1 | The first part of RootFutures is setup. The imports give us the
concurrency tools we need and a list to store our futures in. |
| 2 | We have three constants. THREADS specifies the number of threads to
create. N gives the number we’re going up to. FUTURES is the total number
of futures we create, considerably larger than the number of threads
they share. |
| 3 | Inside the main() method, we create an ArrayList to hold the
futures. Since we know the number of futures ahead of time, an array
would be ideal. Unfortunately, quirks in the way Java handles generics
make it illegal to create an array with a generic type. Instead, we
create an ArrayList with the size we’ll need pre-allocated. |
| 4 | Next, we create an ExecutorService with a thread pool of size THREADS. |
| 5 | Finally, we find the amount of work done by each future by dividing N
by FUTURES. We can use simple division in this case instead of a more
complicated load-balancing approach because 100,000,000 is divisible by 10. |
System.out.println("Creating futures...");
for(int i = 0; i < FUTURES; i++) {
Callable<Double> summer = new RootSummer(1 + i*work, 1 + (i + 1)*work); (1)
Future<Double> future = executor.submit(summer); (2)
futures.add(future);
}| 1 | To create the futures, we first instantiate a RootSummer object with the
appropriate bounds for the work it’s going to compute. |
| 2 | Then, we supply that object to the submit() method on the
ExecutorService, which returns a Future object. We could have saved a
line of code by storing this return value
directly into the list futures. |
System.out.println("Getting results from futures...");
double sum = 0.0;
for(Future<Double> future: futures) { (1)
try {
sum += future.get(); (2)
}
catch(InterruptedException | ExecutionException e) { (3)
e.printStackTrace();
}
}
executor.shutdown(); (4)
System.out.println("The sum of square roots is: " + sum); (5)
}
}| 1 | To collect the values from each future, we iterate
through the list of futures with an enhanced for loop. |
| 2 | We add the return value of each future’s get() method to our running
total sum. |
| 3 | Because get() is a blocking call, we have to catch an InterruptedException
in case we’re interrupted while waiting for the future to respond.
However, we also have to catch an ExecutionException in case an
exception occurs during the execution of the future. This exception
handling mechanism is one of the big advantages of using futures:
Exceptions thrown by the future are propagated back to the thread that
gets the answer from the future. Normal threads simply die if they have
unhandled exceptions. Note that we use the modern exception-catching syntax
to handle two unrelated exceptions with the same catch block. |
| 4 | After all the values have been read and summed, we shut the
ExecutorService down. If we’d wanted, we could have submitted
additional Callable objects to it to run more futures. |
| 5 | Finally, we print out the result. |
19.7. Exercises
Conceptual Problems
-
Example 19.1 gave a mathematical recursive definition for x ⋅ y. Give a similar recursive definition for x + y, assuming that y is a positive integer. The structure is similar to the recursion to determine your current age given in Section 19.2.1.
-
In principle, every problem that can be solved with an iterative solution can be solved with a recursive one (and vice versa). However, the limited size of the call stack can present problems for recursive solutions with very deep recursion. Why? Conversely, are there any recursive solutions that are impossible to turn into iterative ones?
-
Consider the first (non-memoized) recursive version of the Fibonacci method given in Example 19.5. How many times is
fibonacci()called with argument 1 to computefibonacci(n)? Instrument your program and count the number of calls for n = 2, 3, 4, …, 20. -
In the recursive
solve()method in theMazeSolverprogram given in Section 19.5, the current location in the maze array is set to a space character (' ') if no solution is been found. What value was in that location? How would the program behave if the value wasn’t changed back?
Programming Practice
-
Exercise 8.11 from Chapter 8 challenges you to write a method to determine whether a
Stringis a palindrome. Recall that a palindrome (if punctuation and spaces are ignored) can be described as an emptyStringor aStringin which the first and last characters are equal, with all the characters in between forming a palindrome. Write a recursive method with the following signature to test if aStringis a palindrome.public static boolean isPalindrome(String text, int start, int end)In this method, the
startparameter is the index of the first character you’re examining, and theendparameter is the index immediately after the last character you’re examining. Thus, it would initially be called with aString,0, and the length of theString, as follows.boolean result = isPalindrome("A man, a plan, a canal: Panama", 0, 30); -
The efficient implementation of Fibonacci from Example 19.5 eliminates redundant computation through memoization, storing values in an array as they’re found. However, it’s possible to carry along the computations of the previous two Fibonacci numbers without the overhead of storing an array. Consider the following method signature.
public static int fibonacci(int previous, int current, int n)The next recursive call to the
fibonacci()method passes inn - 1and suitably altered versions ofpreviousandcurrent. Whennreaches0, thecurrentparameter holds the value of the Fibonacci number you were originally looking for.The method would be called as follows for any value of
n.int result = fibonacci(0, 1, n);Complete the implementation of this recursive method.
-
Write an implementation of fast exponentiation that works for even and odd n. This implementation is exactly the same as the one given at the end of Example 19.7 except when n is odd. Use the following recursive definition of exponentiation to guide your implementation.
-
Example 19.5 shows two implementations that can be used to find the nth Fibonacci number. With some knowledge of recurrence relations, it’s possible to show that there’s a closed-form equation that gives the nth Fibonacci number Fn where F0 = F1 = 1.
Although this equation is a bit ugly, you can plug numbers into it to discover the value of Fn quickly, provided that you have an efficient way to raise values to the nth power. Use the recursive algorithm for fast exponentiation from Exercise 19.7 to make an implementation that finds the nth Fibonacci number very quickly.
Note that this approach uses real numbers (including the square root of 5) that need to be represented as
doublevalues. There are exact methods that use fast exponentiation of integer matrices to do this computation without doing any floating-point arithmetic, but we won’t go into those details here. -
Example 19.9 shows a way to calculate the size of a linked list recursively. Add a recursive method called
print()to theRecursiveListSizeclass that prints out the values in the linked list recursively, one value per line. -
Expand the previous exercise to add another method called
reversePrint()that prints out the values in the linked list in the opposite order that they appear. It should take only a slight modification of theprint()method you’ve already written. -
Create a recursive
find()method (and a non-recursive proxy method to call it) for theTreeclass given in Program 19.4. Its operation is similar to theadd()method. If the subtree it’s examining is empty (null), it should returnfalse. If the value it’s looking for is at the root of the current subtree, it should returntrue. These are the two base cases. If the value it’s looking for comes earlier in the alphabet than the value at the root of the current subtree, it should look in the left subtree. If the value it’s looking for comes later in the alphabet than the value at the root of the current subtree, it should look in the right subtree. Those are the two recursive cases. -
The height of a binary tree is defined as the longest path from the root to any leaf node. Thus, the height of a tree with only a root node in it is 0. By convention, the height of an empty tree is -1.
Create a recursive
getHeight()method (and a non-recursive proxy method to call it) for theTreeclass given in Program 19.4. The base case is an empty tree (anullpointer), which has a height of -1. For the recursive case of a non-empty tree, its height is one more than the height of the larger of its two subtrees. -
Create a Java interface that describes a tree ADT. Modify the programs in Example 19.10 to implement this interface.
Experiments
-
Write an iterative version of the factorial function and compare its speed to the recursive version given in the text. Use the
System.nanoTime()method before and afterforloops that call the factorial methods 1,000,000 times each for random values. -
Write a program that generates four arrays of random
intvalues with lengths 1,000, 10,000, 100,000, and 1,000,000. Make two additional copies of each array. Then, sort each of three copies of the array with the selection sort algorithm given in Example 6.2, the bubble sort algorithm given in Section 10.1, and the merge sort algorithm given in Example 19.8, respectively. Use theSystem.nanoTime()method to time each of the sorts. Note that both selection sort and bubble sort might take quite a while to sort an array of 1,000,000 elements.Run the program several times and find average values for each algorithm on each array size. Plot those times on a graph. The times needed to run selection sort and bubble sort should increase quadratically, but the time to run merge sort should increase linearithmically. In other words, an array length of n should take time proportional to n2 (multiplied by some constant) for selection sort and bubble sort, but it should take time proportional to n log2 n (multiplied by some constant) for merge sort. For large arrays, the difference in time is significant.
-
Investigate the performance of using recursion to compute Fibonacci numbers. Implement the naive recursive solution, the memoization method, and an iterative solution similar to the memoization method. Use the
System.nanoTime()method to time the computations for large values of n.Warning: It might take a very long time to compute the nth Fibonacci number with the naive recursive solution.
-
Exercise 6.9 from Chapter 6 explains how binary search can be used to search for a value in a sorted array of values. The idea is to play a “high-low” game, first looking at the middle value. If the value is the one you’re looking for, you’re done. If it’s too high, look in the lower half of the array. If it’s too low, look in the upper half of the array. Implement binary search both iteratively and recursively. Populate an array with 100,000
intvalues between 1 and 10,000,000 and sort it. Then, search for 1,000,000 random values generated between 1 and 10,000,000 using iterative binary search and then recursive binary search. Use theSystem.nanoTime()method to time each process. Was the iterative or recursive approach faster? By how much?