JavaScript | 「再帰の動き」を図解で追う

では「再帰を使ったソートアルゴリズム」の代表例、クイックソートを図解で追ってみましょう。
これが分かると「再帰で問題を分割して解く」イメージが一気にクリアになります。

クイックソートの考え方

1. 配列から基準（ピボット）を1つ選ぶ
2. ピボットより小さい要素を左、大きい要素を右に分ける
3. 左と右の配列を再帰的にソートする
4. 「左 + ピボット + 右」をつなげて完成

コード例

function quickSort(arr) {
  if (arr.length <= 1) return arr; // 終了条件

  const pivot = arr[0]; // 基準
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([3, 7, 2, 5, 1]));
// [1, 2, 3, 5, 7]

function quickSort(arr) {
  if (arr.length <= 1) return arr; // 終了条件

  const pivot = arr[0]; // 基準
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([3, 7, 2, 5, 1]));
// [1, 2, 3, 5, 7]

実行の流れ（例: [3, 7, 2, 5, 1]）

1. ピボット = 3
   • 左 = [2, 1]
   • 右 = [7, 5]
     → quickSort([2,1]) と quickSort([7,5]) を呼ぶ
2. quickSort([2,1])
   • ピボット = 2
   • 左 = [1], 右 = []
   • → [1,2]
3. quickSort([7,5])
   • ピボット = 7
   • 左 = [5], 右 = []
   • → [5,7]
4. 戻りながら結合
   • [1,2] + [3] + [5,7] = [1,2,3,5,7]

図でイメージ

[3,7,2,5,1]
   pivot=3
   left=[2,1], right=[7,5]

   quickSort([2,1]) → [1,2]
   quickSort([7,5]) → [5,7]

   => [1,2] + [3] + [5,7]
   => [1,2,3,5,7]

ポイント

• 分割統治法の典型例：「大きな問題を小さな同じ形の問題に分ける」
• 再帰で「左」「右」をそれぞれソートして、最後に組み合わせる
• ループで書くとスタック管理が必要になるが、再帰なら自然に書ける

👉 ここまでで「探索」と「ソート」というアルゴリズムの2大応用を見ました。