Section 12.7. Object-Oriented Design: Recursion or Iteration?

[Page 586 (continued)]

12.7. Object-Oriented Design: Recursion or Iteration?

As we mentioned at the outset of this chapter, recursive algorithms require more computational overhead than iterative algorithms. We are now in a good position to appreciate why this is so.

A recursive algorithm incurs two kinds of overhead that are not incurred by an iterative algorithm: memory and CPU time. Both of these are direct results of the fact that recursive algorithms do a lot of method calling.

As we saw in our various traces, each time a method is called, a representation of the method call is placed on the method call stack.These representations often take the form of a block of memory locations. Such blocks can be quite large. The block must contain space for the method's local variables, including its parameters. Unless the method is void, the block must also contain space for the method's return value. In addition it must contain a reference to the calling method, so that it will know where to go when it is done. Figure 12.26 shows what the method call block would look like for the search() method.

Figure 12.26. A more detailed picture of the method call stack, showing two method blocks for search() after two levels of recursion.

Method call overhead

Memory overhead

---

[Page 587]

In addition to the memory required, a method call also requires extra CPU time. Each time a method is called, Java must create a method call block, copy the method call arguments to the parameters in the block, create initial values for any local variables used by the method, and fill in the return address of the calling method. All of this takes time, and in the case of a recursive method, these steps are repeated at each level of the recursion.

CPU overhead

Exploring the Mandelbrot Set

The Mandelbrot set is one of the most fascinating fractals. It is named after its discovered, IBM mathematician Benoit Mandelbrot. The Mandelbrot set itself is the black, heart-shaped image shown in Figure 12.27. What makes the Mandelbrot set so interesting is that with the help of a Java applet you can explore the set as if you were taking a trip through outer space. The most interesting regions to explore are those just along the boundary of the set. For example, note that the boundary contains numerous circular shapes, each of which is itself studded with circular shapes. This is an example of the scaled self-similarity that we found to be so prevalent in recursive structures. By continually expanding the regions around the boundary, you'll find an infinite recursion of fascinating images and shapes. In some regions of the set you'll even find miniature replications of the set itself.

Figure 12.27. The Mandelbrot set.

The Mandelbrot set is generated by an iterated function system. The mathematics underlying this fascinating object is quite accessible, and there are a number of online tutorials that explain how the set is generated and how the pictures are produced. Many of the Mandelbrot and fractal Web sites contain excellent Java applets that let you explore the Mandelbrot set as well as related sets. An excellent place to start your exploration would be David Joyce's award-winning Web site,

http://aleph0.clarku.edu/~djoyce/julia/

which contains references to a number of other good sites. For a tutorial on how the various Mandelbrot set-generating Java programs work, see

http://storm.shodor.org/mteach/

---

[Page 588]

Compare these memory and CPU requirements with what normally transpires for an iterative algorithman algorithm involving a loop. The loop structure usually occurs entirely within a method, so it doesn't incur either the memory or CPU overhead involved in recursion. Therefore, iterative algorithms are generally more efficient than recursive algorithms. Here, then, is a useful guideline: when runtime performance and efficiency are of prime importance, use iteration instead of recursion.

Effective Design: Iteration or Recursion?

Use an iterative algorithm instead of a recursive algorithm whenever efficiency and memory usage are important design factors.

On the other hand, for many problems recursive algorithms are much easier to design than the corresponding iterative algorithms. We tried to illustrate this point in our development of the Sierpinski gasket algorithm, but there are many other examples we could have used. Given that programmer and designer time is the most expensive resource involved in software development, a recursive solution may be easier to develop and maintain than a corresponding iterative solution. And given the great cost of software development, a less efficient solution that is easier to develop, easier to understand, and easier to maintain may be preferable to a highly efficient algorithm that is difficult to understand. For some problems, then, such as the Sierpinski gasket, a recursive algorithm may provide the best solution.

Efficiency of development

Effective Design: Keep It Simple

When all other factors are equal, choose the algorithm (recursive or iterative) that is easiest to understand, develop, and maintain.

One final point worth making is that some optimizing compilers are able to convert recursive methods into iterative methods when they compile the program. The algorithms for doing this are well known. They are often subjects for study in a data structures course, so we won't go into them here. The resulting runtime programs will be just as efficient, in CPU time and memory, as if you had written iterative methods. The point is that if you have such a compiler, you really get the best of both worlds. You get the advantage of using recursion as a problem-solving and software-development approach, and the compiler takes care of producing an efficient object program.

Optimizing compiler