JavaScript | 再帰的なアルゴリズムの実例集

JavaScript

2026.07.17

再帰アルゴリズムとは何か（やさしい入口）
JavaScriptで見る最も基本的な再帰：カウントダウン
1. カウントダウンの流れをかみ砕いて理解する
再帰でよく出てくる「階乗」の例（n!）
1. 階乗の再帰を式で理解する
再帰の裏側で起きていること：コールスタック
1. コールスタックとエラー（初心者がつまずきやすいポイント）
再帰とループの違いをイメージする
もう一つの代表例：フィボナッチ数列（ただし注意付き）
1. なぜフィボナッチは「注意付き」なのか
再帰が活きる現実的な場面への橋渡し

再帰アルゴリズムとは何か（やさしい入口）

「再帰（さいき）」という言葉は少し難しく聞こえますが、アイデア自体はシンプルです。再帰とは「関数が自分自身を呼び出すこと」です。

JavaScriptでは、ある処理を「同じ形の小さな問題」に分解していき、その小さな問題を解くために同じ関数をもう一度呼び出す――これが再帰的アルゴリズムの基本的な考え方です。

ここで重要なのは次の2点です。

「いつまで自分を呼び出し続けるのか」という終了条件（＝ベースケース）を必ず用意すること
「少しだけ小さくした問題」を自分自身に渡して呼び出すこと

この2つがそろっていないと、再帰は無限ループのように止まらなくなり、プログラムがフリーズしたりエラーになったりします。

JavaScriptで見る最も基本的な再帰：カウントダウン

まずは、初心者向けに「カウントダウン」を再帰で書いてみます。 0になるまで数字を表示していくシンプルな例です。

function countdown(n) {
  console.log(n);

  if (n === 0) {
    // ここが「ベースケース」：これ以上は自分を呼び出さない
    return;
  }

  // 問題を少しだけ小さくして、もう一度自分を呼び出す
  countdown(n - 1);
}

countdown(5);

function countdown(n) {
  console.log(n);

  if (n === 0) {
    // ここが「ベースケース」：これ以上は自分を呼び出さない
    return;
  }

  // 問題を少しだけ小さくして、もう一度自分を呼び出す
  countdown(n - 1);
}

countdown(5);

JavaScript

このコードを実行すると、コンソールには

と表示されます。

カウントダウンの流れをかみ砕いて理解する

この関数の動きを、初心者向けに一歩ずつ追いかけてみます。

1回目の呼び出し countdown(5) 関数の中で console.log(5) が実行されます。 n === 0 ではないので、countdown(4) が呼び出されます。

2回目の呼び出し countdown(4) 同じように console.log(4) が実行され、また countdown(3) が呼び出されます。

この流れが n === 0 になるまで続き、最後に countdown(0) が呼び出されたとき、 if (n === 0) の条件が真になり、return; で再帰が終了します。

ここで重要なのは、毎回「問題を少しだけ小さくしている」という点です。 n を 1ずつ減らしていくことで、いつか必ず 0 に到達し、そこで再帰が止まるようになっています。

再帰でよく出てくる「階乗」の例（n!）

再帰アルゴリズムの入門で、ほぼ必ず登場するのが「階乗（かいじょう）」です。階乗とは、次のような計算です。

3の階乗： $3! = 3 \times 2 \times 1 = 6$
5の階乗： $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$

これを再帰で書くと、とても「再帰らしい」形になります。

