フィボナッチ数列の実装法は色々とある。プログラミングの題材としても好まれてるしな。
ここでは次のような実装法を紹介しよう。
def fibs(n):
head = [0, 1]
if n < 2:
return head[:n + 1]
else:
tail = fibs(n-1)
return head + [sum(i) for i in zip(tail[:-1], tail[1:])]
ここでは変数tailで再帰を行っている。
この実装のポイントは、再帰を使って設定した変数tail(fibsの返り値によりリストである)をズラシつつ加算する事でフィボナッチ数列を作り上げてるトコロである。
次の表を見てもらいたい。
[0, 1, 1, 2, 3, 5, 8, 13] <= tail[:-1][1, 1, 2, 3, 5, 8,13, 21]<= tail[1:][0, 1, 1, 2, 3, 5, 8,13,21,34]<= fibs(n)
関数fibsがn > 1の時、その値はtail[:-1]とtail[1:]のそれぞれの要素の和になってるのが分かるだろうか。
と言う事は関数fibsがn>1に於いて、tail[:-1]とtail[1:]のそれぞれの要素の組の和を取ればフィボナッチ数列が生成される筈である。
と言うわけで、まずはtail[:-1]とtail[1:]のそれぞれの要素の組を作る。
Pythonでこのテの作業をする機能が組み込み関数zipである。
>>> list(zip([0, 1, 1, 2, 3, 5, 8, 13], [1, 1, 2, 3, 5, 8, 13, 21]))
[(0, 1), (1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 13), (13, 21)]
>>>
組み込み関数zipは過去のPython(2.0系列)と違ってイテラブルを返すんで、データを可視化するには組み込み関数listを用いなければならないが、いずれにせよ、キチンと意図したデータの組を返してるのが分かるだろう。
>>> [sum(i) for i in zip([0, 1, 1, 2, 3, 5, 8, 13], [1, 1, 2, 3, 5, 8, 13, 21])]
[1, 2, 3, 5, 8, 13, 21, 34]
>>>
これで動作保証が出来た。形式的にはリスト内包表記を用いて、zipで纏められた各要素の和を算出しながらリストを生成する。
この形式を用いれば上で見せたようなフィボナッチ数列のコードをでっち上げる事が出来るのだ。
