再帰（さいき）を初心者向けにやさしく、例題たっぷりで詳しく説明します。コードは JavaScript で書きます。実行しながら理解すると早いので、ブラウザのコンソールや Node.js で試してみてください。
再帰とは？
再帰は「関数の中で自分自身を呼び出す」テクニックです。繰り返し（ループ）と似ていますが、「問題を小さな同じ形の問題に分けて解く」アプローチです。
重要なポイントは次の2つ：
- 終了条件（ベースケース）：いつ再帰を止めるかを必ず決める。
- 縮小・更新：再帰呼び出しごとに問題が小さくなる（引数を変えるなど）ようにする。
これがないと無限ループ（スタックオーバーフロー）になります。
例1：カウントダウン（超シンプル）
再帰の考え方を最も分かりやすく示す例です。
function countdown(n) {
if (n <= 0) {
console.log("終わり！");
return;
}
console.log(n);
countdown(n - 1); // 自分自身を呼ぶ（n が小さくなる）
}
countdown(3);
// 出力:
// 3
// 2
// 1
// 終わり！
流れ（追いかけ方）
countdown(3)→console.log(3)→countdown(2)countdown(2)→console.log(2)→countdown(1)countdown(1)→console.log(1)→countdown(0)countdown(0)→ 終了条件でreturn
例2：階乗（factorial） — 再帰の古典
数学的に定義された問題を再帰で書くと非常に自然です。
function factorial(n) {
if (n === 0) return 1; // ベースケース
return n * factorial(n - 1);
}
console.log(factorial(5)); // 120
なぜ動くか（考え方）
factorial(5)は5 * factorial(4)によって定義される。factorial(0)が 1 を返すことで計算が終わる。- 呼ばれた関数は戻り値を使って上へ戻り、最終結果を作る。
例3：フィボナッチ数列（注意点あり）
フィボナッチは再帰で簡単に書けますが、パフォーマンスに注意（指数時間になりやすい）です。
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
console.log(fib(6)); // 8
注意点
fib(6)はfib(5)とfib(4)を呼び、それぞれがまた複数回呼ばれる → 重複計算が多い。nが大きいと遅くなる（例：fib(40)はかなり時間がかかる）。- 対策：メモ化（結果を保存） や 反復（ループ） に置き換える。
メモ化の例：
function fibMemo(n, memo = {}) {
if (n in memo) return memo[n];
if (n <= 1) return n;
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
console.log(fibMemo(40)); // 高速に計算できる
例4：ツリー（フォルダ）を再帰で探索する
フォルダ構造やツリー構造の処理は再帰が得意です。次は簡単な木を辿る例（擬似データ）。
const tree = {
name: "root",
children: [
{ name: "a", children: [{name: "a1", children: []}] },
{ name: "b", children: [] }
]
};
function traverse(node) {
console.log(node.name);
for (const child of node.children) {
traverse(child);
}
}
traverse(tree);
// 出力: root, a, a1, b
ポイント
- 各ノードに対して自分と子ノードへの同じ処理（再帰）を行う。
- 基本的には「ノードが葉（children が空）」になればそれ以上呼ばない（暗黙のベースケース）。
再帰のトレース方法（デバッグのコツ）
- 小さな数で一度試して、
console.logで引数の変化を表示する。 - スタック（呼び出し順）を紙に書くと分かりやすい。
- ブラウザのデバッガでブレークポイントを使うと各呼び出しの変化が見える。
例（ログを詳しく出す）：
function trace(n) {
console.log("呼び出し: n =", n);
if (n <= 0) {
console.log("戻る: n =", n);
return;
}
trace(n - 1);
console.log("戻ってきた: n =", n);
}
trace(2);
出力：
呼び出し: n = 2
呼び出し: n = 1
呼び出し: n = 0
戻る: n = 0
戻ってきた: n = 1
戻ってきた: n = 2
再帰 vs ループ（どちらを使うべき？）
- 読む人が理解しやすい方 を選ぶのが第一。再帰は表現が簡潔になる場合が多い（ツリー探索など）。
- パフォーマンス：深い再帰はコールスタックを消費する。JSでは末尾呼び出し最適化（tail call optimization）が一般的に保証されていないため、深い再帰（例：数万回）は避けるかループに変える。
- 再帰が自然な問題（木構造、分割統治）では再帰を使う価値が大きい。
よくあるミス（初心者がハマるポイント）
- 終了条件を書き忘れる → 無限再帰でクラッシュ（StackOverflow）。
- 引数を正しく変えない → 終了条件に到達しない。
- 重複計算に注意（例：単純なフィボナッチ） → メモ化を検討。
- 深すぎる再帰 → スタックオーバーフロー。反復に切替え。
練習問題（手を動かそう）
sumTo(n)：1 から n までの合計を再帰で計算する関数を作れ。- 配列
arrの中の要素をすべて足す再帰関数を作れ（配列を半分に分ける方法など）。 - 二分探索の再帰版（ソート済み配列で値を探す）を書け。
解答例（問題1）
function sumTo(n) {
if (n <= 0) return 0;
return n + sumTo(n - 1);
}
console.log(sumTo(5)); // 15
まとめ（覚えておくこと）
- 再帰は「問題を同じ形の小さな問題に分ける」強力な手法。
- 必ず終了条件を明確に。
- 引数は毎回変化させ、終了条件に近づける。
- フィボナッチのような重複計算にはメモ化、深い再帰は反復に切替えを検討。
- 小さな例（階乗やカウントダウン）で動きを追ってみるのが理解への近道。