Javaによる関数型プログラミング ―Java 8ラムダ式とStream

7章再帰の最適化

難しい問題は、それを解くために適切かつ必要なところまで分割しなさい。

――René Descartes

再帰は魅力的で強力な問題解決方法です。再帰はとても表現力に富んでいます。ある問題自体の解決方法を、その問題の部分的な問題にも適用するような解決方法を提供します。このアプローチは「分割統治法（divide and conquer）」と呼ばれます。地図上の最短距離を求める場合や、最小コストまたは最大の利益を計算する場合、無駄を削減する場合など、様々なアプリケーションに使われています。

今日使われているほとんどのプログラミング言語が再帰をサポートしています。ただ、再帰が本当に役に立つような問題は非常に大きな問題であることが多く、単純な実装では残念ながらすぐにスタックオーバーフローが発生してしまいます。そこで本章では、大きな問題の再帰処理を可能とする末尾呼び出し最適化（tail-call optimization、TCO）を説明します。最後に、問題の解法がその部分問題の解法と重なるような再帰問題を紹介し、メモ化を使ってその解決を高速にする方法を説明します。

7.1　末尾呼び出し最適化を使う

再帰を使う上で最も高いハードルは、巨大な入力値によるスタックオーバーフローのリスクです。しかし、末尾呼び出し最適化（TCO）という優れたテクニックがこの心配の種を取り除きます。末尾呼び出しとは、最後の処理が自身の呼び出しとなるような再帰呼び出しのことをいいます。これは、自身への呼び出しの後にその結果を使って処理を続ける通常の再帰とは異なります。TCOは通常の再帰呼び出しを末尾呼び出しに変えて、大きな入力値でも再帰を実用的なものにします。

JavaはTCOをコンパイラレベルで直接サポートしていませんが、ラムダ式を使って数行で実装できます。このソリューションはトランポリン ...