Java Reference
In-Depth Information
The operation of the nonrecursive method factI( ) should be clear. It uses a loop starting
at 1 and progressively multiplies each number by the moving product.
The operation of the recursive factR( ) is a bit more complex. When factR( ) is
called with an argument of 1, the method returns 1; otherwise, it returns the product of
factR(n-1)*n . To evaluate this expression, factR( ) is called with n-1 . This process re-
peats until n equals 1 and the calls to the method begin returning. For example, when the
factorial of 2 is calculated, the first call to factR( ) will cause a second call to be made with
an argument of 1. This call will return 1, which is then multiplied by 2 (the original value
of n ). The answer is then 2. You might find it interesting to insert println( ) statements into
factR( ) that show at what level each call is, and what the intermediate results are.
When a method calls itself, new local variables and parameters are allocated storage on
the stack, and the method code is executed with these new variables from the start. A re-
cursive call does not make a new copy of the method. Only the arguments are new. As each
recursive call returns, the old local variables and parameters are removed from the stack,
and execution resumes at the point of the call inside the method. Recursive methods could
be said to “telescope” out and back.
Recursive versions of many routines may execute a bit more slowly than their iterative
equivalents because of the added overhead of the additional method calls. Too many re-
cursive calls to a method could cause a stack overrun. Because storage for parameters and
local variables is on the stack and each new call creates a new copy of these variables,
it is possible that the stack could be exhausted. If this occurs, the Java run-time system
will cause an exception. However, you probably will not have to worry about this unless
a recursive routine runs wild. The main advantage to recursion is that some types of al-
gorithms can be implemented more clearly and simply recursively than they can be iter-
atively. For example, the Quicksort sorting algorithm is quite difficult to implement in an
iterative way. Also, some problems, especially AI-related ones, seem to lend themselves to
recursive solutions. When writing recursive methods, you must have a conditional state-
ment, such as an if , somewhere to force the method to return without the recursive call be-
Search WWH ::




Custom Search