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.

Contents:

• Introduction: Another Guide To Recursion? And Why Is It So Long?
• Scope, Frame and Stack
  • Understanding how functions work
  • Nested functions are nested frames
  • Functional state and namespaces
  • Heuristics
• Recursion in Light of Frames
  • My first recursive code
  • Understanding recursion as a process
  • Heuristics and Exercises
• Counting In Recursion
  • Steps vs Frames
  • Counting the post-recursive cascade
  • Heuristics and Exercises
• Recursion and Swapped Arguments
  • Doing it Euclid’s way
  • Heuristics and Exercises
• Palindromes and Recursion-as-Evaluation
  • Applying recursion to strings
  • Multiple base cases
  • Heuristics and Exercises
• Summing a List of Lists
  • Recursion…but only when it’s needed
  • Computing values inside each recursive frame
  • Where’s the base case?
  • Using recursion for directory listing
  • Heuristics and Exercises
• Using Recursion to Make More: The Power Set
  • Thinking before coding
  • The right seed in the right frame
  • Heuristics and Exercises
• Expanding a Series: Pascal’s Triangle
  • Returning the nth layer
  • Returning the entire series
  • Heuristics and Exercises
• Multiple Recursive Calls: Fibonacci Sequence, Part 1
  • Introducing multiple recursive calls
  • Measuring efficiency and complexity
  • Heuristics and Exercises
• Memoization: Fibonacci Sequence, Part 2
  • Memoizing by list
  • Memoizing by dictionary
  • Memoizing Fibonacci
  • Heuristics and Exercises
• Recursive Approaches To Searching And Sorting
  • Searching by bisecting the search space
  • Sorting things out: mergeSort()
  • Heuristics and Exercises
• Recursion and Self-Similarity: Koch Curves
  • Turtles all the way down
  • Tracing the recursive calls
  • The Koch snowflake
  • Heuristics and Exercises
• The Sierpinski Triangle
  • Setting up the problem
  • Midpoints of midpoints
  • Determining the order of drawing
  • Stepping through the code
  • Heuristics and Exercises
• Lindenmayer Systems
  • A different way of generating fractals
  • Exercises
• Solving L-System Recursion
  • Recursive version of a Koch curve L-system
  • Implementing absolute distance
  • Recursively finding a target string
• Boss Level: The Tower of Hanoi
  • Put the algorithm in your hands
  • Filling in the binary tree
  • Designing the recursive calls
  • Why does it work?
  • Heuristics and Exercises

Indices and tables

• Index
• Module Index
• Search Page