Pythonで再帰フィボナッチのメモ化

# -*- 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