```
# -*- coding: utf-8 -*-
def fib(n):
"""フィボナッチ数列"""
if n <= 1:
return n
return fib(n-1) + fib(n-2)
def fib_memo(n):
"""メモ化フィボナッチ"""
memo = [0]*(n+1)
def _fib(n):
if n <= 1:
return n
if memo[n] != 0:
return memo[n]
memo[n] = _fib(n-1) + _fib(n-2)
return memo[n]
return _fib(n)
```

# 時間計測

```
import time
def do_fib():
start = time.time()
print(fib(50))
stop = time.time()
print("elapsed: {}".format(stop - start))
def do_fib_memo():
start = time.time()
print(fib_memo(50))
stop = time.time()
print("elapsed: {}".format(stop - start))
if __name__ == '__main__':
do_fib()
do_fib_memo()
```

実行結果

```
12586269025
elapsed: 3211.8407917022705
12586269025
elapsed: 0.0009133815765380859
```