Data Structures and Algorithms in Java, 2nd Edition

6. Recursion

In This Chapter

• Triangular Numbers

• Factorials

• Anagrams

• A Recursive Binary Search

• The Towers of Hanoi

• Mergesort

• Eliminating Recursion

• Some Interesting Recursive Applications

Recursion is a programming technique in which a method (function) calls itself. This may sound like a strange thing to do, or even a catastrophic mistake. Recursion is, however, one of the most interesting, and one of the most surprisingly effective, techniques in programming. Like pulling yourself up by your bootstraps (you do have bootstraps, don’t you?), recursion seems incredible when you first encounter it. However, it not only works, it also provides a unique conceptual framework for solving many problems.

In this chapter we’ll examine ...