递归算法的 StackOverflowError

Question

我正在尝试编写递归算法，以便为名为 kakuro 的游戏生成有效棋盘（唯一解）。执行程序时，我不断收到 WhosebugError。我尝试调试我的代码并且它按预期工作，但它突然在非递归方法中崩溃。我一直在互联网上阅读有关此问题的信息，并且我已经检查过我没有使用相同的参数进行两次递归调用。该算法为某些方块尝试不同的值，并且（当每个方块都有自己的值时，它应该因此尝试这些方块的所有可能的值组合）解决它以查看它是否有唯一的解决方案。

 private boolean generarKakuroRecursivo(ArrayList<Negra> noColocados, Casella[][] tablero){
        if (noColocados.size() == 0 ){
            System.out.println(getStringTablero());
            if (kakuroUnico(tablero)){
                this.tauler = tablero;
                return true;
            }
            else return false; 
        }
        
        Negra casillaNegra = noColocados.get(0);

        boolean fila = casillaNegra.getFila() == 0 && casillaNegra.getCoords().getElement1()+1 < dimensio && this.tauler[casillaNegra.getCoords().getElement0()][casillaNegra.getCoords().getElement1()+1].getTipus() == 'B';
        boolean columna = casillaNegra.getColumna() == 0 && casillaNegra.getCoords().getElement0()+1 < dimensio && this.tauler[casillaNegra.getCoords().getElement0()+1][casillaNegra.getCoords().getElement1()].getTipus() == 'B';
        ArrayList <Pair<Integer, ArrayList<ArrayList<Integer>> >> posibilidadesNegra = calcularPosibilidades(casillaNegra);

        //CALCULAMOS LOS POSIBLES NUMEROS PARA LA CASILLA NEGRA QUE HEMOS COGIDO

        int index1 = casillaNegra.getCoords().getElement0(), index2 = casillaNegra.getCoords().getElement1();
        for (Pair<Integer, ArrayList<ArrayList<Integer>> > posibilidad : posibilidadesNegra){
            int valor = posibilidad.getElement0();
            if (fila && columna){
                colocarNegra(((Negra)tablero[index1][index2]), valor, true);
                noColocados.get(0).setNumFil(valor); //poner fila =false
            } //actualizar restricciones
            else if(fila){
                colocarNegra(((Negra)tablero[index1][index2]), valor, true);
                noColocados.remove(0);
            }
            else if (columna){
                colocarNegra(((Negra)tablero[index1][index2]), valor, false);
                noColocados.remove(0);
            }
            if (generarKakuroRecursivo(noColocados, tablero)) return true;
            else{
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     if (!noColocados.contains(casillaNegra)) noColocados.add(casillaNegra);
                if (fila){
                    retirarNegra((Negra)tablero[index1][index2],true);
                    if (!noColocados.contains(casillaNegra)) noColocados.add(casillaNegra);
                }

                else if (columna) {
                    retirarNegra((Negra)tablero[index1][index2], false);
                    if (!noColocados.contains(casillaNegra)) noColocados.add(casillaNegra);
                }

            }
        } //Caso recursivo

        //PROBAMOS RECURSIVAMENTE TODAS LAS OPCIONES

        return false;
}

这是讨论中的递归函数，noColocados 是一个 ArrayList，其中包含正方形（属于 tablero），我们想在其中尝试所有可能的组合（如果其中一个组合生成唯一的解决方案（应该发生）算法停止）。

Boards generated by the algorithm before crashing

正如您在上图中看到的，该算法在崩溃之前运行良好。

Debug information of the crash

在这张图片中，您可以看到触发 WhosebugError 的位置，因为您可以看到 calculaNumCells 是一种非递归方法。

编辑：我也尝试不解析参数 tablero 因为它对递归算法没有必要（它与 class 的隐式参数相同）也没有像 CalculaNumCells 这样的其他方法。无论如何，执行一直在与之前崩溃的位置完全相同的地方崩溃。

Answer 1

WhosebugError 仅表示堆栈中没有 space 可用于新帧。在您的情况下，递归调用仍然会填满大部分堆栈，但是，由于该方法会调用除自身之外的其他方法，因此这些方法也会耗尽堆栈。

例如，如果您的递归方法仅调用其自身，则在调用该方法时堆栈总是会耗尽。

递归算法的 StackOverflowError

StackOverflowError on recursive algorithm

java

stack-overflow

algorithm

recursion