递归时出现 StackOverFlowError

Question

我正在使用递归算法编写游戏，但在编译时得到 "Whosebug error"。我知道这可能是因为没有一个好的结束条款，而且它会永远重复。我只是想获得一些有关如何修复它的帮助。我也知道我要发布的代码有点太多，但我想提供尽可能多的信息。有什么疑问，尽管问。

它从以下调用开始：

Integer matrix[][] = new Integer[5][5];
Deque<String> path = new ArrayDeque<>();
ArrayList<Deque<String>> paths = new ArrayList<>();
CoordenateList cList = new CoordenateList();

solver2(matrix, 0, 0, 1, path, paths, cList);

"solver2"方法及辅助方法如下：

public static void solver2(Integer[][] matrix, int x, int y, int num,
        Deque<String> path, ArrayList<Deque<String>> paths, CoordenateList cList) {

    if (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)) == null) {
        Coordenate c = new Coordenate((Integer.toString(y) + "," + Integer.toString(x))); //substitir nos IF's
        cList.addCoordenate(c);
    }

    if (y - 3 < 0 || (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[0] == true || matrix[y - 3][x] != null) {
        //NORTE
        if (x + 3 > matrix.length - 1 || (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[1] == true || matrix[y][x + 3] != null) {
            //ESTE
            if (y + 3 > matrix.length - 1 || (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[2] == true || matrix[y + 3][x] != null) {
                //SUL
                if (x - 3 < 0 || (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[3] == true || matrix[y][x - 3] != null) {
                    //OESTE
                    if (y - 2 < 0 || x + 2 > matrix.length - 1 || (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[4] == true || matrix[y - 2][x + 2] != null) {
                        //NE
                        if (y + 2 > matrix.length - 1 || x + 2 > matrix.length - 1 || (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[5] == true || matrix[y + 2][x + 2] != null) {
                            //SE
                            if (y + 2 > matrix.length - 1 || x - 2 < 0 || (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[6] == true || matrix[y + 2][x - 2] != null) {
                                //SO
                                if (y - 2 < 0 || x - 2 < 0 || (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[7] == true || matrix[y - 2][x - 2] != null) {
                                    //NO

                                    if (num == matrix.length * matrix.length) {
                                        Deque<String> aux = new ArrayDeque<>();
                                        aux.addAll(path);
                                        paths.add(aux);
                                        path.pop();
                                        cleanRecord(num, matrix, cList); //desnecessário
                                        num--;

                                    } else {
                                        //LOSER
                                        path.pop();
                                        num--;
                                        y = getCoordenatePrevious(num, matrix)[1];
                                        x = getCoordenatePrevious(num, matrix)[0];
                                        num++;
                                        cleanRecord(num, matrix, cList);
                                        num--;
                                    }

                                } else {
                                    matrix[y - 2][x - 2] = num + 1;
                                    (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[7] = true;
                                    path.push(Integer.toString(y + 2) + "," + Integer.toString(x - 2));
                                    solver2(matrix, x - 2, y + 2, num + 1, path, paths, cList);
                                }
                            } else {
                                matrix[y + 2][x - 2] = num + 1;
                                (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[6] = true;
                                path.push(Integer.toString(y + 2) + "," + Integer.toString(x - 2));
                                solver2(matrix, x - 2, y + 2, num + 1, path, paths, cList);
                            }
                        } else {
                            matrix[y + 2][x + 2] = num + 1;
                            (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[5] = true;
                            path.push(Integer.toString(y + 2) + "," + Integer.toString(x + 2));
                            solver2(matrix, x + 2, y + 2, num + 1, path, paths, cList);
                        }
                    } else {
                        matrix[y - 2][x + 2] = num + 1;
                        (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[4] = true;
                        path.push(Integer.toString(y - 2) + "," + Integer.toString(x + 2));
                        solver2(matrix, x + 2, y - 2, num + 1, path, paths, cList);
                    }
                } else {
                    matrix[y][x - 3] = num + 1;
                    (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[3] = true;
                    path.push(Integer.toString(y) + "," + Integer.toString(x - 3));
                    solver2(matrix, x - 3, y, num + 1, path, paths, cList);
                }
            } else {
                matrix[y + 3][x] = num + 1;
                (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[2] = true;
                path.push(Integer.toString(y + 3) + "," + Integer.toString(x));
                solver2(matrix, x, y + 3, num + 1, path, paths, cList);
            }
        } else {
            matrix[y][x + 3] = num + 1;
            (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[1] = true;
            path.push(Integer.toString(y) + "," + Integer.toString(x + 3));
            solver2(matrix, x + 3, y, num + 1, path, paths, cList);
        }
    } else {
        matrix[y - 3][x] = num + 1;
        (cList.getCoordenateByKey(Integer.toString(y) + "," + Integer.toString(x)).getVisited())[0] = true;
        path.push(Integer.toString(y - 3) + "," + Integer.toString(x));
        solver2(matrix, x, y - 3, num + 1, path, paths, cList);
    }

    int cont = 0;
    if (checkIfNumExists(num, matrix)) {
        boolean[] b = cList.getCoordenateByKey(Integer.toString(getCoordenatePrevious(num, matrix)[1]) + "," + Integer.toString(getCoordenatePrevious(num, matrix)[0])).getVisited();

        if (y - 3 >= 0 && matrix[y - 3][x] == null && b[0] == false) {
            //NORTE
            cont++;
            solver2(matrix, x, y, num, path, paths, cList);
        } else if (x + 3 < matrix.length && matrix[y][x + 3] == null && b[1] == false) {
            //ESTE
            cont++;
            solver2(matrix, x, y, num, path, paths, cList);
        } else if (y + 3 < matrix.length && matrix[y + 3][x] == null && b[2] == false) {
            //SUL
            cont++;
            solver2(matrix, x, y, num, path, paths, cList);
        } else if (x - 3 >= 0 && matrix[y][x - 3] == null && b[0] == false && b[3] == false) {
            //OESTE
            cont++;
            solver2(matrix, x, y, num, path, paths, cList);
        } else if (y - 2 >= 0 && x + 2 < matrix.length && matrix[y - 2][x + 2] == null && b[4] == false) {
            //NE
            cont++;
            solver2(matrix, x, y, num, path, paths, cList);
        } else if (y + 2 < matrix.length && x + 2 < matrix.length && matrix[y + 2][x + 2] == null && b[5] == false) {
            //SE
            cont++;
            solver2(matrix, x, y, num, path, paths, cList);
        } else if (y + 2 < matrix.length && x - 2 >= 0 && matrix[y + 2][x - 2] == null && b[6] == false) {
            //SO
            cont++;
            solver2(matrix, x, y, num, path, paths, cList);
        } else if (y - 2 >= 0 && x - 2 >= 0 && matrix[y - 2][x - 2] == null && b[7] == false) {
            //NO
            cont++;
            solver2(matrix, x, y, num, path, paths, cList);
        }

    }

    if (cont == 0 && checkIfNumExists(num, matrix)) {
        if (num != 1) {
            num--;
            path.pop();
            cleanRecord(num + 1, matrix, cList);
            cleanMatrixAbove(num, matrix, cList);

        }

    }
}

/**
 * returns the coordenates of the num
 *
 * @param num
 * @param matrix
 * @return
 */
public static int[] getCoordenatePrevious(int num, Integer[][] matrix) {

    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix.length; j++) {
            if (matrix[i][j] != null && matrix[i][j] == num) {
                int[] array = new int[2];
                array[0] = j; //x
                array[1] = i; //y
                return array;
            }
        }
    }

    return null;
}

/**
 * cleans the visited record of the num
 *
 * @param num
 * @param matrix
 * @param cList
 */
public static void cleanRecord(int num, Integer[][] matrix, CoordenateList cList) {

    if (checkIfNumExists(num, matrix)) {
        Coordenate c = cList.getCoordenateByKey(Integer.toString(getCoordenatePrevious(num, matrix)[1]) + "," + Integer.toString(getCoordenatePrevious(num, matrix)[0]));
        c.cleanVisited();
    }
}

/**
 * sets null every number in the matrix that are bigger than num
 *
 * @param num
 * @param matrix
 * @param cList
 */
public static void cleanMatrixAbove(int num, Integer[][] matrix, CoordenateList cList) {

    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix.length; j++) {
            if (matrix[i][j] != null && matrix[i][j] > num) {
                matrix[i][j] = null;
            }
        }
    }
}

/**
 * checks if the num exists in the matrix
 * 
 * @param num
 * @param matrix
 * @return 
 */
public static boolean checkIfNumExists(int num, Integer[][] matrix) {
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix.length; j++) {
            if (matrix[i][j] != null && matrix[i][j] == num) {
                return true;
            }
        }
    }
    return false;
}

其他类（Coordenate, CoordenateList）如下：

public class Coordenate {

String keyID;
boolean[] visited;

public Coordenate(String keyID) {
    this.keyID = keyID;
    this.visited = new boolean[8];
}

public String getKeyID() {
    return this.keyID;
}

public int getXFromKeyID() {
    String[] aux = this.keyID.split(",");
    int xaux = Integer.parseInt(aux[0]);
    return xaux;
}

public int getYFromKeyID() {
    String[] aux = this.keyID.split(",");
    int yaux = Integer.parseInt(aux[1]);
    return yaux;
}

public boolean[] getVisited() {
    return visited;
}

public void cleanVisited() {
    visited = new boolean[8];
}

public boolean allVisited() {
    for (int i = 0; i < 8; i++) {
        if (visited[i] = false) {
            return false;
        }
    }
    return true;
}

@Override
public String toString() {
    return "Coordenate{" + "keyID=" + keyID + ", visited=" + visited + '}';
}

@Override
public int hashCode() {
    int hash = 3;
    return hash;
}

@Override
public boolean equals(Object obj) {
    if (obj == null) {
        return false;
    }
    if (getClass() != obj.getClass()) {
        return false;
    }
    final Coordenate other = (Coordenate) obj;
    if (!Objects.equals(this.keyID, other.keyID)) {
        return false;
    }
    return true;
}

}


public class CoordenateList {

public ArrayList<Coordenate> coordenateList;

public CoordenateList() {
    coordenateList = new ArrayList<>();
}

public ArrayList<Coordenate> getCoordenateList() {
    return coordenateList;
}

public Coordenate getCoordenateByKey(String keyID) {
    for (Coordenate c : coordenateList) {
        if (c.getKeyID().equals(keyID)) {
            return c;
        }
    }
    return null;
}

public boolean addCoordenate(Coordenate c) {
    if (!coordenateList.contains(c)) {
        return coordenateList.add(c);
    }
    return false;
}

public boolean removeCoordenate(Coordenate c){
    if (coordenateList.contains(c)) {
        return coordenateList.remove(c);
    }
    return false;
}
}

再一次，对于庞大的代码，我深表歉意，但我真的想提供尽可能多的信息。如有任何问题或疑问，请随时提出。

Answer 1

如果您在编译代码时遇到 Whosebug 错误，那么您可能在编译器中发现了错误。但是您绝对 而不是 在编译代码时收到 Whosebug 错误，您在运行你的代码。

^{（递归是一个高级计算机科学主题，但如果您仍然在编译程序和运行等概念上苦苦挣扎，那么递归可能是一个现在对你来说有点太高级了。只是一个想法。）}

在您的 solver2() 函数中，您有一个可怕的嵌套 if() 语句，除了某些不太可能发生的情况外，它总是会递归。

然后，您有另一个 if()-else 语句序列，除非 none 个测试条件为真，否则它们也将始终递归。

我不认为任何人会投入所有必要的时间来阅读和理解你那里的这个怪物，所以唯一可以提出的建议是在你的递归函数中添加更多条件，这将使它更可能会在某些时候避免递归，这样你的递归函数就不会永远递归。（也就是说，直到它用完堆栈。）

递归时出现 StackOverFlowError

StackOverFlowError when recursing

java

stack-overflow

recursion

netbeans