Data Structures and Algorithms in Python

Chapter 4

Recursion

Contents

4.1 Illustrative Examples

4.1.1 The Factorial Function

4.1.2 Drawing an English Ruler

4.1.3 Binary Search

4.1.4 File Systems

4.2 Analyzing Recursive Algorithms

4.3 Recursion Run Amok

4.3.1 Maximum Recursive Depth in Python

4.4 Further Examples of Recursion

4.4.1 Linear Recursion

4.4.2 Binary Recursion

4.4.3 Multiple Recursion

4.5 Designing Recursive Algorithms

4.6 Eliminating Tail Recursion

4.7 Exercises

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

Recursion is a technique by which a function 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 ...