Memoisation: Caching Recursive Results
Apply @functools.lru_cache and manual memo dicts to Fibonacci and climbing-stairs to eliminate exponential recomputation.
The Problem with Redundant Recursion
Naive recursive Fibonacci computes the same values repeatedly. fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) and fib(2) — so fib(3) is computed twice. This redundancy grows exponentially: fib(40) makes over one billion function calls. Memoisation solves this by storing each result the first time it is computed, so subsequent calls retrieve it in O(1) rather than recomputing it.
# Count calls without memoisation
call_count = [0]
def fib_plain(n):
call_count[0] += 1
if n <= 1: return n
return fib_plain(n-1) + fib_plain(n-2)
fib_plain(20)
print(f'fib(20) without memo: {call_count[0]:,} calls')
# ~21,891 calls for n=20; ~1 billion for n=40Manual Memoisation with a Dict
Add a memo dict as a parameter (or a closure). Before computing, check if the answer is already in memo. If yes, return it immediately. If no, compute it, store in memo, and return. Every unique sub-problem is now computed exactly once, turning O(2^n) into O(n) time and O(n) space for the memo dict plus O(n) stack space.
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
print(fib_memo(10)) # 55
print(fib_memo(50)) # 12586269025
print(fib_memo(100)) # huge number — still fast!All lessons in this course
- Recursion Framework: Base Case, Trust, Build
- Visualising the Call Stack
- Recursive vs Iterative Trade-offs
- Memoisation: Caching Recursive Results