Java Reference
In-Depth Information
Most modern compilers will convert certain simple recursive method definitions to
iterative ones before translating the code. In such cases there is no loss of efficiency for
using the recursive version in place of an iterative version.
Self-Test Exercise
15. Write a recursive method definition for the following method:
/**
Precondition: n >= 1
Returns the sum of the squares of the numbers 1 through n.
*/
public static int
squares(
int
n)
For example,
squares(3)
returns
14
because 1
2
+ 2
2
+ 3
2
is 14.
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, since 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).
