6. Recursion

In This Chapter

Triangular Numbers



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 ...

Get Data Structures & Algorithms in Python now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.