Java Reference
In-Depth Information
If I had calculated the factorial of ten (10!), I would have had ten instances of the
calculate
method
on the stack. To avoid this problem, I can rewrite the method to use a loop instead, thus:
Listing 14-2. Converting Recursion to a Loop
package com.bryantcs.examples.factorial;
public class Factorial {
int calculate(int number) {
if (number < 0) {
throw new IllegalArgumentException("integer must be 0+");
}
if( number == 0 || number == 1)
return 1;
else {
int total = 1;
for (int i = 1; i < number + 1; i++) {
total *= i;
}
return total;
}
}
public static void main(String[] args) {
Factorial factorial = new Factorial();
System.out.println(factorial.calculate(4));
}
}
Since it contains no calls to itself, the calculate method appears on the stack only once. Therefore,
the lesson here is that any time you can easily replace recursion with a loop, you should do so.
When to Use Recursion
If you should replace recursion with loops whenever you can easily do so, when should you use
recursion? The simple (but not helpful) answer is: when it's useful to do so. But when is that? Essentially,
you should use recursion when you can't know (or can't be sure of) the number of times you need to
process something. Processing an XML file is a good illustration of this problem. When you write a
program to process an XML file, you can't be sure how many nodes will be in the given XML file. It is
possible to solve these kinds of problems with while loops, but in this case, recursion is easier both to
code and to understand.
In addition to parsing, other problems are simply easier to code with recursion. If you can
significantly reduce the size of your code or gain an algorithm that is easier to understand, you should
consider recursion, even in cases where the problem can be solved with loops. What sorts of things are
solved with recursive algorithms? Let's look at some common problems that utilize recursion (and I'll
code some of the more interesting ones later in the chapter):
