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 nth 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, ...
Get Big Java, 4th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
