初学者向け | 海外のCS授業で習った再帰関数をデザインする4ステップ
はじめまして！海外大学CS専攻しているみゃおち(@MeowNotFound)です。
はじめに
本記事では、私が海外大学のコンピュータサイエンスの授業で学んだ「再帰関数の設計を4ステップで考える方法」を紹介します。初学者でもスムーズに理解できるようにイラストも含めて、段階を踏んで解説しています。再帰とはなにかから始まりますので、必要に応じて目次をご活用ください。
再帰について知る
そもそも再帰法とは？
再帰（リカージョン）とは、関数が自分自身を呼び出して、より小さな同じ問題を解く手法です。
なぜ再帰を使うのか？
再帰は、繰り返し処理をより自然な形で書けるときに便利です。特に、構造が再帰的なデータ（例：木構造、分割統治法などのアルゴリズム）を扱う場面で力を発揮します。
初学者にとっては「繰り返し処理のもう一つの選択肢」として、再帰の考え方を身につけておくと、後々の学習にも役立ちます。
再帰はなぜ動作するのか？
再帰呼び出しは、関数が「一時停止」して次の関数を呼び出し、戻ってきたときに処理を再開する仕組みです。これをコールスタック（呼び出しスタック）と呼びます。
再帰関数は、自分自身を呼び出すたびに「いったん途中で止まり」、新しい関数の処理が終わるのを待ちます。この「途中で止まった状態」は、スタック（積み重ね）構造で記録されていて、最後の呼び出しから順番に戻って処理を再開します。
たとえば factorial(3) を呼び出すと、内部的には次のような順番で処理されます：
-
factorial(3)はfactorial(2)を呼ぶ（自分は止まる） -
factorial(2)はfactorial(1)を呼ぶ -
factorial(1)はfactorial(0)を呼ぶ（ここで終了条件に到達） - 戻りながら結果を計算：
factorial(1)→factorial(2)→factorial(3)
このように、再帰呼び出しは「積み木を積んでから、上から順に外していく」ような動きになります。
再帰設計の4ステップ
さあ、ここで再帰関数のデザインステップを定義しようと思います。
- Shrink – 問題を小さくする（例: n-1, n/2）
- Combine – 小さな答えを組み合わせる （結果を融合する）
- Base Case – 終了条件を明確にする
- Code – ロジックをコードに落とす
まずは条件分岐を再帰関数に変換してみよう
いきなり再帰を設計する前に、慣れ親しんだループ版の選択ソートを見て、これを再帰に書き換えるというところから始めていきます。
一見ループで十分に思える処理をあえて再帰で書くことで、再帰の構造的な考え方（縮小・結合・終了条件）を実感できます。こうした練習を通して、「どんな問題でも再帰で解ける」力が身につきます。
void selectionSort(double* list, int listSize) {
for (int i = 0; i < listSize; i++) {
// list[i..listSize-1] で最小値を探す
double currentMin = list[i];
int currentMinIndex = i;
for (int j = i + 1; j < listSize; j++) {
if (currentMin > list[j]) {
currentMin = list[j];
currentMinIndex = j;
}
}
// 必要なら交換
if (currentMinIndex != i) {
list[currentMinIndex] = list[i];
list[i] = currentMin;
}
}
}
変換ルール
- 各ループにつき固有の再帰関数を作る
- ネストがある場合はネストの深さ分だけ再帰関数を用意する
変換の流れ
-
2 つのループを理解
- 外側ループ … 次に整列済みに加える位置を決定
- 内側ループ … 未整列領域の最小値を探索
-
内側ループを再帰化（最小値インデックスを返す）
ここで再帰法の登場です！※i は探索の開始位置、j は終了位置ですint findMin(double *list, int i, int j) { if (i == j) return i; // 終了条件（ステップ３） int k = findMin(list, i + 1, j); // 問題を縮小（ステップ１） return (list[i] < list[k]) ? i : k; // 結果を結合（ステップ２） } -
外側ループを再帰化
こちらも同じように再帰法に変換します。void selectionSort(double *list, int n, int cur) { if (cur == n) return; // 終了条件 int minIdx = findMin(list, cur, n-1); if (minIdx != cur) std::swap(list[minIdx], list[cur]); selectionSort(list, n, cur + 1); // 次へ }
例 1：階乗
- Shrink – 問題を小さくする → factorial(n-1)
- Combine – 小さな答えを組み合わせる → factorial(n) = n * factorial(n-1)
- Base Case – 終了条件を明確にする → factorial(0) = 1
- Code – ロジックをコードに落とす
int factorial(int n) {
if (n == 0) return 1; // 終了条件
return n * factorial(n - 1); // 縮小＋結合
}
例 2：配列を逆順に出力
- Shrink – 問題を小さくする → Print the rest → printReverse(arr, n - 1)
- Combine – 小さな答えを組み合わせる → After recursion, print the current element → cout << arr[n - 1]
- Base Case – 終了条件を明確にする → n == 0になったらストップ
- Code – ロジックをコードに落とす
void printReverse(int arr[], int n) {
if (n == 0) return; // 終了条件
std::cout << arr[n-1] << " ";
printReverse(arr, n-1); // 縮小
}
再帰を使うときの注意点：スタックオーバーフローに気をつけよう
再帰はとても便利な手法ですが、使い方を間違えると 「スタックオーバーフロー（stack overflow）」というエラー を起こすことがあります。
スタックとは？
コンピュータは関数を呼び出すたびに、その関数の情報（引数、戻り先など）を スタック と呼ばれる「積み重ねのメモリ」に一時的に保存します。
この記事では度々出てくる表現ですが、このスタックは、「積み木のタワー」 のようなものです。
もちろんこの積み木（スタック）には 上限 があるので、あまりにも多くの関数を呼び続けるとメモリが足りなくなってしまいます。
スタックオーバーフローとは？
終了条件がない再帰 や、極端に深い再帰呼び出し をすると、スタックの上限を超えて プログラムがクラッシュ します。これを スタックオーバーフロー と呼びます。
// 終了条件のない危険な再帰
int factorial(int n) {
return n * factorial(n - 1); // 終了条件ないので無限に呼び出してしまう！
}
防ぐためのポイント
- 必ず 終了条件（Base Case） を正しく書く
- 再帰のたびに 終了に向かって進んでいるか を確認する
- 呼び出しが深くなりすぎる問題では ループや別の方法に書き換える ことを検討する
練習問題
- 連続した重複文字を削除する再帰関数
removeDup(s)を実装せよ- 例:
removeDup("aabbccca") → "abca"
- 例:
さいごに
少しでも参考になれば幸いです〜！
さらに学びたい方はTail Recursion（末尾再帰）や木構造アルゴリズムなど、さらに学習の幅を広げてみてくださいね:)
Discussion