Recursion - Java Concepts - page 805

The call pattern of a recursive method looks complicated, and the key to the
successful design of a recursive method is not to think about it. Instead, look at the
getArea method one more time and notice how utterly reasonable it is. If the width
is 1, then, of course, the area is 1. The next part is just as reasonable. Compute the
area of the smaller triangle and don't think about why that works. Then the area of the
larger triangle is clearly the sum of the smaller area and the width.

589
590

There are two key requirements to make sure that the recursion is successful:

ȗ Every recursive call must simplify the computation in some way.

ȗ There must be special cases to handle the simplest computations directly.

The getArea method calls itself again with smaller and smaller width values.
Eventually the width must reach 1, and there is a special case for computing the area
of a triangle with width 1. Thus, the getArea method always succeeds.

For a recursion to terminate, there must be special cases for the simplest values.

Actually, you have to be careful. What happens when you call the area of a triangle
with width ɨ1? It computes the area of a triangle with width ɨ2, which computes the
area of a triangle with width ɨ3, and so on. To avoid this, the getArea method
should return 0 if the width is ʎ 0.

Recursion is not really necessary to compute the triangle numbers. The area of a
triangle equals the sum

1 + 2 + 3 + È + width

Of course, we can program a simple loop:

double area = 0;
for (int i = 1; i <= width; i++)
area = area + i;

Many simple recursions can be computed as loops. However, loop equivalents for
more complex recursionsȌsuch as the one in our next exampleȌcan be complex.

Actually, in this case, you don't even need a loop to compute the answer. The sum of
the first n integers can be computed as