python〜再帰関数とメモ化とフィボナッチ数列

はじめに

こんにちは，Keymaleです．今回はフィボナッチ数列を用いて再帰関数とメモ化をメインに説明していきます．関数の計算時間はこちらの記事に記載しています．まずはフィボナッチ数列について

フィボナッチ数列

フィボナッチ数列とは，1個前と2個前の値を足していく数列で，以下のようになります．

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …..

漸化式で書くと以下のようになります．

f(n) = f(n – 1) + f(n – 2)

この数列をpythonで記述していきます．

再帰関数

早速ですが，以下のコードになります．

def fibonacci0(n):
    if n < 2:
        return n
    return fibonacci0(n - 1) + fibonacci0(n - 2)

再帰関数とは関数内で自身の関数を呼び出す関数になります．
初期値のn<2の部分以外は前回値と前々回値をreturnで返す関数になります．

再帰関数は簡単に記述できて便利ですが，fibonacci(n)を呼び出すとfibonacci(n-1)とfibonacci(n-2)を呼び出し，fibonacci(n-1)はfibonacci(n-2)とfibonacci(n-3)を呼び出し，．．．と呼び出し回数が指数関数的に増加し，計算コストがあっという間に増加してしまいます．

メモ化

そこでメモ化です．fibonacci(n)を呼び出したときにfibonacci(n-1)とfibonacci(n-2)を呼び出し，fibonacci(n-1)を呼び出したときにfibonacci(n-2)とfibonacci(n-3)を呼び出しているため，このときfibonacci(n-2)が重複しています．重複したものを保存しておいて，再度計算しなくて良いようにします．以下にコードを記載します．

memo = {0: 0, 1:1}
def fibonacci1(n):
    if n not in memo:
        memo[n] = fibonacci1(n - 1) + fibonacci1(n - 2)
    return memo[n]

memoという辞書に，nをkeyにして，値を保存しておきます．
非メモの関数とメモ化した関数で計算時間を比較してみます．
計算時間は以下のコードで行いました．

import time

def time_count(func,k):
    start = time.time()
    func(n=30)
    elapsed_time = time.time() - start
    print ("fibonacci"+str(k)+" elapsed_time:{0}".format(elapsed_time) + "[sec]")

フィボナッチ数列の30個目を計算させたときの時間です．結果はこちら

fibonacci0 elapsed_time:0.7882053852081299[sec]
fibonacci1 elapsed_time:4.76837158203125e-05[sec]

メモ化した方が4桁以上早いですね．

ただいちいちメモ化するのは面倒ですね．そこで自動メモ化です．

自動メモ化

pythonには便利な自動メモ化moduleがあります．以下のようにコードを記載します．

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci2(n):
    if n < 2:
        return n
    return fibonacci2(n - 1)+ fibonacci2(n - 2)

関数の直前に

@lru_cache(maxsize=None)

と記載するだけです．maxsizeはキャッシュサイズで，Noneとすることで無制限となります．

計算結果を比較してみましょう．

fibonacci0 elapsed_time:0.7882053852081299[sec]
fibonacci1 elapsed_time:4.76837158203125e-05[sec]
fibonacci2 elapsed_time:7.104873657226562e-05[sec]

メモ化なしよりも当然早くなりましたね．手動メモ化より若干遅いのは，キャッシュサイズに制限をつけていないせいだと思います．

再帰型は便利ですが，メモ化しても呼び出し回数が多いことに代わりありません．再帰関数で定義できるものは必ず，反復型でも定義できます．

反復型

以下に再帰関数を用いないでフィボナッチ数列を計算する方法を記載します．

def fibonacci3(n):
    if n == 0:
        return n
    last = 0
    next = 1
    for _ in range(n-1):
        last, next = next, last + next
    return next

単純に，最初から順番に足していっているものになります．速度を比較してみましょう．

fibonacci0 elapsed_time:0.7882053852081299[sec]
fibonacci1 elapsed_time:4.76837158203125e-05[sec]
fibonacci2 elapsed_time:7.104873657226562e-05[sec]
fibonacci3 elapsed_time:1.71661376953125e-05[sec]

やはりいちばん早いですね．再帰関数を使わないで関数を作れるならば，使わないに越したことはないでしょうが，コードは複雑になります．用途に合わせて使っていきましょう．

最後におまけですが，ジェネレータを載せておきます．

ジェネレータ

今までは，指定下順番のフィボナッチ数列を返していただけですが，全数列挙するものを記載します．

def fibonacci4(n):
    yield 0
    if n > 0: yield 1
    last = 0
    next = 1
    for _ in range(n-1):
        last, next = next, last + next
        yield next


for i in fibonacci4(10):
        print(i)

これを実行すると，10個目までのフィボナッチ数列が出力されます．