Python programs / Dynamic programming / Fibonacci with memoization

Python Program for Fibonacci Using Memoization

Intermediate Dynamic programming Time O(n) Space O(n)

Works out Fibonacci numbers with recursion, remembering each answer in a dict so that no number is ever calculated twice.

In the Fibonacci sequence each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55… The direct recursive function, fib(n - 1) + fib(n - 2), works out the same numbers again and again: fib(10) makes 177 calls, and fib(50) would make over 40 billion. Memoization fixes that by remembering each answer the first time it's worked out, which brings fib(10) down to 19 calls. It's the simplest example of dynamic programming: solve each smaller problem once, and reuse its answer.

Program

memo = {0: 0, 1: 1}  # the answers known so far


def fib(n):
    """The nth Fibonacci number, each one worked out only once."""
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]


print("Fibonacci 10:", fib(10))
print("Fibonacci 50:", fib(50))

Open in the editor Download fibonacci_memoization.py

Output

Fibonacci 10: 55
Fibonacci 50: 12586269025

How it works

  1. memo is a dictionary from n to the nth Fibonacci number. It starts with the first two, 0 and 1, which is where the recursion stops.
  2. If the answer for n isn't known yet, it's the sum of the two numbers before it, worked out by calling fib() again (recursion), and stored in memo.
  3. Either way, the answer is now in memo, and the function returns it. Any later call for the same n skips straight to this line.
  4. The program works out the 10th and the 50th numbers. fib(50) reuses the answers up to fib(10) that the first call left in memo.

After fib(10), memo holds every number up to it:

{0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55}

How many calls each version makes, starting from an empty memo:

Plain recursion With memo
fib(10) 177 19
fib(20) 21,891 39
fib(50) 40,730,022,147 99

Time and space complexity

TimeO(n)
Extra spaceO(n)

Each number from 2 to n is worked out once, with one addition, and every other call finds its answer in memo straight away: O(n) time, where plain recursion takes about O(1.6ⁿ). memo holds n + 1 numbers, and the calls go n deep before the first one returns, so the extra space is O(n). That depth is also a limit: Python allows about 1,000 calls running at once, so a single call such as fib(2000) on a memo that stops at 50 fails with a RecursionError.

Other ways to write it

With functools.lru_cache

@lru_cache is a decorator that does the remembering for any function, so the function itself stays the plain recursive one. maxsize=None keeps every answer; since Python 3.9, @cache does the same.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(100))

Bottom-up, with a loop

Working up from the start needs no recursion and no dict: two variables hold the last two numbers, and each step moves them one place along. It's O(n) time and O(1) space, with no limit on how far it can go.

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib(50))

Try it yourself

  • Print memo after fib(10) to see every answer it remembered, then again after fib(50).
  • Count the calls: add a global calls = 0, add 1 to it at the start of fib(), and print it after fib(10). It's 19; the plain recursive version makes 177.
  • Add print(fib(2000)) at the end. It fails with a RecursionError; the bottom-up version works it out at once.
  • Count the ways to climb a staircase taking 1 or 2 steps at a time: it's the same sum of the two before. Start memo at {1: 1, 2: 2}, and fib(10) gives 89 ways to climb 10 steps.

More dynamic programming programs

Share this program