JavaScript | 「再帰関数」レベル別の練習問題

では、プログラミング初心者が段階的に「再帰関数」を理解できるように、レベル別の練習問題＋模範解答＋やさしい解説をまとめます。

レベル1：超入門（再帰の形を覚える）

🧩 問題1：カウントダウン

1から0までのカウントダウンを、再帰関数を使って表示してください。

✅ 解答例

function countdown(n) {
  if (n < 0) return; // 終了条件
  console.log(n);
  countdown(n - 1); // 自分を呼び出す（1ずつ減らす）
}

countdown(3);

function countdown(n) {
  if (n < 0) return; // 終了条件
  console.log(n);
  countdown(n - 1); // 自分を呼び出す（1ずつ減らす）
}

countdown(3);

💡 解説

• if (n < 0) が「終わりの条件」。
• countdown(n - 1) で少しずつ n を減らしていき、最終的に n = -1 で終了します。
• 再帰の基本形「ベースケース＋再帰呼び出し」が理解できればOK！

レベル2：計算に使う（値を返す）

🧩 問題2：1〜n の合計を求める

1からnまでの合計を、再帰で計算して返す関数を作ってください。
（例：sumTo(5) → 15）

✅ 解答例

function sumTo(n) {
  if (n === 0) return 0;     // 終了条件
  return n + sumTo(n - 1);   // 自分で計算 + 小さい問題を呼ぶ
}

console.log(sumTo(5)); // 15

function sumTo(n) {
  if (n === 0) return 0;     // 終了条件
  return n + sumTo(n - 1);   // 自分で計算 + 小さい問題を呼ぶ
}

console.log(sumTo(5)); // 15

💡 解説

• sumTo(5) は「5 + sumTo(4)」と考えます。
• sumTo(0) が 0 を返すので、最終的に「5+4+3+2+1+0」が計算されます。
• 「大きな問題を、小さな同じ形の問題に分けて解く」のが再帰の考え方です。

レベル3：定義型の再帰（数学的な例）

🧩 問題3：階乗（factorial）

n!（= n × (n-1) × (n-2) × … × 1）を再帰で求めましょう。

✅ 解答例

function factorial(n) {
  if (n === 0) return 1; // 0! は 1（数学の定義）
  return n * factorial(n - 1);
}

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

function factorial(n) {
  if (n === 0) return 1; // 0! は 1（数学の定義）
  return n * factorial(n - 1);
}

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

💡 解説

• 「n! = n × (n-1)!」という定義をそのままコードにしたものです。
• 終了条件（n==0）がないと無限ループになります。
• 再帰では、数学の定義をコードに“直訳”するイメージがわかりやすいです。

レベル4：分岐型の再帰

🧩 問題4：フィボナッチ数列

フィボナッチ数列は次のように定義されます。

F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)

これを再帰で求めましょう。

✅ 解答例

function fib(n) {
  if (n <= 1) return n; // 終了条件（0か1のとき）
  return fib(n - 1) + fib(n - 2);
}

console.log(fib(6)); // 8

function fib(n) {
  if (n <= 1) return n; // 終了条件（0か1のとき）
  return fib(n - 1) + fib(n - 2);
}

console.log(fib(6)); // 8

💡 解説

• fib(6) は「fib(5) + fib(4)」で定義されます。
• 再帰が「2方向」に分かれるタイプ。
• ただし、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)); // 高速で結果が出る

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)); // 高速で結果が出る

💡 memo（メモ）は、過去の結果を記録して使い回すしくみです。

レベル5：構造をたどる（ツリー探索）

🧩 問題5：フォルダの中身を全部表示

次のようなフォルダ構造（ツリー）を全部たどって、名前をすべて表示してください。

const folder = {
  name: "root",
  children: [
    { name: "docs", children: [{ name: "memo.txt", children: [] }] },
    { name: "images", children: [] }
  ]
};

const folder = {
  name: "root",
  children: [
    { name: "docs", children: [{ name: "memo.txt", children: [] }] },
    { name: "images", children: [] }
  ]
};

✅ 解答例

function showFolder(node) {
  console.log(node.name);
  for (const child of node.children) {
    showFolder(child); // 子要素を再帰的に処理
  }
}

showFolder(folder);

function showFolder(node) {
  console.log(node.name);
  for (const child of node.children) {
    showFolder(child); // 子要素を再帰的に処理
  }
}

showFolder(folder);

💡 解説

• 子があれば「自分と同じ処理」をもう一度行う（再帰）。
• 木構造やフォルダ階層のように、ネストが深いデータには再帰が最適。
• 終了条件は「子がないとき」なので明示しなくても止まります。

レベル6（チャレンジ）

🧩 問題6：配列の中の数をすべて足す

配列の中にさらに配列が入っているかもしれません（ネスト構造）。
すべての数を合計してください。

const arr = [1, [2, [3, 4]], 5]; // => 15

const arr = [1, [2, [3, 4]], 5]; // => 15

✅ 解答例

function deepSum(array) {
  let total = 0;
  for (const item of array) {
    if (Array.isArray(item)) {
      total += deepSum(item); // 配列なら再帰で足す
    } else {
      total += item; // 数値ならそのまま足す
    }
  }
  return total;
}

console.log(deepSum([1, [2, [3, 4]], 5])); // 15

function deepSum(array) {
  let total = 0;
  for (const item of array) {
    if (Array.isArray(item)) {
      total += deepSum(item); // 配列なら再帰で足す
    } else {
      total += item; // 数値ならそのまま足す
    }
  }
  return total;
}

console.log(deepSum([1, [2, [3, 4]], 5])); // 15

💡 解説

• 「配列の中に配列がある」＝階層構造 → 再帰の得意分野。
• ループ＋再帰の組み合わせで柔軟な処理ができる。

まとめ表

学びのステップ

1. まずは「呼び出し→終了条件→戻り値」の流れを理解する。
2. 小さい問題で練習（カウントダウン・合計・階乗）。
3. 構造をたどるタイプ（ツリー・配列）に進む。
4. メモ化や最適化を学ぶと応用力が一気に上がります。