stackoverflower

2ledvvac  于 2021-07-06  发布在  Java
关注(0)|答案(1)|浏览(1249)

我试图编写一个递归算法,以便为一个名为kakuro的游戏生成一个有效的棋盘(唯一的解决方案)。当执行程序时,我总是得到一个stackoverflower错误。我试着调试我的代码,它是按预期工作,但它突然崩溃在一个非递归方法。我在互联网上读到过这个问题,我已经检查过我没有用相同的参数进行两次递归调用。该算法对某些正方形尝试不同的值,并且(当每个正方形都有自己的值时,它应该尝试这些正方形的所有可能的值组合)对其进行求解,以查看它是否有唯一的解。

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),我们希望在其中尝试所有可能的组合(如果其中一个组合生成了唯一的解决方案(应该发生),算法停止)。
崩溃前由算法生成的电路板
如上图所示,该算法在崩溃前工作良好。
崩溃的调试信息
在这张图片中,您可以看到StackOverflowerError是在哪里触发的,因为您可以看到calculanumcells是一个非递归方法。
edit:我也尝试不解析参数tablero,因为它对递归算法或其他方法(如calculanumcells)是不必要的(与类的隐式参数相同)。不管怎么说,执行总是在和以前一样的地方崩溃。

lo8azlld

lo8azlld1#

StackOverflowerError仅表示堆栈中没有可用于新帧的空间。在您的例子中,递归调用仍然会填满堆栈的大部分,但是由于该方法调用除自身之外的其他方法,因此这些方法也会耗尽堆栈。
例如,如果您的递归方法仅调用自身,则在调用该方法时堆栈将始终耗尽。

相关问题