Javaへの関数的アプローチ

第12章. 再帰的

この作品はAIを使って翻訳されている。ご意見、ご感想をお待ちしている：[e-mail]

再帰は、それ自身をより小さなバージョンに分解できる問題を解決するアプローチである。 多くの開発者は、再帰を反復ベースの問題解決への、しばしば複雑な別のアプローチと見なしている。 それでも、機能的な方法で特定の問題群に対するさまざまなテクニックを知っておくことは良いことだ。

この章では、再帰の背後にある一般的な考え方、再帰的メソッドの実装方法、そしてJavaコードにおける再帰の位置づけを、他の形式の反復と比較して示す。

再帰とは何か？

再帰」では、階乗（入力パラメータ以下のすべての正の整数の積）を計算する例を見てきた。 多くの本やガイド、チュートリアルでは、再帰を示すために階乗を使っている。部分的に解くには最適な問題だからである。

階乗の計算の各ステップは、入力パラメータと次の階乗演算の結果の積に分解される。 計算がfac(1)（"1 "と定義）に達すると、連鎖は終了し、前のステップに値を提供する。 完全なステップは、式12-1で見ることができる。

式12-1. 階乗計算の形式的表現

$$\begin{array}{c}fac\left(n\right)\hfill \\ \hfill \to & n*fac(n-1)\hfill \\ \hfill \to & n*(n-1)*fac(n-2)\hfill \\ \hfill \to & n*(n-1)*(n-2)*\cdots *fac\left(1\right)\hfill \\ \hfill \to & n*(n-1)*(n-2)*\cdots *1\hfill \end{array}$$

この計算ステップの一般化は、再帰の根底にある概念、つまり同じ問題の小さなインスタンスを組み合わせて問題を解くという概念を視覚化したものである。 これは、基本条件に達するまで引数を変更して呼び出すメソッドを用いて行われる。

再帰は2つの異なる演算子で構成されている：

基本条件付き

基本条件とは、実際の値を返し、再帰的呼び出しチェーンを解き放つ、問題の解決策となる定義済みのケースのことである。基本条件は、その値を前のステップに提供し、前のステップは結果を計算し、それを前のステップに返すことができる。

再帰的呼び出し

呼び出しチェーンが基本条件に達するまで、各ステップは、変更された入力パラメータで自分自身を呼び出すことで、別の呼び出しチェーンを作成する。

図12-1は、再帰的呼び出しチェーンの一般的な流れを示している。

図12-1. より小さな問題で問題を解く

この解は次の大きな問題の入力となり、すべてのパーツの合計が元の問題の解を構築するまで続く。

ヘッドとテールの再帰的比較

再帰的呼び出しは、メソッド本体における再帰的呼び出しの位置によって、先頭再帰と末尾再帰の2つに分類される：

再帰的ヘッド

再帰的メソッド呼び出しの後に他の文/式が実行/評価されるため、最後の文にはならない。

テール再帰的

再帰的呼び出しは、メソッドの最後の文であり、その結果を現在の呼び出しにリンクさせるような更なる計算はない。

例題12-1では、再帰的ヘッダーの使い方を示している。

例 12-1. 再帰的に階乗を計算する

long