2025/08/08 15:10 Why Tail-Recursive Functions Are Loops
やあ、ロボ子！今日は再帰関数とループの面白い話をするのじゃ。
博士、こんにちは。再帰関数とループですか、興味深いですね。どちらも繰り返し処理を実現する手段ですが、違いは何でしょうか？
そうじゃな。まず、大前提として「ループと末尾再帰は等価」なのじゃ。そして、再帰関数は帰納法との相性が抜群なのじゃ！
なるほど、等価なのですね。でも、再帰関数はループよりも遅いと聞いたことがあります。
その通り！「再帰関数はスタックフレームをプッシュするため、一般にループよりも遅い」のじゃ。ループはアキュムレータを使って部分的な結果を蓄積するから、一定の空間で線形時間で実行できるのじゃ。
スタックフレームのプッシュがボトルネックになるのですね。具体的にどのような場合に問題になるのでしょうか？
例えば、深い再帰呼び出しをする場合じゃな。「直接的な実装では、再帰呼び出しはスタックフレームをプッシュし、O(n)のスタック領域を必要とする」から、スタックオーバーフローを起こす可能性があるのじゃ。
スタックオーバーフローは避けたいですね。何か対策はありますか？
そこで「末尾再帰」の出番じゃ！「末尾再帰では、すべての再帰呼び出しは末尾呼び出しでなければならない」のじゃ。
末尾呼び出し、ですか？
そう。「末尾呼び出しは、式の戻り値が式全体からの戻り値である場合に、末尾位置にある」のじゃ。つまり、再帰呼び出しの結果をそのまま返すということじゃな。
なるほど。末尾再帰にすると、何が良いのでしょうか？
「末尾呼び出し最適化を行うコンパイラは、末尾呼び出しをjmp文にコンパイルし、スタックの使用量をゼロにする」のじゃ！これでスタックオーバーフローの心配もなくなるのじゃ！
すごい！コンパイラが最適化してくれるんですね。でも、末尾再帰になっていない場合はどうすれば良いのでしょうか？
そんな時は「継続渡しスタイル（CPS）変換」じゃ！「CPS変換により、すべての呼び出しを末尾呼び出しにすることができ、スタックを排除できる」のじゃ。
CPS変換ですか。少し難しそうですね。
大丈夫！CPS変換は、関数に「次に何をすべきか」という継続を渡すことで、処理の流れを明示的にするのじゃ。ただ、「CPS変換されたプログラムは、ヒープに割り当てられた継続を使用するため、スタックオーバーフローが発生する可能性がある」ことには注意が必要じゃ。
ヒープに割り当てることで、スタックオーバーフローのリスクを減らすんですね。勉強になります！
そういうことじゃ！再帰関数とループ、そして末尾再帰最適化をうまく使いこなして、より効率的なコードを書くのじゃ！
はい、博士！頑張ります！
ところでロボ子、再帰関数が好きなプログラマーは何科に進むと思う？
えっと…再帰…ですか？うーん、わかりません！
それは、きか（帰化）関数じゃ！
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。