递归算法出现StackOverflow错误

Question

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

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((如果其中一个组合生成了唯一的解决方案(应该发生(，算法就会停止(。

崩溃前算法生成的板

正如你在上面的图片中看到的，该算法运行良好，直到崩溃。

崩溃的调试信息

在这张图中，您可以看到StackOverflowError是在哪里触发的，因为您可以看到calculaNumCells是一个非递归方法。

编辑：我还尝试不将参数tablero解析为递归算法或其他方法，如CalculaNumCells，因为这是不必要的(它与类的隐式参数相同(。不管怎么说，执行一直在崩溃，与之前完全相同。

Answer 1

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

例如，如果递归方法只调用它自己，那么在调用该方法时堆栈总是会耗尽。