11.1 The Basics of Recursion
TIARA
—TIARA is a recursive acronym.
The TTP Project
—DILBERT
It often turns out that a natural way to design an algorithm involves using the same algorithm on one or more subcases. For example, the following is an outline of an algorithm for searching for a name in a phone book: Open the phone book to the middle of the book. If the name is on that page, you are done. If the name is alphabetically before that page, search the first half of the book. If the name is alphabetically after that page, search the second half of the book. Searching half of the phone book is a smaller version of the original task of searching the entire phone book.
Whenever an algorithm has one subtask that is a smaller version of the entire ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access