再帰
再帰（Recursion）とは、関数がその定義または実行中に直接的または間接的に自身を呼び出すプログラミング手法です。核となる考え方は、複雑な問題をより小さく構造が同じ部分問題に分解することです。
再帰の基本概念
再帰呼び出しのスタックフレームの変化 — factorial(3) を例に
fact(3)fact(2) の戻りを待つ → プッシュ
↓ 呼び出し
fact(2)fact(1) の戻りを待つ → プッシュ
↓ 呼び出し
fact(1)fact(0) の戻りを待つ → プッシュ
↓ 呼び出し
fact(0) = 1ベース条件！戻り始める → ポップ
↑ 層ごとに戻る (LIFO)
fact(3) = 3 × fact(2) = 3 × 2 × fact(1) = 3 × 2 × 1 × fact(0) = 3 × 2 × 1 × 1 = 6
オレンジ色の枠（ベース条件）→再帰を停止して戻り始める | スタックフレームはLIFO順にポップされる：最後にプッシュされたものが最初に戻る
有効な再帰関数は、次の2つの重要な要素を含む必要があります：
| 要素 | 意味 | 例（階乗） |
|---|---|---|
| ベース条件 | 再帰を終了させる条件で、無限再帰を防ぐ | if (n == 0) return 1; |
| 再帰条件 | 問題をより小さな部分問題に分解し、自身を呼び出す | return n * factorial(n-1); |
古典的再帰問題
階乗
例
#include <stdio.h>
/* 階乗の再帰実装
n! = n × (n-1)!、ベース条件: 0! = 1 */
long long factorial(int n) {
if (n == 0) return 1; /* ベース条件 */
return n * factorial(n - 1); /* 再帰条件 */
}
int main() {
printf("5! = %lld\n", factorial(5)); /* 出力: 120 */
return 0;
}
/* 階乗の再帰実装
n! = n × (n-1)!、ベース条件: 0! = 1 */
long long factorial(int n) {
if (n == 0) return 1; /* ベース条件 */
return n * factorial(n - 1); /* 再帰条件 */
}
int main() {
printf("5! = %lld\n", factorial(5)); /* 出力: 120 */
return 0;
}
フィボナッチ数列
例
#include <stdio.h>
/* 素朴な再帰：大量の重複計算、O(2ⁿ) */
int fib(int n) {
if (n <= 1) return n; /* ベース条件 */
return fib(n-1) + fib(n-2); /* 再帰条件 */
}
/* メモ化最適化：計算済みの結果をキャッシュ、O(n) */
#define MAX 100
long long memo[MAX] = {0};
long long fibMemo(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n]; /* 計算済みなら直接返す */
memo[n] = fibMemo(n-1) + fibMemo(n-2);
return memo[n];
}
int main() {
printf("fib(10) (素朴): %d\n", fib(10)); /* 出力: 55 */
printf("fibMemo(50) (メモ化): %lld\n", fibMemo(50)); /* 出力: 12586269025 */
return 0;
}
/* 素朴な再帰：大量の重複計算、O(2ⁿ) */
int fib(int n) {
if (n <= 1) return n; /* ベース条件 */
return fib(n-1) + fib(n-2); /* 再帰条件 */
}
/* メモ化最適化：計算済みの結果をキャッシュ、O(n) */
#define MAX 100
long long memo[MAX] = {0};
long long fibMemo(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n]; /* 計算済みなら直接返す */
memo[n] = fibMemo(n-1) + fibMemo(n-2);
return memo[n];
}
int main() {
printf("fib(10) (素朴): %d\n", fib(10)); /* 出力: 55 */
printf("fibMemo(50) (メモ化): %lld\n", fibMemo(50)); /* 出力: 12586269025 */
return 0;
}
ハノイの塔問題
例
#include <stdio.h>
/* ハノイの塔の再帰的解法
n 枚の円盤を src から aux を利用して dst へ移動
手順：n-1 枚を src→aux、最大を src→dst、n-1 枚を aux→dst */
void hanoi(int n, char src, char aux, char dst) {
if (n == 1) {
printf("円盤 1 を %c から %c へ移動\n", src, dst);
return;
}
hanoi(n - 1, src, dst, aux); /* n-1 枚を src から aux へ移動 */
printf("円盤 %d を %c から %c へ移動\n", n, src, dst);
hanoi(n - 1, aux, src, dst); /* n-1 枚を aux から dst へ移動 */
}
int main() {
printf("ハノイの塔 (3 枚の円盤):\n");
hanoi(3, 'A', 'B', 'C');
/* 出力: 合計 7 手 (2³-1)、最小手数 = 2ⁿ-1 */
return 0;
}
/* ハノイの塔の再帰的解法
n 枚の円盤を src から aux を利用して dst へ移動
手順：n-1 枚を src→aux、最大を src→dst、n-1 枚を aux→dst */
void hanoi(int n, char src, char aux, char dst) {
if (n == 1) {
printf("円盤 1 を %c から %c へ移動\n", src, dst);
return;
}
hanoi(n - 1, src, dst, aux); /* n-1 枚を src から aux へ移動 */
printf("円盤 %d を %c から %c へ移動\n", n, src, dst);
hanoi(n - 1, aux, src, dst); /* n-1 枚を aux から dst へ移動 */
}
int main() {
printf("ハノイの塔 (3 枚の円盤):\n");
hanoi(3, 'A', 'B', 'C');
/* 出力: 合計 7 手 (2³-1)、最小手数 = 2ⁿ-1 */
return 0;
}
再帰と反復の比較
| 観点 | 再帰 | 反復 |
|---|---|---|
| コードの可読性 | 高（数学的な定義に近い） | 再帰ほど直感的でない場合がある |
| 実行効率 | 低い（スタックフレームのオーバーヘッド） | 高い |
| 空間オーバーヘッド | O(再帰の深さ) のスタック領域 | O(1) |
| スタックオーバーフローのリスク | 有（深さが大きすぎる場合） | 无 |
| 適した構造 | 木、グラフなどの自然な再帰構造 | 配列などの線形構造 |
その他の拡張末尾再帰特殊な形式の再帰で、再帰呼び出しが関数本体で実行される最後の操作となるものです。一部のコンパイラは末尾再帰を最適化し、等価な反復に変換してスタック領域を節約できます。ただし、すべてのCコンパイラがこの最適化をデフォルトで有効にしているわけではありません。