Java Reference
In-Depth Information
P
ROGRAMMING
T
IPS
•
An iterative method contains a loop. A recursive method calls itself. Although some recursive methods con-
tain a loop
and
call themselves, if you have written a
while
statement within a recursive method, be sure that
you did not mean to write an
if
statement.
•
A recursive method that does not check for a base case, or that misses the base case, will not terminate nor-
mally. This situation is known as infinite recursion.
•
Too many recursive calls can cause the error message “stack overflow.” This means that the stack of activa-
tion records has become full. In essence, the method uses too much memory. Infinite recursion or large-size
problems are the likely causes of this error.
•
Do not use a recursive solution that repeatedly solves the same problem in its recursive calls.
•
If a recursive method does not work, answer the following questions. Any “no” answers should guide you to
the error.
•
Does the method have at least one parameter or input value?
•
Does the method contain a statement that tests a parameter or input value, leading to different cases?
•
Did you consider all possible cases?
•
Does at least one of these cases cause at least one recursive call?
•
Do these recursive calls involve smaller arguments, smaller tasks, or tasks that get closer to the solution?
•
If these recursive calls produce or return correct results, will the method produce or return a correct result?
•
Is at least one of the cases a base case that has no recursive call?
•
Are there enough base cases?
•
Does each base case produce a result that is correct for that case?
•
If the method returns a value, does each of the cases return a value?
E
XERCISES
1.
Consider the method
displayRowOfCharacters
that displays any given character the specified number of times
on one line. For example, the call
displayRowOfCharacters('*', 5);
produces the line
*****
Implement this method in Java by using recursion.
2.
Describe a recursive algorithm that draws concentric circles, given the diameter of the outermost circle. The diam-
eter of each inner circle should be three-fourths the diameter of the circle that encloses it. The diameter of the
innermost circle should exceed 1 inch.
3.
Write a method that asks the user for integer input that is between 1 and 10, inclusive. If the input is out of range,
the method should recursively ask the user to enter a new input value.
4.
The factorial of a positive integer
n
—which we denote as
n
!—is the product of
n
and the factorial of
n
-
1. The
factorial of 0 is 1. Write two different recursive methods that each return the factorial of
n
.
5.
Write a recursive method that writes a given array backward. Consider the last element of the array first.
6.
Repeat Exercise 5, but instead consider the first element of the array first.
7.
Repeat Exercises 5 and 6, but write a string backward instead of an array.
