ABSTRACT
Have you ever noticed, while laying on your back under a tree, that each branchof the tree resembles the tree itself? If you could take any branch, from the smallest to the largest, and place it upright in the ground, it could probably be mistaken for a smaller tree. This phenomenon, called self-similarity , is widespread in nature. There are also computational problems that, in a more abstract way, exhibit self-similarity. In this chapter, we will discuss a computational technique, called recursion, that we can use to elegantly solve problems that exhibit this property. As the second quotation above suggests, although recursion may seem somewhat foreign at first, it really is quite natural and just takes some practice to master.
