JavaScript | アルゴリズムと再帰関数 (recursive function)

前半：アルゴリズムと再帰関数の「土台」を固める

JavaScriptでアルゴリズムや再帰を学ぶのは、かなり良い選択です。
ブラウザでもNode.jsでもすぐ試せるし、エラーもその場で見えるので「手を動かして覚える」に向いています。
ここではまず、「アルゴリズムってそもそも何？」「再帰関数って何者？」というところから、ゆっくり土台を作っていきます。

アルゴリズムとは何か

アルゴリズムを日常の言葉にすると

アルゴリズムは「問題を解くための手順書」です。
もっとくだけた言い方をすると、「こうすれば必ずゴールにたどり着ける、ステップの並び」です。

たとえば「カップラーメンを作るアルゴリズム」を書くとしたら、こんな感じになります。

お湯を沸かす
フタを開けて、かやくを入れる
お湯を線まで注ぐ
3分待つ
フタを開けて、よく混ぜる

これをプログラムの世界に持ってきたものが「アルゴリズム」です。
違いは、「人間が読むか」「コンピュータが実行するか」だけです。

なぜアルゴリズムがそんなに大事なのか

プログラミングは「文法を覚えたら終わり」ではありません。
文法は「言語」、アルゴリズムは「考え方」です。

同じ問題を解くにしても、

時間がかかりすぎて現実的に使えないコード
メモリを食いすぎて落ちるコード
入力次第で止まらなくなる危険なコード

こういうものは、文法的に正しくても「使えない」し、ときにはセキュリティ上のリスクにもなります。
アルゴリズムを学ぶというのは、「正しく・速く・安全に」問題を解くための思考を鍛えることです。

再帰関数とは何か（JavaScript版）

一言でいうと「自分自身を呼ぶ関数」

再帰関数（recursive function）は、「自分の中で自分自身を呼び出す関数」です。

JavaScriptでの形は、だいたいこんな感じになります。

function foo(n) {
  // 何か処理
  foo(n - 1);  // 自分自身を呼んでいる
}

function foo(n) {
  // 何か処理
  foo(n - 1);  // 自分自身を呼んでいる
}

これだけ見ると「え、これ無限ループじゃない？」と感じると思います。
その感覚は正しいです。
だからこそ、再帰には必ず「終わりを決める仕組み」が必要になります。

再帰関数の2本柱：ベースケースと再帰ステップ

再帰関数は、次の2つがセットになって初めて「まともに動く」ようになります。

ベースケース（基底条件）
再帰ステップ

この2つをJavaScriptのコードで見ていきます。

JavaScriptで見る、いちばんやさしい再帰：カウントダウン

カウントダウンを再帰で書いてみる

まずは「n から 1 までカウントダウンして表示する」関数を、再帰で書いてみます。

function countdown(n) {
  if (n <= 0) {              // ① ベースケース（終わりの条件）
    console.log("終了");
    return;
  }

  console.log(n);            // ② 今の仕事
  countdown(n - 1);          // ③ 問題を少し小さくして、自分自身を呼ぶ
}

countdown(3);

function countdown(n) {
  if (n <= 0) {              // ① ベースケース（終わりの条件）
    console.log("終了");
    return;
  }

  console.log(n);            // ② 今の仕事
  countdown(n - 1);          // ③ 問題を少し小さくして、自分自身を呼ぶ
}

countdown(3);

このコードを実行すると、コンソールには次のように表示されます。

3
2
1
終了

ここから、重要な部分をじっくり分解していきます。

ベースケースを深掘りする

if (n <= 0) { ... return; }
ここがベースケースです。

意味としては、「n が 0 以下になったら、もうこれ以上自分を呼ばずに終わる」という宣言です。
もしこの条件がなかったら、countdown は永遠に countdown(n - 1) を呼び続けます。

n が 3 → 2 → 1 → 0 → -1 → -2 → …
と、どこまでも減り続けて、最終的には「Maximum call stack size exceeded」というエラー（スタックオーバーフロー）になります。

セキュリティ・安全性の観点から言うと、「必ず終わる条件を入れる」は再帰の絶対ルールです。
ここを雑にすると、「特定の入力を与えるとサーバーが落ちる」みたいな脆弱なコードが生まれます。

再帰ステップを深掘りする

countdown(n - 1);
ここが再帰ステップです。

やっていることはシンプルで、「今の n を1つ減らして、残りの仕事を未来の自分に任せる」という動きです。

countdown(3) は「3を表示して、あとは countdown(2) に任せる」
countdown(2) は「2を表示して、あとは countdown(1) に任せる」
countdown(1) は「1を表示して、あとは countdown(0) に任せる」

そして countdown(0) でベースケースに到達し、「終了」と表示して終わります。

ここで大事なのは、「自分で全部やろうとしない」ことです。
再帰では、「自分は一歩だけ進めて、残りは再帰呼び出しに任せる」という考え方をします。

裏側で何が起きているか：コールスタック

JavaScriptエンジンの視点で見る再帰

JavaScriptエンジン（V8 など）は、関数を呼び出すたびに「どこから呼ばれたか」「そのときの変数の値は何か」といった情報をスタックに積み上げていきます。
これを「コールスタック」と呼びます。

countdown(3) の流れを、コールスタックのイメージで追ってみます。

最初に countdown(3) が呼ばれる
その中で countdown(2) が呼ばれる
その中で countdown(1) が呼ばれる
その中で countdown(0) が呼ばれる

