Extra Topic: Recursion and Memoization
Note: extra topics are not in CS Academy, but are required
and can appear on any future
homework, writing session, quiz, or exam.
Memoization
Memoization is a general technique to make certain recursive applications more efficient. The Big idea: when a program does a lot of repetitive computation, store results as they are computed, then look up and reuse results when available.
- The problem:
def fib(n):
if (n < 2):
return 1
else:
return fib(n-1) + fib(n-2)
import time
def testFib(maxN=40):
for n in range(maxN+1):
start = time.time()
fibOfN = fib(n)
ms = 1000*(time.time() - start)
print(f'fib({n:2}) = {fibOfN:8}, time = {ms:5.2f}ms')
testFib() # gets really slow!
- A solution:
fibResults = dict()
def fib(n):
if (n in fibResults):
return fibResults[n]
if (n < 2):
result = 1
else:
result = fib(n-1) + fib(n-2)
fibResults[n] = result
return result
import time
def testFib(maxN=40):
for n in range(maxN+1):
start = time.time()
fibOfN = fib(n)
ms = 1000*(time.time() - start)
print(f'fib({n:2}) = {fibOfN:8}, time = {ms:5.2f}ms')
testFib() # ahhh, much better!
- A more elegant solution:
def memoized(f):
# You are not responsible for how this decorator works. You can just use it!
import functools
cachedResults = dict()
@functools.wraps(f)
def wrapper(*args):
if args not in cachedResults:
cachedResults[args] = f(*args)
return cachedResults[args]
return wrapper
@memoized
def fib(n):
if (n < 2):
return 1
else:
return fib(n-1) + fib(n-2)
import time
def testFib(maxN=40):
for n in range(maxN+1):
start = time.time()
fibOfN = fib(n)
ms = 1000*(time.time() - start)
print(f'fib({n:2}) = {fibOfN:8}, time = {ms:5.2f}ms')
testFib() # ahhh, much better!
- Using the builtin @cache
from functools import cache
@cache
def fib(n):
if (n < 2):
return 1
else:
return fib(n-1) + fib(n-2)
import time
def testFib(maxN=40):
for n in range(maxN+1):
start = time.time()
fibOfN = fib(n)
ms = 1000*(time.time() - start)
print(f'fib({n:2}) = {fibOfN:8}, time = {ms:5.2f}ms')
testFib() # still much better!