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

それでは「再帰を使った探索アルゴリズム」を図解で追ってみましょう。ここでは分かりやすい例として 迷路探索（深さ優先探索） を取り上げます。

問題設定

• 迷路を2次元配列で表す
• 0 = 通れる道
• 1 = 壁
• S = スタート
• G = ゴール

例：

S 0 1
1 0 0
1 1 G

再帰的な探索の考え方

1. 現在地がゴールなら成功
2. 壁や範囲外なら失敗
3. 上下左右に1歩進んで再帰的に探索
4. どこかで成功したら true を返す

コード例（イメージ）

function searchMaze(maze, x, y) {
  // 範囲外や壁なら失敗
  if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length) return false;
  if (maze[x][y] === 1) return false;

  // ゴールなら成功
  if (maze[x][y] === "G") return true;

  // 通った場所を「壁」にして再訪を防ぐ
  maze[x][y] = 1;

  // 上下左右を探索
  return searchMaze(maze, x+1, y) ||
         searchMaze(maze, x-1, y) ||
         searchMaze(maze, x, y+1) ||
         searchMaze(maze, x, y-1);
}

function searchMaze(maze, x, y) {
  // 範囲外や壁なら失敗
  if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length) return false;
  if (maze[x][y] === 1) return false;

  // ゴールなら成功
  if (maze[x][y] === "G") return true;

  // 通った場所を「壁」にして再訪を防ぐ
  maze[x][y] = 1;

  // 上下左右を探索
  return searchMaze(maze, x+1, y) ||
         searchMaze(maze, x-1, y) ||
         searchMaze(maze, x, y+1) ||
         searchMaze(maze, x, y-1);
}

実行の流れ（図解）

スタート S から探索を始めると：

S → 右へ進む → 下へ進む → ゴールGに到達！

再帰の動きはこうなります：

1. searchMaze(S)
   → ゴールじゃないので上下左右を試す
2. 右に進む → searchMaze(0,1)
   → さらに下に進む → searchMaze(1,1)
   → さらに右に進む → searchMaze(1,2)
   → 下に進む → searchMaze(2,2) = ゴール！

ポイント

• 再帰は「分岐がある探索」に強い
• ループで書くと「スタック」や「キュー」を自分で管理する必要があるが、再帰なら「関数呼び出しの積み重ね」がそのまま探索の流れになる
• 木構造や迷路探索など「どんどん潜っていって、戻りながら答えを探す」処理に最適

👉 ここまでで「再帰の基礎 → 配列処理 → ネスト構造 → 探索アルゴリズム」とステップアップしてきました。