StackOverFlowError when recursing

Question

I'm programming a game using a recursive algorithm but I got "StackOverFlow error" when compiling it. I'm aware that that's probably due to not having a good end clause and it's re-cursing forever. I'm just trying to get some help on how to fix it. I'm also aware that the code I'll be posting is a bit too much but I want to provide as much info as I can. Any doubts, just ask.

It starts with the following call:

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

The "solver2" method and the auxiliar methods are the following:

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

The other classes (Coordenate, CoordenateList) are the following:

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

Once again, I'm sorry for the huge code, but I really want to give as much info as I possibly can. Any questions or doubts, feel free to ask.

Sorry I can not give proper answer since I dont have time to read and understand all code but quickest way I can think of is adding logging for each single step. So you can see which conditions are satisfied and where you are circling. Also you better check/exercise on internet for alternatives of large if-else chains. i.e. Enum types or some java 8 future like lambda. here is a basic idea: http://stackoverflow.com/questions/1199646/long-list-of-if-statements-in-java — HRgiger, Dec 08 '15 at 16:26
This sounds like a *great* opportunity to familiarize yourself with the use of a debugger. With a debugger, you can step through the code *as it executes* and observe its behavior as well as the runtime values of any variables in the code. This will help you diagnose why your recursion is infinite (or at least too deep) and allow you to determine why the conditions you expect *should* terminate the recursion are not doing so. (Hint: Stack Overflow is not such a debugger.) — David, Dec 08 '15 at 16:27
@David I'm well familiarized with Debugger! The problem is that there's too much recursions and I'ts really hard to keep track of everything. I debugged a lot and It was all working perfectly so I assumed that it would run well too, but It seems it doesn't — Pedro Gonçalves, Dec 08 '15 at 16:29

Mike Nakis · Accepted Answer · 2015-12-08T16:52:21.003

If you were getting a StackOverFlow error when compiling your code, then you would have found a bug in your compiler. But you are definitely not receiving a StackOverFlow error when compiling your code, you are receiving it when running your code.

^{(Recursion is an advanced computer science topic, but if you are still struggling with concepts like when you are compiling your program and when you are running it, then recursion might be a bit too advanced for you right now. Just a thought.)}

In your solver2() function you have a monstrous nested if() statement which will always recurse except for a certain unlikely set of circumstances.

Then, you have another sequence of if()-else statements which will also always recurse unless none of the tested conditions is true.

I do not think anyone will invest all the time necessary to read and make sense out of this monstrosity that you have there, so the only recommendation that can be made is to add more conditions in your recursive function which will make it far more likely to refrain from recursing at some point, so that your recursive function will not keep recursing forever. (That is, until it runs out of stack.)

StackOverFlowError when recursing

1 Answers1