Data Structures and Algorithms in Java, 6th Edition

Chapter 5

Recursion

Contents

5.1 Illustrative Examples

5.1.1 The Factorial Function

5.1.2 Drawing an English Ruler

5.1.3 Binary Search

5.1.4 File Systems

5.2 Analyzing Recursive Algorithms

5.3 Further Examples of Recursion

5.3.1 Linear Recursion

5.3.2 Binary Recursion

5.3.3 Multiple Recursion

5.4 Designing Recursive Algorithms

5.5 Recursion Run Amok

5.5.1 Maximum Recursive Depth in Java

5.6 Eliminating Tail Recursion

5.7 Exercises

One way to describe repetition within a computer program is the use of loops, such as Java's while-loop and for-loop constructs described in Section 1.5.2. An entirely different way to achieve repetition is through a process known as recursion.

Recursion is a technique by which a method makes one or more calls to itself during execution, or by which a data structure relies upon smaller instances of the very same type of structure in its representation. There are many examples of recursion in art and nature. For example, fractal patterns are naturally recursive. A physical example of recursion used in art is in the Russian Matryoshka dolls. Each doll is either made of solid wood, or is hollow and contains another Matryoshka doll inside it.

In computing, recursion provides an elegant and powerful alternative for performing repetitive tasks. In fact, a few programming languages (e.g., Scheme, Smalltalk) do not explicitly support looping constructs and instead ...