今週もこちらのイベントに参加してきたので、会の様子と感想を書いていこうと思います。
再帰と反復
反復は再帰と比較して、TCOを使うなどスタックフレームを節約することができるし、計算量も減るため、(メモ化などを使わない場合は)高速であるという話を確認していきました。
確認は、実際にコードレベルで書いてみて、(メモ化などを使わない)再帰のほうが処理がどうしても多くなってしまうよね、というのを考えていきました。
再帰
(factorial 6)
=(* 6 (factorial 5))
=(* 6 (* 5 (factorial 4)))
=(* 6 (* 5 (* 4 (factorial 3))))
=(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
...
反復
(factorial 6)
=(fact-iter 1 1 6)
=(fact-iter 1 2 6)
=(fact-iter 2 3 6)
=(fact-iter 6 4 6)
なぜn^3になるのか？
今日はこの部分をひたすらに話していきました。
階乗の計算の場合、再帰を使ってもどうやってもO(n^3)にはならないので、本の例を改めて見ていったのですが、各再帰呼び出しが2つの新しい呼び出しを生成するが故に計算量が指数関数的に増加することまでしか分からず、コンパイラの最適化の仕組みなどを見ていかないとどうしようもないのかな？という結論に落ち着きました。
また、生成AIなどの力も借りながら、本書のプログラムの計算量の増加度合いを厳密に計算してみたのですが、O(2^n)がどうも近そうだという結論に至り、これがO(n^3)と近似するかを確認してみたのですがやはり近似はしておらず、著者も厳密な計算をしているというよりは実行時間を数回計測して、「なんとなくこれくらいになりそうだ」くらいで書いているんじゃないのか？という話で終わりました。
メモ化
延長線で、メモ化の仕組みを見ていきました。
以下のような再帰があったときに、fibonacci (1)など複数回計算されるものをキャッシュするのがメモ化で、メモ化をすることで実行時間はたしかに反復のときと同等レベルに落ち着きそうだということを話していきました。
全体を通した感想
オブジェクト指向の話になかなかいかないところは悩みどころですが笑、アルゴリズム周りの話を一緒にする機会はコミュニティだと全然これまでなかったので、頭の良い体操になって面白かったです。
本書のプログラム以外のプログラムでも本書の内容を適用してみて、生成AIや他の教科書の力も借りながら理解が少しずつ進んでいく感じも印象的でした。
