tmiyamon https://blog.hatena.ne.jp/tmiyamon/ ソフトウェアエンジニアに大切なこと https://tmiyamon.hatenadiary.jp/ フィボナッチ数列っていうのがあります。 フィボナッチ数 - Wikipedia 再帰の実装サンプルなんかでよく使われるアレですが、普通に実装すると簡単に処理できなくなるアレです。 よくある実装はこんなかんじですよね。 def fib(n): if n == 0 or n == 1: return 1 return fib(n-1) + fib(n-2) 定義の通りに書いた感じです。これを手元のマシンで実行したところ、n=40ほどでもう帰ってこなくなりました。 では次に、メモ化による高速化を行うとどこまでいけるのでしょうか？ 上記のサンプルでn=40で戻ってこなくなるのは、同じ計算が多すぎるから… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftmiyamon.hatenadiary.jp%2Fentry%2F2013%2F11%2F14%2F000211" title="再帰じゃないフィボナッチ数 - ソフトウェアエンジニアに大切なこと" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2013-11-14 00:02:11 rich https://tmiyamon.hatenadiary.jp/entry/2013/11/14/000211 1.0 100%