StackOverflowError on recursive algorithm

I’m trying to code a recursive algorithm in order to generate a valid board(unique solution) for a game called kakuro. When executing the program I keep getting a StackOverflowError. I tried debugging my code and it is working as expected, but it suddenly crashes in a non recursive method. I have been reading about this issue on the internet and I have already checked that I don’t make two recursive calls with the same parameters. This algorithm tries different values for certain squares and (when every square has its own value, it should thus try every possible combination of values for those squares) solves it in order to see whether it has an unique solution.

 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;
}

This is the recursive function in discuss, noColocados is an ArrayList which contains the squares (belonging to tablero) where we want to try all the possible combinations (if one of those combinations generates a unique solution(it should happen) the algorithm stops).

Boards generated by the algorithm before crashing

As you can see in the picture above, the algorithm works well until it crashes.

Debug information of the crash

In this picture you can see where the StackOverflowError is triggered, as you can see calculaNumCells is a non recursive method.

Edit: I also tried not parsing the parameter tablero as it was unnecessary (it is the same as the implicit parameter of the class) to the recursive algorithm nor other methods like CalculaNumCells. Anyway the execution keeps crashing in the same exact point that it was crashing before.

Answer

A StackOverflowError merely indicates that there’s no space available in the stack for a new frame. In your case, the recursive calls still fill up most of the stack but, since the method calls other methods besides itself, those can also exhaust the stack.

If, for example, your recursive method called only itself, the stack would always be exhausted when calling that one method.

Advertisement

Answer