Python Recursion in Depth
Recursion is a function calling itself on smaller pieces of a problem. Nested data can sit far deeper than a simple countdown.
Recurse into nested data
The function calls itself on each inner list. Plain values go straight into the result.
def flatten(items):
result = []
for item in items:
if isinstance(item, list):
result.extend(flatten(item))
else:
result.append(item)
return result
print(flatten([1, [2, [3, 4]], 5]))Memoise by hand
A dict stores each finished result. A later call with the same input reads the dict.
memo = {}
def fib_hand(n):
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fib_hand(n - 1) + fib_hand(n - 2)
return memo[n]
print(fib_hand(10))Memoise with lru_cache
The decorators section introduced lru_cache. It gives the same saving with no dict code.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_fast(n):
if n < 2:
return n
return fib_fast(n - 1) + fib_fast(n - 2)
print(fib_fast(10))Flatten with an explicit stack
A list acts as your own stack here. Pushing inner items in reverse keeps the order right.
def flatten_iter(items):
stack = list(reversed(items))
result = []
while stack:
item = stack.pop()
if isinstance(item, list):
stack.extend(reversed(item))
else:
result.append(item)
return result
print(flatten_iter([1, [2, [3, 4]], 5]))Example
def flatten(items):
result = []
for item in items:
if isinstance(item, list):
result.extend(flatten(item))
else:
result.append(item)
return result
def flatten_iter(items):
stack = list(reversed(items))
result = []
while stack:
item = stack.pop()
if isinstance(item, list):
stack.extend(reversed(item))
else:
result.append(item)
return result
data = [1, [2, 3], [4, [5, 6]], 7]
print(flatten(data))
print(flatten_iter(data))
print("Same result:", flatten(data) == flatten_iter(data))Key points
- Memoise: save a result the first time, then reuse it instead of working it out again
- Use lru_cache to memoise a function with one decorator line
- Use an explicit stack, a list you push and pop yourself, to replace recursion
- Recursion suits data whose depth is not known in advance
- Python has no tail-call optimisation
In this example, flatten walks the nested list one item at a time. A plain value goes straight into the result list. A list item sends flatten into that list first. Its flattened values join the result in order. Next, flatten_iter solves the same problem with a loop. It keeps pending items on an explicit stack list. Each pop takes the next item to handle. A list item is pushed back in reversed order. A plain value joins the result. The data list nests three levels deep. Both functions print the same flat list. The last line proves the two versions agree. The stack version has no recursion limit worry.
Note
A call in the tail position still uses a new stack frame, so deep recursion hits the recursion limit.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
Why can very deep recursion fail in Python, even when the code is correct?