"""
fibonacci
┌ 1; n = 0
fibo(n) = ┤ 1; n = 1
└ fibo(n-1) + fibo(n-2); n > 1
http://www.geocities.jp/m_hiroi/light/pyalgo01.html
"""
"""
fibo(5) ┬ fibo(4) ┬ fibo(3) ┬ fibo(2) ┬ fibo(1)
│ │ │ │
│ │ │ └ fibo(0)
│ │ └ fibo(1)
│ └ fibo(2) ┬ fibo(1)
│ │
│ └ fibo(0)
│
└ fibo(3) ┬ fibo(2) ┬ fibo(1)
│ │
│ └ fibo(0)
└ fibo(1)
There are many duplicated calls above. This is inefficient.
"""
def fibo(n):
if n == 0 or n == 1: return 1
# double recursion
return fibo(n - 2) + fibo(n - 1)
"""
Tail recursive
fibo(5)
fibo(4, 1, 1)
fibo(3, 2, 1)
fibo(2, 3, 2)
fibo(1, 5, 3)
fibo(0, 8, 5)
=> return a1: 8
=> 8
=> 8
=> 8
=> 8
=> 8
"""
def fibo_tr(n , a1=1, a2=0):
if n < 1: return a1
return fibo_tr(n-1, a1 + a2, a1)
"""
Tail recursive optimization
"""
def fibo_tr_opt(n):
a1, a2 = 1
while n > 0:
a1, a2 = a1 + a2, a1
n -= 1
return a1
"""
memorize fibo
http://www.python-course.eu/python3_memoization.php
"""
def fibo_memo(n, memo):
if n == 0 or n == 1: return 1
if n in memo:
return memo[n]
memo[n] = fibo_memo(n - 2, memo) + fibo_memo(n - 1, memo)
return memo[n]
def memorize(f):
memo = {}
def helper(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return helper
fibo_memo2 = memorize(fibo)
@memorize
def fibo_memo_dec(n):
if n == 0 or n == 1: return 1
# double recursion
return fibo(n - 2) + fibo(n - 1)
class Memoize:
def __init__(self, fn):
self.fn = fn
self.memo = {}
def __call__(self, *args):
# args is tuple
if args not in self.memo:
self.memo[args] = self.fn(*args)
return self.memo[args]
@Memorize
def fibo_memo_dec(n):
if n == 0 or n == 1: return 1
# double recursion
return fibo(n - 2) + fibo(n - 1)
ref:
http://ymotongpoo.hatenablog.com/entry/2015/02/23/165341