memoization.py
· 553 B · Python
Raw
# example of memoization in python for fibonacci
# Memoization: Let’s Be Efficient, Shall We?
# Ever worry about recursion and the stack and so on...
# Ever ask the same question over and over?
# Annoying, right? That’s what your computer thinks too.
# Memoization fixes this by storing results so you don’t have to repeat expensive calculations.
def fib(n, memo={}):
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
fib(100)
# 354224848179261915075
| 1 | # example of memoization in python for fibonacci |
| 2 | |
| 3 | # Memoization: Let’s Be Efficient, Shall We? |
| 4 | # Ever worry about recursion and the stack and so on... |
| 5 | # Ever ask the same question over and over? |
| 6 | # Annoying, right? That’s what your computer thinks too. |
| 7 | # Memoization fixes this by storing results so you don’t have to repeat expensive calculations. |
| 8 | def fib(n, memo={}): |
| 9 | if n in memo: |
| 10 | return memo[n] |
| 11 | if n < 2: |
| 12 | return n |
| 13 | memo[n] = fib(n - 1, memo) + fib(n - 2, memo) |
| 14 | return memo[n] |
| 15 | |
| 16 | fib(100) |
| 17 | |
| 18 | # 354224848179261915075 |
| 19 |