Java 递归算法实战：迷宫、八皇后与汉诺塔详解

递归算法核心原理

递归是指方法在执行过程中调用自身的行为。这种结构能够显著简化复杂逻辑的代码编写，使程序结构更加清晰和易于理解，但代价是需要消耗更多的内存和时间来建立函数副本。相比迭代（循环结构），递归使用的是选择结构，其时间复杂度通常与递归调用的深度相关。

递归的执行过程分为两个阶段：

1. 调用阶段（递）：层层向下传递参数，直到达到基准条件（Base Case）。
2. 回退阶段（归）：满足基准条件后，按照调用顺序的逆序依次返回结果。

在处理大规模且不易直接求解的问题时，常结合分治法思想，将大问题拆解为若干个小模块逐一解决。

案例一：迷宫路径求解

该案例旨在通过递归回溯策略，在一个二维数组表示的迷宫中找到从起点到终点的路径。地图中 0 代表未走过，1 代表墙壁，2 代表通路，3 代表已走过但走不通的死胡同。

迷宫示意图：

第1步：初始化迷宫网格

创建一个指定行数和列数的二维数组，默认四周边界设为墙壁 1，内部初始化为 0。

public class MiGong {
    private int[][] map;
    private int desX, desY; // 终点坐标

    public MiGong(int row, int col) {
        if (row <= 0 || col <= 0) return;
        map = new int[row][col];
        // 设置上下左右围墙
        for (int i = 0; i < col; i++) {
            map[0][i] = 1;
            map[row - 1][i] = 1;
        }
        for (int i = 0; i < row; i++) {
            map[i][0] = 1;
            map[i][col - 1] = 1;
        }
    }
}

第2步：添加内部挡板

在迷宫内部特定坐标添加障碍物，模拟真实的寻路环境。

// 在位置 (i, j) 添加挡板，不能越界到围墙内
public void addBaffle(int i, int j) {
    if (map == null) return;
    if (i > 0 && i < map.length - 1 && j > 0 && j < map[0].length - 1) {
        map[i][j] = 1;
    }
}

第3步：实现递归寻路逻辑

设定寻路策略：下 → 右 → 上 → 左。如果当前点可以通行则标记为 2；若所有方向均无法到达终点，则该点标记为 3 并回溯。

public boolean setWay(int i, int j) {
    // 1. 如果终点已被标记为通路，说明找到路径
    if (map[desX][desY] == 2) {
        return true;
    }
    
    // 2. 如果当前点不是通路(0)，直接返回false
    if (map[i][j] != 0) {
        return false;
    }

    // 3. 假定当前点可走，标记为2
    map[i][j] = 2;

    // 4. 按照策略递归探测：下(i+1,j)、右(i,j+1)、上(i-1,j)、左(i,j-1)
    if (setWay(i + 1, j)) return true;
    else if (setWay(i, j + 1)) return true;
    else if (setWay(i - 1, j)) return true;
    else if (setWay(i, j - 1)) return true;
    else {
        // 5. 四个方向都走不通，标记为死路3，回溯
        map[i][j] = 3;
        return false;
    }
}

第4步：测试与验证

构建 8x7 的迷宫，添加挡板，设置起点为 (1,1)，终点为 (6,5)。

public class Main {
    public static void main(String[] args) {
        MiGong miGong = new MiGong(8, 7);
        miGong.addBaffle(3, 1); // 添加挡板
        miGong.addBaffle(3, 2); // 添加挡板
        miGong.setDes(6, 5);      // 设置终点
        
        System.out.println("初始地图情况：");
        miGong.show();
        
        miGong.setWay(1, 1);     // 开始寻路
        
        System.out.println("小球走过的路径：");
        miGong.show();
    }
}

输出结果显示，成功标记出一条连通终点的路线（值为2），其余部分保持原状或标记为死路。

案例二：八皇后问题

