Java Software Structures, 4th Edition Exercise Solutions, Ch. 8
Chapter 8 Exercise Solutions
EX 8.1 Write a recursive definition of a valid Java identifier.
A Java-Identifier is a: Letter
or a: Digit followed by a Java-Identifier-Substring
EX 8.2 Write a recursive definition of xy (x raised to the power y), where x and y are
integers and y > 0.
x1 = x
EX 8.3 Write a recursive definition of i * j (integer multiplication), where i > 0. Define
the multiplication process in terms of integer addition. For example, 4 * 7 is
equal to 7 added to itself 4 times.
1 * j = j
EX 8.4 Write a recursive definition of the Fibonacci numbers, a sequence of integers,
each of which is the sum of the previous two numbers. The first two numbers
in the sequence are 0 and 1. Explain why you would not normally use recursion
to solve this problem.
Fib(0) = 0
EX 8.5 Modify the method that calculates the sum of the integers between 1 and N
shown in this chapter. Have the new version match the following recursive
definition: The sum of 1 to N is the sum of 1 to (N/2) plus the sum of (N/2 + 1)
to N. Trace your solution using an N of 7.
// Computes the sum of the numbers between n1 and n2 (inc)
public int sum (int n1, int n2)
Java Software Structures, 4th Edition Exercise Solutions, Ch. 8
}
EX 8.6 Write a recursive method that returns the value of N! (N factorial) using the
definition given in this chapter. Explain why you would not normally use
recursion to solve this problem.
public int factorial (int num)
{
int result;
if (num == 1)
EX 8.7 Write a recursive method to reverse a string. Explain why you would not
normally use recursion to solve this problem.
public String reverse (String text)
{
String result = text;
Java Software Structures, 4th Edition Exercise Solutions, Ch. 8
EX 8.8 Design or generate a new maze for the MazeSearch program in this chapter,
and rerun the program. Explain the processing in terms of your new maze,
giving examples of a path that was tried but failed, a path that was never tried,
and the ultimate solution.
A new maze could be generated with nested for loops which randomly place either a 1
A maze with a solution could be hard-coded with the following statement:
private int [][] grid = {{1,0,1,0,1,1,1,1,1},
{1,0,1,0,1,0,1,0,1},
{1,1,1,0,1,0,1,0,1},
{0,0,1,0,1,0,1,0,1},
{1,0,1,0,1,0,1,0,1},
After the search arrives at position (5,0), it attempts position (6,0). Encountering a 0
causes this path to fail. It then attempts position (5,1) which succeeds. Subsequently,
7 0 1 0 1 1 7 7 7
7 0 1 0 1 0 7 0 7
7 0 1 0 1 0 7 0 7
7 0 1 0 1 0 7 0 7
1 0 7 0 1 0 7 0 7
1 0 7 0 1 0 7 0 7
1 0 7 0 1 0 7 0 7
EX 8.9 Annotate the lines of output of the SolveTowers program in this chapter to
show the recursive steps.
Move one disk from 1 to 2 // called with numDisks = 1
Move one disk from 1 to 3 // called with numDisks = 2
Move one disk from 3 to 2 // called with numDisks = 2
Move one disk from 1 to 2 // called with numDisks = 1
Move one disk from 1 to 3 // called with numDisks = 4
Move one disk from 2 to 3 // called with numDisks = 1
Move one disk from 2 to 1 // called with numDisks = 2
EX 8.10 Produce a chart showing the number of moves required to solve the Towers of
Hanoi puzzle using the following number of disks: 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20,
and 25.
Disks Moves
2 3
3 7
EX 8.11 Determine and explain the order of your solution to Exercise 8.4.
You would not normally use recursion to solve this problem because the iterative
solution is straightforward and the recursive version is inefficient. Calculating a
Fibonacci number less than Fib(j-1) would be calculated at least twice in order to
Fib(0) = 0 1 call
Fib(1) = 1 1 call
Fib(2) = Fib(1) + Fib(0) 3 calls
Fib(3) = Fib(2) + Fib(1) = Fib(1) + Fib(0) + 1 5 calls
EX 8.12 Determine and explain the order of your solution to Exercise 8.5.
Using our trace in the solution to Exercise 8.5 as an example, we can see that each
EX 8.13 Determine and explain the order of your solution to Exercise 8.6.
You would not normally use recursion to solve this problem because it can be done
EX 8.14 Determine the order of the recursive maze solution presented in this chapter.
The time complexity of the maze solution is deterimined by looking at the number of
potential moves or potential paths through the maze. Given that from any given
