Java Software Solutions, 8e, Global Edition
Exercise Solutions, Ch. 12
Chapter 12 Exercise Solutions
EX 12.1. Write a recursive definition of a valid Java identifier (see Chapter 1).
A Java–Identifier is a: Letter
or a: Letter followed by a Java–Identifier–Substring
EX 12.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 12.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 12.4. Write a recursive definition of the Fibonacci numbers. The Fibonacci
numbers are 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 12.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)
Java Software Solutions, 8th Edition Exercise Solutions, Ch. 12
EX 12.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;
EX 12.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 Solutions, 8th Edition Exercise Solutions, Ch. 12
EX 12.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
or a 0 in each cell of a two–dimensional array. Because the likelihood of generating a
{1,0,1,0,1,0,1,0,1},
{1,0,1,0,1,0,1,0,1},
{1,0,1,0,1,0,1,0,1},
{1,0,1,1,1,1,1,0,1}};
After the search arrives at position (5,0), it attempts position (6,0). Encountering a 0
0 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 12.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 2 to 3 // called with numDisks = 1
Java Software Solutions, 8th Edition Exercise Solutions, Ch. 12
EX 12.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
7 127
8 255
9 511
10 1023
EX 12.11. How many line segments are used to construct a Koch snowflake of order
N? Produce a chart showing the number of line segments that make up a Koch
snowflake for orders 1 through 9.
Java Software Solutions, 8th Edition Exercise Solutions, Ch. 12