読み方：さいきてきアルゴリズム

再帰的アルゴリズム【recursive algorithm】

再帰的アルゴリズムとは？

ある処理を定義する際に自分自身を呼び出す構造を持つアルゴリズムのこと。問題を同じ形のより小さな問題へと分解し、その積み重ねで最終的な答えを得る仕組みである。

再帰的アルゴリズムは関数などを用いて定義され、「関数を終了させる条件」（基底条件）と「自分自身を呼び出す再帰呼び出し」の二つで構成される。関数が実行されると、問題をより小さな単位に分割して、これを解くよう自分自身を呼び出す。

呼び出しの度に問題の規模が少しずつ縮小され、最終的に基底条件に到達したら、最小単位となった問題を問いて解を返却する。呼び出し元は返却された部分的な解をもとに、より大きな単位の解を問いて返却する。これを繰り返すことで全体の計算が完結する。基底条件がなければ関数の呼び出しは無限に続き、プログラムはメモリを使い果たして強制終了してしまう。

この仕組みが特に力を発揮するのは、構造が入れ子状になった問題である。フォルダの中にフォルダが入り込むファイルシステムや、木構造のデータ探索では、同じ処理を対象に繰り返し適用するだけで全体を走査できる。階乗やフィボナッチ数列のように、問題の定義そのものが自己参照的な数学的問題とも相性がよく、ループで書くより意図が直感的に伝わるコードになることが多い。

一方、関数を呼び出すたびにその時点の実行状態を「スタック」（stack）と呼ばれるメモリ領域に積み上げる必要があるため、再帰の深さが大きくなるとスタック領域が足りなくなる「スタックオーバーフロー」が起きる恐れがある。また、単純な実装では同じ計算を何度も繰り返してしまい、処理効率が落ちる場合もある。対策として、一度計算した結果を保存して再利用する「メモ化」や、再帰をループ処理に書き換える手法が用いられる。