後半：アルゴリズムとしての再帰を「使いこなす」編
前半で「再帰の感覚」と「JavaScriptでの基本形」はつかめてきたと思う。
後半は、もう少しアルゴリズム寄りに踏み込んで、「どんな問題をどう分解すれば再帰で書けるのか」「どこで再帰を選ぶべきか」を一緒に整理していこう。
階乗（factorial）で再帰の型を固める
階乗の定義と再帰のつながり
階乗は、数学では次のように定義される。
0! は 1
n! は n × (n-1)!（n > 0 のとき）
この「自分自身を使って自分を定義している」形が、そのまま再帰関数の形になる。
再帰がきれいにハマる典型例だ。
JavaScriptで書く階乗の再帰
function factorial(n) {
if (n === 0) { // ベースケース
return 1;
}
return n * factorial(n - 1); // 再帰ステップ
}
console.log(factorial(5)); // 120
ここで重要なのは、ベースケースと再帰ステップが「数学の定義」と一対一で対応していること。
0! を 1 と決めるのがベースケースで、n! を n × (n-1)! と書くのが再帰ステップになっている。
この感覚が身につくと、「数学の再帰的な定義を見たら、そのままコードに写せる」ようになる。
アルゴリズムの本や競技プログラミングの世界では、こういう定義が頻繁に出てくるので、かなり強い武器になる。
フィボナッチ数列と「やりすぎ再帰」の罠
フィボナッチ数列の再帰定義
フィボナッチ数列は次のように定義される。
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)（n ≥ 2）
これも、定義そのものが再帰になっているパターンだ。
JavaScriptでの素直な再帰実装
function fib(n) {
if (n === 0) { // ベースケース1
return 0;
}
if (n === 1) { // ベースケース2
return 1;
}
return fib(n - 1) + fib(n - 2); // 再帰ステップ
}
console.log(fib(6)); // 8
見た目はとても美しい。
定義とコードがほぼ同じで、「アルゴリズムをそのまま書いた」感じがする。
パフォーマンスを深掘りする
ここが重要ポイントだ。
この実装は、n が大きくなると一気に遅くなる。
理由は、「同じ値を何度も何度も計算している」から。
例えば fib(6) を計算するとき、fib(5) と fib(4) を呼ぶ。
fib(5) は fib(4) と fib(3) を呼ぶ。
すると fib(4) が何度も呼ばれ、fib(3) も何度も呼ばれ…という具合に、呼び出し回数が爆発していく。
アルゴリズム的に言うと、時間計算量が指数関数的に増える。
セキュリティ・運用の視点から見ると、「ちょっと大きな入力を与えただけでCPUを食い尽くす」ようなコードは、サービス妨害（DoS）的な弱点になり得る。
ここで学んでほしいのは、「再帰が書ける＝良いアルゴリズム」ではない、ということ。
再帰は表現方法であって、「速さ」「メモリ」「安全性」は別軸でちゃんと考える必要がある。
ネスト構造・木構造と再帰：JavaScriptらしい本番の出番
ネストしたオブジェクトをたどる再帰
JavaScriptでは、オブジェクトや配列が入れ子になったデータを扱うことが多い。
例えば、次のような構造を考えてみる。
const data = {
name: "root",
children: [
{ name: "child1", children: [] },
{
name: "child2",
children: [
{ name: "grandchild1", children: [] }
]
}
]
};
これは「木構造」と呼ばれる形で、フォルダ階層やDOMツリーと同じような構造だ。
この全てのノードの name を表示したいとする。
再帰で木構造をたどる関数
function traverse(node) {
console.log(node.name); // 今のノードの仕事
if (!node.children || node.children.length === 0) { // ベースケースに近い条件
return;
}
for (const child of node.children) {
traverse(child); // 子ノードに対して同じ処理を再帰的に行う
}
}
traverse(data);
ここでのポイントは、「1つのノードに対してやること」がとてもシンプルなこと。
自分の name を表示する
子どもたちに対して「同じことをやって」と頼む
この「自分の仕事をして、子に同じことをさせる」というパターンは、木構造・DOM・フォルダ階層など、現場でめちゃくちゃよく出てくる。
DOMツリーに置き換えてイメージする
ブラウザの世界で考えると、document.body を根として、全ての要素のタグ名を表示するような処理も、ほぼ同じ形で書ける。
function traverseDom(node) {
console.log(node.tagName);
for (const child of node.children) {
traverseDom(child);
}
}
// ブラウザのコンソールで
traverseDom(document.body);
DOMはまさに木構造なので、再帰との相性が抜群だ。
JavaScriptでフロントエンドをやるなら、この感覚は早めに体に入れておくとかなり楽になる。
再帰とループ、どちらを選ぶべきか
思考としての再帰、実装としてのループ
実務寄りの話をすると、「頭の中では再帰で考えて、コードとしてはループで書く」ことがよくある。
理由はシンプルで、ループの方が
スタックオーバーフローの心配がない
パフォーマンスが安定しやすい
JavaScriptエンジンの最適化が効きやすい
といったメリットがあるからだ。
ただし、木構造や再帰的な定義をそのまま表現したいときは、再帰の方が圧倒的に読みやすいことも多い。
「読みやすさ」と「安全性・速さ」のバランスをどう取るかが、プロの判断ポイントになる。
セキュリティ・パフォーマンスの観点からの指針
入力サイズがどこまで大きくなり得るか
最悪ケースで再帰の深さはどれくらいか
同じ計算を何度も繰り返していないか
このあたりをざっくりでもいいので意識しておくと、「とりあえず動く」から一歩抜け出せる。
特に、ユーザー入力や外部データをそのまま再帰の深さに反映させるようなコードは、慎重に設計した方がいい。
再帰を書くときの「思考の型」
型1：先にベースケースを決める
再帰を書くときは、まず「どんな状態になったら、もう再帰をやめていいか」を決める。
ここを先に決めることで、「必ず終わる」ことが保証される。
n が 0 になったら終わり
配列の末尾まで来たら終わり
子どもがいないノードまで来たら終わり
この「終点」を先に決める癖は、バグ防止にもセキュリティにも効く。
型2：問題を「一歩だけ」小さくする
次に、「今の問題を一歩だけ小さくする」ことを考える。
n! を「n × (n-1)!」にする
配列全体の合計を「先頭＋残りの合計」にする
木全体の処理を「今のノード＋子ノードの処理」にする
ここで大事なのは、「自分で全部やろうとしない」こと。
自分は一歩だけ進めて、残りは再帰呼び出しに任せる、というマインドセットが再帰のコアだ。
型3：スタックの深さと計算量をざっくり見積もる
最後に、「この再帰はどれくらい深くなるか」「呼び出し回数はどれくらいか」をざっくりでいいのでイメージする。
深さが n で、呼び出し回数もだいたい n なら、まだわかりやすい。
フィボナッチのように、呼び出し回数が指数関数的に増えるものは要注意だ。
この「最悪ケースをざっくり想像する」癖は、アルゴリズム設計とセキュリティ設計の両方で効いてくる。
手を動かすための小さな課題
課題1：配列の最大値を再帰で求める
ヒントはこうだ。
要素が1つだけの配列なら、その要素が最大
そうでなければ、「先頭」と「残りの最大値」を比べる
これを JavaScript で関数にしてみてほしい。
課題2：文字列の長さを再帰で求める
str.length を使わずに、再帰だけで文字列の長さを求める関数を書いてみる。
空文字列なら長さは 0
そうでなければ、「1 ＋ 残りの長さ」
という分解で考えると、きれいに書ける。
まとめ：再帰は「問題分解の筋トレ」
ここまでで、JavaScriptにおけるアルゴリズムと再帰関数を、かなり深めに見てきた。
再帰は「自分自身を呼ぶ関数」だけど、本質は「大きな問題を同じ形の小さな問題に分解する技術」
ベースケースと再帰ステップを先に設計することで、「必ず終わる」「読みやすい」再帰になる
階乗・フィボナッチ・木構造・配列処理など、典型パターンを通して再帰の型を体に入れられる
再帰は美しいが、スタックの深さや計算量、データコピーのコストには常に注意が必要
アルゴリズムとセキュリティの両方の視点から、「速くて安全な再帰」を意識できると、一気にプロ寄りの思考になる
