テクノロジー編26: アルゴリズム

ある関数の中で自分自身を呼び出すようなアルゴリズム。
特に、規模の大きな問題を、同じ構造を持つ小さな問題に分割して解決する際に有効。

数学の漸化式やパズルの解法、マージソート・クイックソートなどで用いられる。

問題の構造をそのままコードに反映できるため、コードが簡潔になり可読性が向上することが見込める。
再帰的に関数を呼び出すたびにメモリ上に新しいデータが積み上げられるため、パフォーマンスに若干の影響が出ることもある。

再帰的に関数を呼び出す「再帰ステップ」と、再帰を終了させるための条件「基底ケース」が必要。

再帰アルゴリズムを用いない実装例

int n = 5;
int fact = 1;
for (int i = 1; i <= n; i++) {
  fact *= i;
}

int fact(int n) {
  return n * fact(n - 1);
}
fact(5); // 無限ループ

int fact(int n) {
  if (n == 0) {
    // 基底ケース
    return 1;
  }
  // 再帰ステップ
  return n * fact(n - 1);
}
fact(5); // 6