このとき、スタックには

countdown(3)
countdown(2)
countdown(1)
countdown(0)

という感じで「呼び出しの履歴」が積み上がっています。

countdown(0) がベースケースで return すると、一番上の countdown(0) がスタックから消えます。
次に countdown(1) に戻り、そこも処理が終わるとスタックから消え…というふうに、一段ずつ戻っていきます。

スタックオーバーフローとセキュリティ

コールスタックには上限があります。
再帰が深くなりすぎると、「Maximum call stack size exceeded」というエラーになります。

これはJavaScriptでは単なる実行時エラーですが、低レイヤーの世界ではスタックオーバーフローは古典的な攻撃手法の一つです。
もちろん、JavaScript単体で同じような攻撃を仕掛けるのは難しいですが、「スタックを無限に積み上げるコードは危険」という感覚は、セキュリティエンジニアとしても重要な感性です。

アルゴリズムと再帰の関係

再帰は「アルゴリズムの表現方法」の一つ

アルゴリズムは「問題を解く手順」でした。
その手順をコードに落とし込むときに、

ループ（for, while）で書く
再帰で書く

という2つの大きなスタイルがあります。

たとえば「1 から n までの合計を求める」というアルゴリズムを考えてみます。

ループで書くとこうなります。

function sumLoop(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

function sumLoop(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

同じことを再帰で書くと、こうなります。

function sumRecursive(n) {
  if (n === 0) {          // ベースケース
    return 0;
  }
  return n + sumRecursive(n - 1);   // 再帰ステップ
}

function sumRecursive(n) {
  if (n === 0) {          // ベースケース
    return 0;
  }
  return n + sumRecursive(n - 1);   // 再帰ステップ
}

どちらも「1 から n までの合計を求める」という同じアルゴリズムを実現しています。
ただ、表現の仕方が違うだけです。

再帰が特に強い場面

再帰が本領を発揮するのは、「入れ子構造」や「木構造」を扱うときです。

フォルダの中にフォルダがあって、その中にまたフォルダがあって…
HTMLのDOMツリーのように、要素の中に子要素があって、その中にまた子要素があって…

こういう「自分と同じ形のものが中に入っている」構造は、再帰と相性が抜群です。
JavaScriptだと、DOM操作やツリー状のデータ構造を扱うときに、再帰がよく登場します。

JavaScriptらしい再帰の例：配列をなめる

配列の合計を再帰で書く

JavaScriptでは配列を扱うことが多いので、配列を題材にした再帰を一つ見ておきましょう。

function sumArray(arr, index = 0) {
  if (index === arr.length) {   // ベースケース：末尾まで来たら0
    return 0;
  }

  return arr[index] + sumArray(arr, index + 1);  // 今の要素 + 残りの合計
}

console.log(sumArray([1, 2, 3, 4]));  // 10

function sumArray(arr, index = 0) {
  if (index === arr.length) {   // ベースケース：末尾まで来たら0
    return 0;
  }

  return arr[index] + sumArray(arr, index + 1);  // 今の要素 + 残りの合計
}

console.log(sumArray([1, 2, 3, 4]));  // 10

ここでやっていることはシンプルです。

配列の末尾まで来たら、合計は 0 とみなす（ベースケース）
そうでなければ、「今の要素」＋「残りの要素の合計」（再帰ステップ）

この「今の1つ＋残りを再帰に任せる」というパターンは、配列・文字列・ツリーなど、いろいろな場面で使える再帰の基本形です。

なぜ index を使うのか

よくある別パターンとして、こう書くこともできます。

function sumArraySlice(arr) {
  if (arr.length === 0) {
    return 0;
  }

  return arr[0] + sumArraySlice(arr.slice(1));
}

function sumArraySlice(arr) {
  if (arr.length === 0) {
    return 0;
  }

  return arr[0] + sumArraySlice(arr.slice(1));
}

これはこれで分かりやすいのですが、arr.slice(1) が毎回「新しい配列」を作るので、要素数が多いとメモリと時間を余計に使います。

セキュリティ・パフォーマンスの観点から言うと、「無駄なコピーを増やさない」ことはとても大事です。
だから、実務寄りに書くなら index を渡すスタイルの方が健全です。

前半のまとめと後半への予告

ここまでの前半で、次の土台を固めました。

アルゴリズムは「問題を解くための手順書」であり、文法とは別に鍛えるべき「考え方」であること
再帰関数は「自分自身を呼び出す関数」だが、本質は「大きな問題を同じ形の小さな問題に分解する」こと
再帰には必ず「ベースケース」と「再帰ステップ」の2本柱が必要で、これを間違えるとスタックオーバーフローや停止しないコードになること
JavaScriptでは、コールスタックという仕組みの上で再帰が動いており、深くなりすぎると Maximum call stack size exceeded になること
カウントダウンや配列の合計など、シンプルな例で再帰の流れと「今の1歩＋残りを任せる」という感覚をつかんだこと

後半では、もう少しアルゴリズム寄りに踏み込みます。

階乗・フィボナッチ数列などの典型的な再帰アルゴリズム
木構造・ネストしたオブジェクトを再帰でたどるイメージ
再帰とループのどちらを選ぶべきか、パフォーマンスとセキュリティの観点
再帰を書くときの「思考の型」と、よくある落とし穴