# Understanding Recursion Using Python¶

**A shamelessly verbose guide to the wonders of recursion**

## Getting Started¶

For a lot of people, learning recursion for the first time pretty much sucks. It doesn’t have to be that way.

This guide is intended to help beginning (and perhaps even intermediate) programmers learn to think recursively. It’s not math-heavy, so there are no proofs, and very little discussion of time/space complexity. But I do take a text-heavy approach, because I think patient explanation is a key ingredient in helping people understand this crucial technique. Although the code is presented in Python, recursion is a fairly universal concept, so the material should be accessible to non-Python developers.

Sometimes I’ll present the code immediately and then unpack it. Other times, we’ll work towards the final recursive solution, starting only from first principles. At the end of each section I deduce a few heuristics, and include an exercise or two that will apply the material and push comprehension a bit further.

I hope the end result is a critical framework developers can use to identify, analyze and solve problems that demand (or simply favor) recursive solutions.

- Introduction: Another Guide To Recursion? And Why Is It So Long?
- Scope, Frame and Stack
- Recursion in Light of Frames
- Counting In Recursion
- Recursion and Swapped Arguments
- Palindromes and Recursion-as-Evaluation
- Summing a List of Lists
- Using Recursion to Make More: The Power Set
- Expanding a Series: Pascal’s Triangle
- Multiple Recursive Calls: Fibonacci Sequence, Part 1
- Memoization: Fibonacci Sequence, Part 2
- Recursive Approaches To Searching And Sorting
- Recursion and Self-Similarity: Koch Curves
- The Sierpinski Triangle
- Lindenmayer Systems
- Solving L-System Recursion
- Boss Level: The Tower of Hanoi