fibonacchi ref: http://qiita.com/giwa/items/db5c088ff2efc956bc67

file0.txt

"""
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)