Java Reference
In-Depth Information
Self-Test Exercises
16. How might you write a nonrecursive version of the program in Display 11.11?
You do not have to write actual code, just think of what approach you might use.
17. The program in Display 11.11 could make thousands of recursive calls if you
have a lot of subdirectories on your hard drive. Why is it unlikely that you will
encounter a stack overfl ow error?
18.
What is the stopping case in Display 11.11 ?
Chapter Summary
•
If a problem can be reduced to smaller instances of the same problem, then a recursive
solution is likely to be easy to find and implement.
•
A recursive algorithm for a method definition normally contains two kinds of cases:
one or more cases that include at least one recursive call and one or more stopping
cases in which the problem is solved without any recursive calls.
•
When writing a recursive method definition, always check to see that the method will
not produce infinite recursion.
•
When you define a recursive method, use the three criteria given in the subsection
“Recursive Design Techniques” to check that the method is correct.
•
When you design a recursive method to solve a task, it is often necessary to solve
a more general problem than the given task. This may be required to allow for the
proper recursive calls, because the smaller problems may not be exactly the same
problem as the given task. For example, in the binary search problem, the task was to
search an entire array, but the recursive solution is an algorithm to search any portion
of the array (either all of it or a part of it).
Answers to Self-Test Exercises
1.
Hip Hip Hurray
2 .
public static void
stars(
int
n)
{
System.out.print('*');
if
(n > 1)
stars(n - 1);
}
The following answer to Self-Test Exercise 3 is also correct, but is more
complicated.
