Java Reference
In-Depth Information
2.5
Recursion
An algorithm is recursive if it calls itself to do part of its work. For this approach
to be successful, the “call to itself” must be on a smaller problem then the one
originally attempted. In general, a recursive algorithm must have two parts: the
base case, which handles a simple input that can be solved without resorting to
a recursive call, and the recursive part which contains one or more recursive calls
to the algorithm where the parameters are in some sense “closer” to the base case
than those of the original call. Here is a recursive Java function to compute the
factorial of n. A trace of
fact
's execution for a small value of n is presented in
Section 4.2.4.
/
**
Recursivelycomputeandreturnn!
*
/
staticlongfact(intn){
//fact(20)isthelargestvaluethatfitsinalong
assert(n>=0)&&(n<=20):"noutofrange";
if(n<=1)return1;//Basecase:returnbasesolution
returnn
*
fact(n-1); //Recursivecallforn>1
}
The first two lines of the function constitute the base cases. If n 1, then one
of the base cases computes a solution for the problem. If n > 1, then
fact
calls
a function that knows how to find the factorial of n 1. Of course, the function
that knows how to compute the factorial of n 1 happens to be
fact
itself. But
we should not think too hard about this while writing the algorithm. The design
for recursive algorithms can always be approached in this way. First write the base
cases. Then think about solving the problem by combining the results of one or
more smaller — but similar — subproblems. If the algorithm you write is correct,
then certainly you can rely on it (recursively) to solve the smaller subproblems.
The secret to success is: Do not worry about how the recursive call solves the
subproblem. Simply accept that it will solve it correctly, and use this result to in
turn correctly solve the original problem. What could be simpler?
Recursion has no counterpart in everyday, physical-world problem solving. The
concept can be difficult to grasp because it requires you to think about problems in
a new way. To use recursion effectively, it is necessary to train yourself to stop
analyzing the recursive process beyond the recursive call. The subproblems will
take care of themselves. You just worry about the base cases and how to recombine
the subproblems.
The recursive version of the factorial function might seem unnecessarily com-
plicated to you because the same effect can be achieved by using a
while
loop.
Here is another example of recursion, based on a famous puzzle called “Towers of
Hanoi.” The natural algorithm to solve this problem has multiple recursive calls. It
cannot be rewritten easily using
while
loops.
