This is possible because python has mutable default arguments. It is functionally the same as the lrucache approach (though arguably less pythonic)
I like this approach because it allows you to reset the cache when needed, while also keeping it between problems, so if you want to keep looking for fib numbers, the memoization is already done, but if you're using this method for something like kepping track of visited nodes in a graph, you can just clear the cache every time you make a new graph.
def fib(n, memo = {0:1, 1:1}): if n not in memo: memo[n] = fib(n-1)+fib(n-2) return memo[n]def fib(n):memo = {0:1, 1:1}def recursiveFib(n):if n not in memo:memo[n] = recursiveFib(n-1)+recursiveFib(n-2)return memo[n]return recursiveFib(n)- def fib(n, memo = {0:1, 1:1}):
- if n not in memo:
- memo[n] = fib(n-1)+fib(n-2)
- return memo[n]
Start getting floating point errors around number 70. Darn you Python.
import math def fib(n): return long((((1+math.sqrt(5))/2)**(n+1) - ((1-math.sqrt(5))/2)**(n+1))/math.sqrt(5))def fib(x):f1, f2 = 0, 1for x in range(x):f1, f2 = f2, (f1 + f2)return f2- import math
- def fib(n):
- return long((((1+math.sqrt(5))/2)**(n+1) - ((1-math.sqrt(5))/2)**(n+1))/math.sqrt(5))
test.assert_equals(1, fib(0)) test.assert_equals(1, fib(1)) test.assert_equals(2, fib(2)) test.assert_equals(3, fib(3)) test.assert_equals(5, fib(4)) test.assert_equals(8, fib(5)) a = 0 b = 1 for i in range(50): test.assert_equals(b, fib(i)) tmp = a a = b b = tmp + b- test.assert_equals(1, fib(0))
- test.assert_equals(1, fib(1))
- test.assert_equals(2, fib(2))
- test.assert_equals(3, fib(3))
- test.assert_equals(5, fib(4))
- test.assert_equals(8, fib(5))
- a = 0
- b = 1
for i in range(1000):- for i in range(50):
- test.assert_equals(b, fib(i))
- tmp = a
- a = b
- b = tmp + b