Thinking Recursively in Python “Of all ideas I have introduced to children, recursion stands out as the one idea that is particularly able to evoke an excited response.”
– Seymour Papert, Mindstorms Problems (in life and also in computer science) can often seem big and scary. If we keep chipping away at them, more often than not we can break them down into smaller chunks trivial enough to solve.
Dear Pythonic Santa Claus
Santa Claus has a list of houses he loops through
- He goes to a house, drops off the presents, eats the cookies and milk, and moves on to the next house on the list
- This is the typical structure of a recursive algorithm
- If the current problem represents a simple case, solve it. If not, divide it into subproblems and apply the same strategy to them
Recursive Functions in Python
A recursive function is a function defined in terms of itself via self-referential expressions
- All recursive functions share a common structure made up of two parts: base case and recursive case
- Base case: n! = n x (n−1) (base case: 1! = 1) / n (n-1) = 1
- Recursive case (receiving n: n + 1) = n * n-1
- Behind the scenes, each recursive call adds a stack frame to the call stack until we reach the base case
Pesky Details
Python doesn’t have support for tail-call elimination
- You can cause a stack overflow if you end up using more stack frames than the default call stack depth
- Also, Python’s mutable data structures don’t support structural sharing, so treating them like immutable data structures is going to negatively affect your space and GC (garbage collection) efficiency because you are going to end up unnecessarily copying a lot of mutable objects
- Use this pattern to decompose lists and recurse over them
Maintaining State
Each recursive call has its own execution context, so to maintain state during recursion you have to either: thread the state through each recursive call so that the current state is part of the current call’s execution context
- Keep the state in global scope
- Global mutable state current_number = 1 accumulated_sum = 0 def sum_recursive(current_number, accumulated_sum): # Base case: return the final state
- Recursive case: thread through the recursive call and pass the initial state to the next recursive call
Fin I was once asked to explain recursion in an interview. I took a sheet of paper and wrote Please turn over on both sides. The interviewer didn’t get the joke.
What’s your #1 takeaway or favorite thing you learned? How are you going to put your newfound skills to use? Leave a comment below and let us know.
Recursive Data Structures in Python
A data structure is recursive if it can be defined in terms of a smaller version of itself
- List is an example of a recursive data structure
- Starting with an empty list, you can generate any list by recursively applying the attach_head function
- Recursion can also be seen as self-referential function composition
Naive Recursion is Naive
Fibonacci numbers were originally defined in the thirteenth century to model the growth of rabbit populations.
- The number of rabbits born in a given year is equal to the number of pairs of rabbits in the previous years, starting from one pair in the first year
- Base case: Fn = Fn-1 + Fn-2, base case: F0 = 0 and F1 = 1
- Recursive case: return fibonacci_recursive(n-1) + ffn=Fn-2
- Cache results in lru_cache
