Big Java, 4th Edition

Chapter 13. Recursion

CHAPTER GOALS

• To learn about the technique of recursion

• To understand the relationship between recursion and iteration

• To analyze problems that are much easier to solve by recursion than by iteration

• To learn to "think recursively"

• To be able to use recursive helper methods

• To understand when the use of recursion affects the efficiency of an algorithm

Recursion is a powerful technique for reducing complex computational problems to simpler ones. The term "recursion" refers to the fact that the same computation recurs, or occurs repeatedly, as the problem is solved. Recursion is often the most natural way of thinking about a problem, and there are some computations that are very difficult to perform without recursion. This chapter shows you simple and complex examples of recursion and teaches you how to "think recursively".

Triangle Numbers

We begin this chapter with a very simple example that demonstrates the power of thinking recursively. In this example, we will look at triangle shapes such as this one:

[]
[][]
[][][]

We'd like to compute the area of a triangle of width n, assuming that each [] square has area 1. This value is sometimes called the n^th triangle number. For example, as you can tell from looking at the triangle above, the third triangle number is 6.

You may know that there is a very simple formula to compute these numbers, but you should pretend for now that you don't know about it. The ultimate purpose of this section is not to compute triangle numbers, ...