Pythonではじめるバイオインフォマティクス ―可読性・拡張性・再現性のあるコードを書くために

4章

フィボナッチ数列の作成：アルゴリズムのコーディング、テスト、およびベンチマーク

　フィボナッチ数列を実装することは、コードを書けるようになる旅路のもう1つのステップです。Rosalind Fibonacciの記述（https://oreil.ly/7vkRw）には、この数列の起源はウサギの繁殖に関する数学的シミュレーションであり、いくつかの重要な（そして非現実的な）仮定に依存していることが記されています。

• 最初の1ヶ月は、生まれたばかりのペアのウサギから始まる。
• ウサギは1ヶ月後に繁殖することができる。
• 毎月、生殖年齢に達したウサギは、別の生殖年齢に達したウサギと交尾をする。
• 2匹のウサギが交尾してからちょうど1ヶ月後に、親と同じ数の子ウサギのペアを産む。
• ウサギは不死で、交尾をやめることはない。

　図4-1に示されているように、数列は常に0と1から始まり、リストの中の直前の2つの値を加えることによって、後続の数字を無限に生成することができます。

図4-1　フィボナッチ数列の最初の8つの数――最初の0と1の後、前の2つの数を足すことで後続の数が作られる

　解法をインターネットで検索すると、数列を生成する方法が何十種類も出てきます。ここでは、かなり異なる3つのアプローチに注目したいと思います。最初の解法は、アルゴリズムがすべてのステップを厳密に定義する命令型アプローチを使用しています。次にジェネレータ関数を使った方法、そして最後に再帰的な方法に焦点を当てます。再帰は面白いのですが、より多くの数列を生成しようとすると劇的に遅くなります。しかし、パフォーマンスの問題はキャッシュを使って解決できることがわかりました。 ...