同じ形の小さな問題を自分自身へ渡す
再帰の中心にあるのは、大きな問題を「同じ種類で、少し小さい問題」に置き換える考え方です。たとえば、あるフォルダ以下にあるファイルをすべて調べるとします。最初のフォルダにあるファイルを確認し、子フォルダがあれば、その子フォルダについてもまったく同じ手順を実行します。深さが何段あるかを先に決めなくても、同じ処理を適用し続けられます。
プログラムでは、ある関数の実行中に、その関数自身を呼び出してこの考え方を表します。ただし、「自分を呼ぶ」という書き方だけが重要なのではありません。呼び出すたびに対象が小さくなり、最後には答えを直接出せる状態へ到達することが必要です。問題の構造とプログラムの形が対応するため、木の枝のように分かれるデータや、入れ子になったデータを処理するアルゴリズムを簡潔に表せることがあります。
再帰を止める「基本部分」が先に必要になる
再帰処理は、基本部分と再帰部分の組み合わせで成り立ちます。基本部分とは、それ以上自分自身を呼ばずに答えを返す場合です。再帰部分とは、対象を小さくして自分自身へ処理を任せ、その結果を使って答えを作る場合です。
設計するときは、次の二点を確かめます。
- どの状態なら直接答えを返せるか：これが終了条件になります。
- 一回の呼び出しで終了条件へ近づくか：数を一つ減らす、木の一段下へ進むなど、進み方を明確にします。
終了条件がなかったり、引数が終了条件へ近づかなかったりすると、呼び出しは止まりません。たとえば「0なら終了する」と決めても、正の数を増やしながら呼び出していては0へ到達しません。終了条件を書いたという事実だけでなく、想定するすべての入力が実際にそこへ到達するかを確認する必要があります。
4の階乗が答えになるまでをたどる
正の整数を1まで順に掛ける階乗は、再帰の流れを観察しやすい例です。factorial(n)を「nとfactorial(n - 1)を掛けた値」、factorial(1)を「1」と定めると、JavaScriptでは次のように書けます。
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}factorial(4)を呼ぶと、すぐに掛け算が完了するわけではありません。まず4 * factorial(3)、次に3 * factorial(2)、さらに2 * factorial(1)まで進みます。factorial(1)が1を返すと、待っていた計算が逆向きに再開し、2 * 1、3 * 2、4 * 6の順に結果が確定します。処理が深い方へ進む段階と、結果を持って戻る段階を分けて考えると、再帰を追いやすくなります。
この例は1以上の整数を前提にしています。0の階乗も扱うなら、基本部分をn === 0のとき1を返す形にする必要があります。どの入力を受け付けるかによって、適切な終了条件も変わります。
呼び出しの途中経過はスタックに積まれる
関数が別の関数を呼び出すと、実行を再開する場所や、その時点の引数・局所的な変数など、処理を続けるための情報が保持されます。この呼び出し情報は、後から入ったものを先に取り出す「スタック」という方式で管理されます。再帰では関数が完了する前に同じ関数をさらに呼ぶため、呼び出しの深さに応じて情報が積み重なります。
深すぎる再帰は、呼び出し情報を保存する領域を使い切り、実行時のエラーになることがあります。許される深さはプログラミング言語や実行環境などに左右されるため、「何回までなら必ず安全」という共通の値はありません。入力によって非常に深くなる可能性がある処理では、明示的なスタックを用意したり、ループへ書き換えたりする方法を検討します。
再帰とループは読みやすさと負担で選ぶ
階乗のように、再帰でもループでも書ける処理は多くあります。単純に数を増減させるだけなら、ループは呼び出し情報を何段も保持せずに済み、処理の流れも追いやすい場合があります。一方、左右の部分木を同じ方法で調べる木構造の探索などでは、再帰の形がデータの形と自然に一致します。
短く書けることと、効率がよいことは同じではありません。同じ計算を何度も呼び出す再帰では、処理時間が大きく増えることがあります。すでに求めた結果を保存して再利用する、分割の方法を変える、ループに置き換えるといった改善が可能です。選択するときは、入力が大きくなったときの計算量と、呼び出しの深さの両方を考えます。
フォルダやWebページにも現れる「再帰的な形」
再帰は計算式だけの技法ではありません。フォルダの中に別のフォルダを置けるように、ある種類の要素の中に同じ種類の要素を含められる構造を、再帰的な構造と呼びます。Webページの文書構造でも、要素の内側に別の要素が入り、その中にさらに要素が入ることがあります。家系図や組織図のような木構造も、ある節から下を切り出すと、全体と同じような枝分かれの形として扱えます。
ここで大切なのは、見た目が繰り返し模様であることではなく、「全体と同じ規則で部分も扱える」ことです。その性質があるため、現在の要素を処理し、含まれる子要素へ同じ処理を適用するだけで、深さの異なる構造にも対応できます。再帰という名前は関数の書き方を指すだけでなく、問題やデータが自分と同じ形を内側に含むという見方にも結び付いています。