function factorial(n) {
  if (n === 0) {
    // ベースケース：0! は 1 と定義されている
    return 1;
  }

  // 再帰ステップ：n! = n * (n - 1)!
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

function factorial(n) {
  if (n === 0) {
    // ベースケース：0! は 1 と定義されている
    return 1;
  }

  // 再帰ステップ：n! = n * (n - 1)!
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

JavaScript

階乗の再帰を式で理解する

階乗の再帰は、次のような「数学の式」とほぼ同じ形です。

ベースケース $0! = 1$
再帰ステップ $n! = n \times (n - 1)!$

JavaScriptのコードにそのまま対応させると、こうなります。

if (n === 0) return 1; → 「0! は 1」というベースケース
return n * factorial(n - 1); → 「n! は n × (n – 1)!」という再帰ステップ

このように、再帰は「同じ形の式」をプログラムに落とし込むのに向いています。数学が少し苦手でも、「自分自身を呼び出している」「少し小さい問題にしている」という視点で見ると理解しやすくなります。

再帰の裏側で起きていること：コールスタック

再帰を本当に理解するためには、「関数呼び出しの積み重ね」をイメージできると強いです。 JavaScriptエンジンは、関数を呼び出すたびに「コールスタック」という仕組みに情報を積み上げていきます。

factorial(3) を例に、何が起きているかをイメージしてみましょう。

factorial(3)
  → 3 * factorial(2)
      → 2 * factorial(1)
          → 1 * factorial(0)
              → 1  // ここがベースケース

factorial(3)
  → 3 * factorial(2)
      → 2 * factorial(1)
          → 1 * factorial(0)
              → 1  // ここがベースケース

JavaScript

一番下の factorial(0) が 1 を返し、その値を使って 1 * 1、2 * 1、3 * 2 と、上に向かって計算結果が戻っていきます。

この「下まで潜ってから、上に戻りながら計算する」という流れが、再帰のとても重要な特徴です。

コールスタックとエラー（初心者がつまずきやすいポイント）

ベースケースを忘れたり、条件を間違えたりすると、関数が永遠に自分自身を呼び出し続けてしまいます。

例えば、次のようなコードは危険です。

function badRecursion(n) {
  console.log(n);
  // ベースケースがない、または到達できない条件になっている
  badRecursion(n + 1);
}

badRecursion(1);

function badRecursion(n) {
  console.log(n);
  // ベースケースがない、または到達できない条件になっている
  badRecursion(n + 1);
}

badRecursion(1);

JavaScript

このコードは n を増やし続けるだけで、「いつ終わるか」が決まっていません。結果として、コールスタックが限界を超えたところで

RangeError: Maximum call stack size exceeded

のようなエラーが発生します。

初心者向けに強調しておきたいのは、再帰を書くときは必ず次の2つをセットで考えることです。

「どこで終わるか」＝ベースケース
「どうやって終わりに近づくか」＝問題を小さくするステップ

この2つがそろっていれば、コールスタックのエラーは基本的に防げます。

再帰とループの違いをイメージする

再帰は「自分自身を呼び出す」テクニックですが、多くの場合、for や while といったループでも同じことができます。

例えば、先ほどのカウントダウンをループで書くとこうなります。

function countdownLoop(n) {
  for (let i = n; i >= 0; i--) {
    console.log(i);
  }
}

countdownLoop(5);

function countdownLoop(n) {
  for (let i = n; i >= 0; i--) {
    console.log(i);
  }
}

countdownLoop(5);

JavaScript

やっていることはほぼ同じですが、書き方のスタイルが違います。

再帰の強みは、次のような場面で特に発揮されます。

入れ子構造（ツリー、フォルダ階層、DOMツリーなど）をたどるとき
問題を「同じ形の小さな問題」に分解しやすいとき
数学的な定義が再帰的になっているとき（階乗、フィボナッチ数列など）

一方で、単純なカウントや繰り返しだけなら、ループの方が読みやすく、パフォーマンス的にも有利なことが多いです。

もう一つの代表例：フィボナッチ数列（ただし注意付き）

再帰の例としてよく紹介されるのが「フィボナッチ数列」です。フィボナッチ数列は次のように定義されます。

最初の2つの値 $F (0) = 0$ , $F (1) = 1$
それ以降 $F (n) = F (n - 1) + F (n - 2)$

これをそのまま再帰で書くと、次のようになります。

function fibonacci(n) {
  if (n === 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }

  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(10)); // 55

function fibonacci(n) {
  if (n === 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }

  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(10)); // 55