Data Structures & Algorithms in Python

6. Recursion

In This Chapter

• Triangular Numbers

• Factorials

• Anagrams

• A Recursive Binary Search

• The Tower of Hanoi

• Sorting with mergesort

• Eliminating Recursion

• Some Interesting Recursive Applications

Recursion is a programming technique in which a function calls itself. This behavior may sound strange, or even catastrophic. Recursion is, however, one of the most interesting, and one of the most surprisingly effective, techniques in programming. It’s been said, ”The definition of insanity is doing the same thing over and over again, but expecting different results,” so how could a function calling itself ever get a better result? It not only works but also provides a unique conceptual framework for solving many problems.

The concept ...