八皇后是一个经典的回溯算法问题：在 8×8 的国际象棋棋盘上放置八个皇后，使其互不攻击（即任意两个皇后不同行、不同列、不同斜线）。本例旨在找出所有可能的摆法总数。

八皇后问题示意图：

第1步：定义数据结构与检查逻辑

使用一维数组 array 存储解，其中 array[i] = val 表示第 i 行的皇后位于第 val 列。由于每行只放一个皇后，自然满足“不同行”约束，只需检查同列和同斜线。

public class Queue8 {
    private static final int MAX = 8;
    private final int[] array = new int[MAX];
    public static int count = 0;
    public static int judgeCount = 0;

    // 判断第 n 个皇后是否与前面 n-1 个皇后冲突
    private boolean judge(int n) {
        judgeCount++;
        for (int i = 0; i < n; i++) {
            // array[i] == array[n] 表示同一列
            // Math.abs(n - i) == Math.abs(array[n] - array[i]) 表示同一斜线
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                return true;
            }
        }
        return false;
    }
}

第2步：实现递归放置与回溯

从第 0 行开始，尝试将皇后放置在 0~7 的列位置。如果当前放置不冲突，则递归处理下一行；如果冲突，则尝试下一列。

private void check(int n) {
    if (n == MAX) { // 8个皇后都已放置完毕
        print();
        return;
    }
    
    for (int i = 0; i < MAX; i++) {
        array[n] = i; // 将第n个皇后放在第i列
        if (!judge(n)) { // 如果不冲突
            check(n + 1); // 递归放置下一个皇后
        }
        // 如果冲突，for循环继续下一次迭代，即尝试下一列，实现回溯效果
    }
}

private void print() {
    count++;
    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
    System.out.println();
}

第3步：运行结果分析

程序运行后会打印出所有合法的摆放方案，并统计总解法数（92种）以及判断冲突的次数（约 1.5w 次）。

案例三：汉诺塔问题

汉诺塔问题是分治思想的典型应用。假设有三根柱子 A、B、C，需要将 N 个盘子从 A 移动到 C，规则是大盘不能在小盘之上。

汉诺塔示意图：

第1步：分析移动步骤

当盘子数量 n ≥ 2 时，可以将最下面的大盘子视为一个整体，上面的所有盘子视为另一个整体。步骤如下：

1. 将上面 n-1 个盘子从 A 借助 C 移动到 B。
2. 将第 n 个盘子（最底下的）直接从 A 移动到 C。
3. 将 B 上的 n-1 个盘子借助 A 移动到 C。

递归出口为 n=1 时，直接从源柱移动到目标柱。

第2步：代码实现

public class Hanoitower {
    public static void move(int num, char a, char b, char c) {
        if (num == 1) {
            System.out.println("第1个盘从 " + a + "->" + c);
        } else {
            // 1. 上方n-1个盘 从A -> B (借助C)
            move(num - 1, a, c, b);
            
            // 2. 最下方大盘 从A -> C
            System.out.println("第" + num + "个盘从 " + a + "->" + c);
            
            // 3. B上的n-1个盘 从B -> C (借助A)
            move(num - 1, b, a, c);
        }
    }
}

第3步：测试调用

public class Main {
    public static void main(String[] args) {
        Hanoitower.move(3, 'A', 'B', 'C');
    }
}

对于 3 个盘子，控制台将按顺序输出 7 步移动指令，完整演示了递归分解与合并的过程。

总结

递归算法通过将复杂问题拆解为规模更小的子问题来简化代码逻辑。在 Java 开发中，无论是迷宫寻路、排列组合还是分治计算，掌握递归的调用栈机制、基准条件的设定以及回溯策略至关重要。需要注意的是，深层递归可能导致栈溢出，在实际工程中应评估数据规模，必要时考虑转换为迭代或使用尾递归优化（虽然 Java 目前不支持尾递归优化）。

以上就是 Java 递归算法在迷宫、八皇后及汉诺塔中应用的详细内容，更多关于 Java 算法与递归的资料请关注本站其它相关文章！