- Recursion Versus Iteration
- A More Challenging Example: Rabbit Numbers
- Inception: The True Benefit of Recursion
- The Tower of Hanoi
- Other Aspects of Efficient Algorithms
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Inception: The True Benefit of Recursion
So far, I seem to have made a case for never using recursion. Yet there is a class of problems for which recursion is essential. That happens when you have a scenario in which there is a context inside a context inside a context; the resolution of each context depends on first solving the context inside it.
The situation is like Christopher Nolan’s film “Inception,” in which the protagonists go several levels into a subject’s dreams: The subject is dreaming inside a dream, so there’s a dream inside a dream inside a dream, and so on, until they get to the deepest level. To solve the problem at one level, they first have to solve the problems one level deeper; after that, they pop back out.
Eventually, the dreamer wakes up. In similar fashion, the function calls within a recursive solution eventually return, producing a final answer. There’s recursion for you.
When does this happen in computer programming? The most common applications are language translators and compilers. These are complex, fairly difficult-to-write programs. A simpler example is the Tower of Hanoi puzzle.