在算法的世界里，递归与回溯算法是一对常常出现在解决组合问题、图算法以及迷宫问题中的强大工具。本文将结合深度优先搜索（Depth First Search, DFS）来解析回溯算法在解决迷宫问题中的应用。

递归的基本概念

递归是一种直接或间接调用自身的编程技术。它通常包含两个部分：

1. 递归条件：函数调用自身的条件，即问题被分解为子问题。
2. 递归终止条件：递归的终止条件，防止无限循环。

一个简单的递归例子是计算阶乘：

function factorial(n: number): number {
    if (n === 1) return 1; // 终止条件
    return n * factorial(n - 1); // 递归条件
}
console.log(factorial(5)); // 输出 120

在这里，递归函数 factorial 不断调用自身直到 n === 1，即递归终止条件满足。

回溯算法的基本思想

回溯算法是一种通过递归实现的试探性算法，用于解决满足约束条件的所有解或部分解问题。其基本思想是逐步探测解空间，并在探测过程中根据约束条件决定是否继续深入或回退，直至找到最终解。

其伪代码如下：

Backtrack(当前状态):
    if 当前状态是目标状态:
        输出解
        return
    for 每个可能的选择 in 当前状态的所有选择:
        做出选择
        if 选择合法:
            递归探索新的状态
        撤销选择

深度优先搜索与迷宫问题

迷宫问题可以用图来表示，其中每个点是一个位置，边表示可以到达的路径。深度优先搜索是一种典型的图遍历算法，用于在路径上探测可能的解。

迷宫问题描述

给定一个二维迷宫矩阵，其中 1 表示可以通过的路径，0 表示障碍物。起点位于左上角 (0,0)，终点位于右下角 (n-1,m-1)。要求找到一条从起点到终点的路径。

DFS 解决迷宫问题

DFS 遍历迷宫的过程是通过递归不断探索当前位置的上下左右四个方向。若当前位置可行，则标记为已访问，并继续递归寻找下一个可行位置；若当前路径走不通，则回溯至上一个位置。

type Maze = number[][];
type Position = [number, number];

function isSafe(maze: Maze, x: number, y: number, visited: boolean[][]): boolean {
    const n = maze.length;
    const m = maze[0].length;
    return x >= 0 && x < n && y >= 0 && y < m && maze[x][y] === 1 && !visited[x][y];
}

function dfs(maze: Maze, x: number, y: number, visited: boolean[][], path: Position[]): boolean {
    const n = maze.length;
    const m = maze[0].length;

    // 如果到达终点
    if (x === n - 1 && y === m - 1) {
        path.push([x, y]);
        return true;
    }

    // 标记当前点已访问
    visited[x][y] = true;
    path.push([x, y]);

    // 方向数组：上、右、下、左
    const directions: Position[] = [[-1, 0], [0, 1], [1, 0], [0, -1]];

    // 尝试所有方向
    for (const [dx, dy] of directions) {
        const newX = x + dx;
        const newY = y + dy;

        if (isSafe(maze, newX, newY, visited)) {
            if (dfs(maze, newX, newY, visited, path)) {
                return true;
            }
        }
    }

    // 回溯：撤销当前点
    path.pop();
    visited[x][y] = false;

    return false;
}

function solveMaze(maze: Maze): Position[] {
    const n = maze.length;
    const m = maze[0].length;
    const visited = Array.from({ length: n }, () => Array(m).fill(false));
    const path: Position[] = [];

    if (dfs(maze, 0, 0, visited, path)) {
        return path;
    }

    return []; // 无解
}

// 示例迷宫
const maze: Maze = [
    [1, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 1, 0, 0],
    [1, 1, 1, 1],
];

const solution = solveMaze(maze);

if (solution.length > 0) {
    console.log('路径: ', solution);
} else {
    console.log('无解');
}

代码解析

1. isSafe 函数：检查给定位置是否在迷宫范围内、是否是可通行的路径、且未被访问。
2. dfs 函数：递归探索迷宫。如果当前点 (x, y) 是终点，则成功找到一条路径。否则，继续探索相邻的四个方向。如果当前路径行不通，则回溯。
3. solveMaze 函数：初始化迷宫，并调用 DFS 开始搜索路径。

输出示例

给定迷宫为：

1 0 0 0
1 1 0 1
0 1 0 0
1 1 1 1

最终输出路径：

路径:  [[0, 0], [1, 0], [1, 1], [2, 1], [3, 1], [3, 2], [3, 3]]

回溯过程与状态撤销

在回溯算法中，递归过程就是不断尝试和探索的过程，而回溯的精髓在于状态的撤销。在迷宫问题中，如果某条路径无法继续，程序会回退到上一个可行的状态，尝试其他方向。因此，回溯算法通常需要在每次递归调用后进行状态恢复操作。

在代码中，我们通过 path.pop() 和 visited[x][y] = false 来实现状态的撤销。这保证了在其他路径探索时，当前点可以重新被访问。

递归深度与时间复杂度

深度优先搜索会尝试所有可能的路径，直到找到一条可行路径。因此，时间复杂度与迷宫的大小有关。在最坏情况下，时间复杂度为 O(N*M)，其中 N 和 M 是迷宫的宽度和高度。这是因为每个点都可能被访问一次。