Recursion & Memoization in Python
Python · Intermediate
Definition
Recursive functions call themselves; functools.lru_cache stores results to avoid repeat work.
Turns exponential recursion into fast DP.
Diagram
Flowchart
Example: Memoized Fibonacci
from functools import lru_cache
@lru_cache(None)
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
print(fib(50))Output: 12586269025
Complexity
Memoized fib O(n)
Key points
- Default recursion limit ~1000
- sys.setrecursionlimit raises it
Interview questions
Why is plain fib slow?
It recomputes the same subproblems, giving O(2ⁿ) calls.