Last active
August 20, 2020 09:46
-
-
Save hughesadam87/0920d7a79daf451778fa25b918ef9690 to your computer and use it in GitHub Desktop.
Fibonacci Python (memoized and unmemoized)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ Python implementation of recursive fib with/without memoization and bottom up (with pytests) """ | |
| def fib(n): | |
| assert n >= 0, f"n was negative ({n})" | |
| # Base cases | |
| if n in [0, 1]: | |
| return n | |
| return fib(n - 1) + fib(n - 2) | |
| def fib_memoized(n): | |
| seen = {} | |
| def fib(m): | |
| assert m >= 0, f"n was negative ({n})" | |
| if m in [0, 1]: | |
| return m | |
| if m in seen: | |
| return seen[m] | |
| result = fib(m - 1) + fib(m - 2) | |
| seen[m] = result | |
| return result | |
| return fib(n) | |
| def fib_bottom_up(n): | |
| assert n >= 0, f"n was negative ({n})" | |
| if n in [0, 1]: | |
| return n | |
| seen = {0: 0, 1: 1} | |
| for i in range(2, n + 1): | |
| seen[i] = seen[i - 1] + seen[i - 2] | |
| return seen[n] | |
| def test_fib(): | |
| assert fib(6) == 8 | |
| def test_fib_mem(): | |
| assert fib_memoized(6) == 8 | |
| def test_fib_bottom_up(): | |
| assert fib_bottom_up(6) == 8 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Note that I used inner function in
fib_memoizedwhich I think it cleaner than using a class or something else as wrapper.By the way, the bottum_up approach is many problems is so much easier to understand that it's weird that we have to study all this recursive stuff for programming interviews. Sure, it helps you think (I guess) but recursive solutions also take up more memory anyway so why wouldn't we just go with bottom up?