Data Structures and the Java Collections Framework, Third Edition

CHAPTER 5

Recursion

One of the skills that distinguish a novice programmer from an experienced one is an understanding of recursion. The goal of this chapter is to give you a feel for situations in which a recursive method is appropriate. Along the way you may start to see the power and elegance of recursion, as well as its potential for misuse. Recursion plays a minor role in the Java Collections Framework: two of the sort methods are recursive, and there are several recursive methods in the TreeMap class. But the value of recursion extends far beyond these methods. For example, one of the applications of the stack class in Chapter 8 is the translation of recursive methods into machine code. The sooner you are exposed to recursion, the more likely you will be able to spot situations where it is appropriate—and to use it.

CHAPTER OBJECTIVES

1. Recognize the characteristics of those problems for which recursive solutions may be appropriate.
2. Compare recursive and iterative methods with respect to time, space, and ease of development.
3. Trace the execution of a recursive method with the help of execution frames.
4. Understand the backtracking design pattern.

5.1 Introduction

Roughly, a method is recursive if it contains a call to itself.¹ From this description, you may initially fear that the execution of a recursive method will lead to an infinite sequence of recursive calls. But under normal circumstances, this calamity does not occur, and the sequence of calls eventually stops. To ...