Java递归函数中数组被永久修改的问题及解决咨询

你当前代码的核心问题是：

1. 使用了全局共享的temp数组，而且只是把原数组的对象引用复制给temp——本质上temp和原数组指向的是同一批Units对象，修改temp里的对象属性时，原数组的对象也会被改动。
2. 递归后试图把原数组复制回temp，但因为对象已经被修改过，这种恢复完全无效。

要保证原数组不受影响，核心思路是让每个递归分支操作独立的数组副本，具体步骤如下：

1. 给Units类实现深拷贝能力 #

因为Units是自定义对象，直接复制引用会导致修改副本时影响原对象，所以需要给Units添加拷贝构造方法或clone方法，用来复制单个对象的状态：

public class Units {
    boolean Frog;
    // 其他属性、removeFrog()/setFrog()等方法
    
    // 拷贝构造方法，复制所有需要保留的属性
    public Units(Units other) {
        this.Frog = other.Frog;
        // 如果有其他属性（比如ID），也要在这里复制
    }
    
    // 或者实现Cloneable接口的clone方法（二选一即可）
    @Override
    public Units clone() {
        try {
            Units clone = (Units) super.clone();
            clone.Frog = this.Frog;
            return clone;
        } catch (CloneNotSupportedException e) {
            throw new AssertionError();
        }
    }
}

2. 实现二维数组的深拷贝工具方法 #

写一个工具方法，用来完整复制整个棋盘的状态，生成完全独立的副本：

private Units[][] deepCopyBoard(Units[][] original) {
    int size = original.length;
    Units[][] copy = new Units[size][size];
    for (int x = 0; x < size; x++) {
        for (int y = 0; y < size; y++) {
            // 用拷贝构造方法或clone创建独立的Units对象
            copy[x][y] = new Units(original[x][y]);
            // 或者 copy[x][y] = original[x][y].clone();
        }
    }
    return copy;
}

3. 重构递归方法，移除全局temp #

修改递归逻辑，每次移动操作都在拷贝后的数组上执行，递归传递这个副本，不再需要手动恢复原数组：

public void RecursiveFunc(Units[][] array) {
    // 先检查当前状态是否是目标状态
    if (CheckNumberFrogs(array) == 1 && CheckLastID(array) == getgoalLoc()) {
        numOfPlans += 1;
        return;
    }

    // 遍历所有青蛙位置，尝试所有可能的移动
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length; j++) {
            if (!array[i][j].Frog) continue;

            // 向左跳
            if (i > 1 && array[i-1][j].Frog && !array[i-2][j].Frog) {
                Units[][] newBoard = deepCopyBoard(array);
                newBoard[i][j].removeFrog();
                newBoard[i-1][j].removeFrog();
                newBoard[i-2][j].setFrog();
                RecursiveFunc(newBoard);
            }

            // 向右跳
            if (i < array.length - 2 && array[i+1][j].Frog && !array[i+2][j].Frog) {
                Units[][] newBoard = deepCopyBoard(array);
                newBoard[i][j].removeFrog();
                newBoard[i+1][j].removeFrog();
                newBoard[i+2][j].setFrog();
                RecursiveFunc(newBoard);
            }

            // 向下跳
            if (j > 1 && array[i][j-1].Frog && !array[i][j-2].Frog) {
                Units[][] newBoard = deepCopyBoard(array);
                newBoard[i][j].removeFrog();
                newBoard[i][j-1].removeFrog();
                newBoard[i][j-2].setFrog();
                RecursiveFunc(newBoard);
            }

            // 向上跳
            if (j < array.length - 2 && array[i][j+1].Frog && !array[i][j+2].Frog) {
                Units[][] newBoard = deepCopyBoard(array);
                newBoard[i][j].removeFrog();
                newBoard[i][j+1].removeFrog();
                newBoard[i][j+2].setFrog();
                RecursiveFunc(newBoard);
            }

            // 左下对角线跳
            if (i > 1 && j > 1 && array[i-1][j-1].Frog && !array[i-2][j-2].Frog) {
                Units[][] newBoard = deepCopyBoard(array);
                newBoard[i][j].removeFrog();
                newBoard[i-1][j-1].removeFrog();
                newBoard[i-2][j-2].setFrog();
                RecursiveFunc(newBoard);
            }

            // 右下对角线跳
            if (i < array.length - 2 && j > 1 && array[i+1][j-1].Frog && !array[i+2][j-2].Frog) {
                Units[][] newBoard = deepCopyBoard(array);
                newBoard[i][j].removeFrog();
                newBoard[i+1][j-1].removeFrog();
                newBoard[i+2][j-2].setFrog();
                RecursiveFunc(newBoard);
            }

            // 左上对角线跳
            if (i > 1 && j < array.length - 2 && array[i-1][j+1].Frog && !array[i-2][j+2].Frog) {
                Units[][] newBoard = deepCopyBoard(array);
                newBoard[i][j].removeFrog();
                newBoard[i-1][j+1].removeFrog();
                newBoard[i-2][j+2].setFrog();
                RecursiveFunc(newBoard);
            }

            // 右上对角线跳
            if (i < array.length - 2 && j < array.length - 2 && array[i+1][j+1].Frog && !array[i+2][j+2].Frog) {
                Units[][] newBoard = deepCopyBoard(array);
                newBoard[i][j].removeFrog();
                newBoard[i+1][j+1].removeFrog();
                newBoard[i+2][j+2].setFrog();
                RecursiveFunc(newBoard);
            }
        }
    }
}

为什么这样能解决问题 #

• 每个递归分支操作的都是当前棋盘的独立副本，原数组永远不会被修改。
• 不需要再手动恢复数组状态，因为所有修改都局限在各自的副本中。
• 深拷贝保证了每个Units对象都是独立的，修改副本的属性不会影响原数组中的对象。

内容的提问来源于stack exchange，提问作者Zack