Memoization done right in Python
Take notes! You know how to create the Fibonacci sequence in Python? Well keep reading, because since Python 3.8 there is a cleaner way of doing this. But is it better? We’ll discuss the pros and cons in this article along with the alternative approaches.
First, let’s start with recursion and iteration, and finally we’ll discuss memoization and how to do it different in Python ≥ 3.8.
Fibonacci
Just as a short reminder: a Fibonacci sequence is basically a sequence of numbers where each number is equal to the sum of the preceding two numbers, starting with 0. So: 0, 1, 1, 2, 3, 5, 8, 13. Where the second one is the some of the 0 and 1 before, the 2 is the sum of the preceding two ones, 5 is the sum of the preceding 2 and 3 etc.
Recursion
We could easily generate the Fibonacci sequence using recursion, where n is the nth number in the sequence:
def fib_recursive(n):
"""
n is the number nth number
you would like to return in the sequence
"""
if n <= 0: # always return 0 if the nth number is less or equal to 0
return 0
if n == 1: # first number is always 1
return 1
# Add the previous two numbers which we generate
# by running the same function with the n-1 and n-2
# as input, which makes this recursive.
return fib_recursive(n-1) + fib_recursive(n-2)
# 6th Fibonacci (including 0 as first number)
fib_recursive(6) # should return 8You can see this as a top-bottom approach. We keep looping backwards till we hit the 1st and 2nd Fibonacci number and sum up all the return values.
Pros:
- You can break up a problem into smaller, simpler code.
Cons:
- At some point you might hit the “maximum recursion depth exceeded” error, depending on the problem.
Iteration
Now with recursion you can hit a maximum recursion depth exceeded error. The maximal number of nested calls (including the first one) is called the recursion depth, which is a 1000 by default and behaves as a guard against a stack overflow. You could increase it, which is not recommended. Instead you could have a look at iteration.
def fib_iter(n):
"""
n is the number nth number
you would like to return in the sequence
"""
a, b = 0, 1 # We always start with a 0 and a 1
for _ in range(0,n):
a, b = b, a + b
return a
# 6th Fibonacci (including 0 as first number)
fib_iter(6) # should return 8If you test above approach, you will recognize that it’s able to provide a much larger Fibonacci number than the recursive method as able to. It will simply start at 0 and calculate the number on the fly.
If a = 0 and b = 1, the second iteration a = b (so a becomes 1) and b = a+b (so b becomes 0+1 = 1). Each iteration it will repeat this process.
Pros:
- Simple and straightforward
- Less memory consuming as variables are overwritten.
Cons:
- You’d have to recalculate from the bottom, every single run. In case of a Fibonacci sequence that’s not much of an issue, but there might be problems where you’d want to speed things up by memorizing the results of calculations that have already been done.
Memoization (dynamic programming)
The problem with recursion is that each number will be calculated from the ground up and iteration has to start over on each function call: so, if you would like to calculate 10 Fibonacci numbers during the lifetime of your script, you would repeat the whole process again and again. But there is a solution, memoization (not to confuse with memorization).
def fib_memo(n, memo={0:0, 1:1}):
"""
n is the number nth number
you would like to return in the sequence
"""
if not n in memo:
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]
# 6th Fibonacci (including 0 as first number)
fib_memo(6) # should return 8What it does, is keeping track of the numbers already calculated and store them in a dictionary, so they won’t be calculated twice. If you just want to calculate one number, you could argue whether this would be faster than iteration, but if you would like to calculate multiple numbers during the lifetime of your script, it definitely will.
Be aware! This works totally fine in Python. Some people feel the need to pass the “mem” argument on each function call but in Python arguments are evaluated when the function definition is encountered. Good to remind that! This means that each time the fib_memo function is called without explicitly providing a value for the memo argument, it will use the same dictionary object that was created when the function was defined.
Pros:
- You prevent recalculating problems which have already been done, by saving the result in a dictionary.
Cons:
- You might still run against the “maximum recursion depth exceeded” limit, because it is using again, recursion. But, if we take the Fibonacci sequence as an example: you could run the function let’s say 10 times or so, and each time increase the nth Fibonacci number to be calculated. Because of memoization it won’t recalculate earlier found Fibonacci numbers, which results in less recursion. Example:
fib_number = 100
fib_memo(fib_number)
fib_memo(fib_number * 10)
fib_memo(fib_number * 20)
fib_memo(fib_number * 30)
fib_memo(fib_number * 40)
...Memoization using @lru_cache
Instead of implementing your own version of memoization, you could use the @lru_cache or the @cache decorator (which basically returns the same as @lru_cache(maxsize=None)).
@lru_cache uses a dictionary behind the scenes. It caches the function’s result under a key that consists of the call to the function, including the supplied arguments. This prevents, among others, to supply your own variable which stores the results of your function. In case of Fibonacci numbers this won’t change much, but there might be scenarios where you want to use this decorator to keep your code clean and simple. In case of interviews, it might even show that you know Python specifics, which might give you an advantage.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
"""
n is the number nth number
you would like to return in the sequence
"""
if n <= 0:
return 0
if n == 1:
return 1
return fib_memo(n-1) + fib_memo(n-2)
# 6th Fibonacci (including 0 as first number)
fib_memo(6) # should return 8Pros:
- You prevent recalculating problems which have already been done, by saving the result in a dictionary.
- Might keep your code cleaner and simpler in contrast to the memoization approach which doesn’t use this decorator, in circumstances.
- Might give you an advantage of using this decorator during job interviews.
Cons:
- As shown with the memoization example, which doesn’t use this decorator, you might still run against the “maximum recursion depth exceeded” limit, but you could use the same workaround to generate larger results by taking advantage of the memoization.
