Section 12.6. Object-Oriented Design: Tail Recursion

[Page 584 (continued)]

12.6. Object-Oriented Design: Tail Recursion

Although the drawBoxes() method is relatively simple to convert into an iterative version (see Self-Study Exercise 12.18), the same cannot be said for the drawGasket() method. It is clearly a case where the recursive approach makes the problem easier to solve.

Tail recursion

One difference between drawBoxes() and drawGasket() is that drawBoxes() is an example of a tail-recursive method. A method is tail recursive if all of its recursive calls occur as the last action performed in the method. You have to be a bit careful about this definition. The recursive call in a tail-recursive method has to be the last executed statement. It needn't be the last statement appearing in the method's definition.

---

[Page 585]

For example, the following method will print "Hello" N times. This method is tail recursive even though its last statement is not a recursive call:

public void printHello(int N) {  if (N > 1) {    System.out.println("Hello");    printHello(N - 1);            // The last executed statement  } else    System.out.println("Hello"); } // printHello() 

This method is tail recursive because the last statement that will be executed, in its recursive cases, is the recursive call.

A tail-recursive method is relatively easy to convert into an iterative method. The basic idea is to make the recursion parameter into a loop variable, taking care to make sure the bounds are equivalent. Thus, the following iterative method will print "Hello" N times:

public void printHelloIterative(int N) {     for (int k = N; k > 0; k--)         System.out.println("Hello"); } 

In this case, we use the parameter N to set the initial value of the loop variable, k, and we decrement k on each iteration. This is equivalent to what happens when we decrement the recursion parameter in the recursive call.

Effective Design: Tail Recursion

Tail-recursive algorithms are relatively simple to convert into iterative algorithms that do the same thing.

As you can see, recursive methods that are not tail recursive are much more complex. Just compare the drawGasket() and drawBoxes() methods. Yet it is precisely for these nontail-recursive algorithms that recursion turns out to be most useful. As you might expect, if you can't give a simple tail-recursive solution to a problem, the problem probably doesn't have a simple iterative solution either. Thus, the problems where we most need recursion are those where we can't give a simple tail-recursive or an iterative solution. And there are a lot of such problems, especially when you get into nonlinear data structures such as trees and graphs.

To gain some appreciation for this complexity, consider how difficult it would be to draw the Sierpinski gasket using an iterative approach. We could start by developing an outer for loop to account for the different levels in the pattern:

for (int k = lev; k > 0; k--) {  drawGasket(g, lev - 1, p1X, p1Y, q1X, q1Y, q2X, q2Y);  drawGasket(g, lev - 1, p2X, p2Y, q1X, q1Y, q3X, q3Y);  drawGasket(g, lev - 1, p3X, p3Y, q2X, q2Y, q3X, q3Y); } 

---

[Page 586]

But now each of the method calls within the body of this loop would have to be replaced by very complex loops. That would be a daunting task. So the lesson to be drawn from this observation is that recursion is most useful as a problem-solving technique for problems that don't yield to a simple iterative solution.

Effective Design: Recursion or Iteration?

If you have difficulty designing an iterative solution to a problem, try developing a recursive solution.

Self-Study Exercises

Exercise 12.19	Trace the drawGasket() method for levels two and three. Pick your own values for the three vertices.
Exercise 12.20	Is the printReverse() method, discussed earlier, tail recursive? Explain.
Exercise 12.21	Is the countChar() method, discussed earlier, tail recursive? Explain.