#Pythonで学ぶアルゴリズム< フィボナッチ数列 >

はじめに

基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第5弾としてフィボナッチ数列を扱う．

フィボナッチ数列

初項，第2項が1で，3項目以降前の2つの和でなされる数列．
例)
1,1,2,3,5,8,13,...
これをpythonで実装し，繰り返し処理の理解を深める．
以下では3つの方法でフィボナッチ数列を求めるプログラムを示すが，最後にはそれらを評価するためのコードも示し，考察する．

実装１

1つ目の方法は再帰である．
再帰とは，定義した関数の中で再度自分(関数)を呼び出すこと．
フィボナッチ数列は前項の情報を繰り返し利用して求められるため，再帰を用いることができる．
以下にコードとその時の出力を示す．

コード

fibonacci1.py

"""
2020/12/17
@Yuya Shimizu

フィボナッチ数列
再帰
関数の中で再度自分の関数を呼び出す方法
"""

def fibonacci(n):
    if n==1 or n==2:
        return 1
    return fibonacci(n-2) + fibonacci(n-1)  #再帰

print(fibonacci(30))

出力

上記のコード内でコメントして再帰と示しているところがちょうど自分(fibonacci関数)を自分(fibonacci関数)の中で呼び出しているところである．
ここで注意すべきはどこで終了させるのかという終了条件が再帰には必要であるということ．ずっと自分を呼び出し続けると終わらない．なので，今回はnが1か2になったところを終了条件としている．

実装２

実装２では実装１の処理速度問題を解決する．先ほど示した実装１は30を超え始めると少し処理が遅くなってきた．理由は明快で，毎度自分の関数を呼び出すことをしており，一度求めた(例えば第3項)を何度も求めて使おうとしている．実装２では，辞書型配列を用いて，一度求めた項の値は記憶して使うことを行う．この記憶させて行うことをメモ化というらしい．
以下にコードとその時の出力を示す．

コード

fibonacci2.py

"""
2020/12/17
@Yuya Shimizu

フィボナッチ数列
メモ化
辞書型配列にない情報を記録していく
"""
memo = {1:1, 2:1}
def fibonacci(n):
    if n in memo:
        return memo[n]
    memo[n] = fibonacci(n-2) + fibonacci(n-1)  #登録されていなければ，計算して登録
    return memo[n]

print(fibonacci(100))

出力

354224848179261915075

たとえ100項目を求めようとも素早く計算することができた．いくらでも行けそうだと思い10000項目を求めようと実行したところ次のようなエラーメッセージが出た．

  [Previous line repeated 1021 more times]
RecursionError: maximum recursion depth exceeded

どうやら再帰には繰り返し限界数があるようだ．試しに回数を調整したところ，どうやら2047という引数が限界で，2048以降はエラーメッセージが出た．

実装３

実装２では限界があることが分かった．
もっと単純に求める方法として，ループでリストに加えていくだけという方法がある．
以下にコードとその時の出力を示す．

コード

fibonacci3.py

"""
2020/12/17
@Yuya Shimizu

フィボナッチ数列
ループ
簡単な問題の場合，リストに順に加えていくだけで計算できる
"""

def fibonacci(n):
    fib = [1, 1]
    for i in range(2, n):
        fib.append(fib[i-2] + fib[i -1])
    return fib[n-1]
print(fibonacci(2048))

出力

45415304437437894250455714462906892027009082612936444289511823902789714525092834356843497180347717304332077420750102996639625006407838018797363807741815915794968069489957662592260489596860563484362187663942834824730009793065752175759244081518806465182648002219755758995565516482064617351513826704211517343602925990599710229276939710372081414109914714493582044185153918055170241694035610145547104337536614028338983073680262684101

実装２でエラーメッセージが出たといった2048項目も無事求められた．実行した感覚では非常に処理は速かったと思う．

評価

実際のところどのくらいの処理速度で計算できるのかを計測し，比較して評価する．コードの構造自体は今回どれも単純であるため評価には考慮していない．以下にコードそれぞれの評価用コードを示す．

コード１:再帰

fibonacci1_evaluation.py

"""
2020/12/17
@Yuya Shimizu

フィボナッチ数列
再帰
関数の中で再度自分の関数を呼び出す方法
"""

def fibonacci(n):
    if n==1 or n==2:
        return 1
    return fibonacci(n-2) + fibonacci(n-1)  #再帰

# 評価
import time

start = time.time()
fibonacci(35)
process_time = time.time() - start

print(process_time)

コード２:メモ化

fibonacci2_evaluation.py

"""
2020/12/17
@Yuya Shimizu

フィボナッチ数列
メモ化
辞書型配列にない情報を記録していく
"""

memo = {1:1, 2:1}
def fibonacci(n):
    if n in memo:
        return memo[n]
    memo[n] = fibonacci(n-2) + fibonacci(n-1)  #登録されていなければ，計算して登録
    return memo[n]

# 評価
import time

start = time.time()
fibonacci(2047)
process_time = time.time() - start

print(process_time)

コード３:ループ

fibonacci3_evaluation.py

"""
2020/12/17
@Yuya Shimizu

フィボナッチ数列
ループ
簡単な問題の場合，リストに順に加えていくだけで計算できる
"""

def fibonacci(n):
    fib = [1, 1]
    for i in range(2, n):
        fib.append(fib[i-2] + fib[i -1])
    return fib[n-1]

# 評価
import time

start = time.time()
fibonacci(2047)
process_time = time.time() - start

print(process_time)

評価結果

以下にそれぞれの実行結果を示す．ただし，引数の値は計算上合わせにくかったため，それぞれのプログラムで異なる引数を与えた．コード１は計算上苦しくない程度の引数で35とし，コード２は限界の2047とし，コード３についてはコード２に合わせて2047とした．これでも３つを比較するという観点でいうと十分評価できるのではないかと思う．
以下にそれぞれの出力を示す．

出力１(フィボナッチ数列35項目)

6.196547746658325

出力２(フィボナッチ数列2047項目)

0.001993894577026367

出力３(フィボナッチ数列2047項目)

0.0009958744049072266

以上が結果であるが，出力１は処理速度に難ありといった感じである．出力２は速いが限界があるという点でほかに劣る．出力３は他に比べてかなり高速でありながら，限界もないということで優れているのではないかと評価できる．

感想

再帰は聞いたことはあったが使ったことはなく，またメモ化については聞いたこともなかったため，それらを学ぶよい機会となった．さらに再帰に限界があることも知ることができた．

参考文献

Pythonで始めるアルゴリズム入門　伝統的なアルゴリズムで学ぶ定石と計算量
　　　　　　　　　　　　　　　　　　　　　　　　増井敏克　著　　翔泳社