Пожалуйста, объясните, почему мой код вызвал ошибку переполнения стека - PullRequest
Новая
       57

Пожалуйста, объясните, почему мой код вызвал ошибку переполнения стека

0 голосов
/ 21 октября 2019

Вот код: 

public static int maxPathLengthHelper(int[][] paths, int x, int y){
    int maxLength = 0;
    if(x > 0 && paths[x-1][y] == 1){
        int currentLength = 1 + maxPathLengthHelper(paths,x-1,y);
        if(currentLength > maxLength){
            maxLength = currentLength;
        }
    }
    if(y > 0 && paths[x][y-1] == 1){
        int currentLength = 1 + maxPathLengthHelper(paths,x,y-1);
        if(currentLength > maxLength){
            maxLength = currentLength;
        }
    }
    if(x < paths.length - 1 && paths[x+1][y] == 1){
        int currentLength = 1 + maxPathLengthHelper(paths,x+1,y);
        if(currentLength > maxLength){
            maxLength = currentLength;
        }
    }
    if(y < paths[0].length - 1 && paths[x][y+1] == 1){
        int currentLength = 1 + maxPathLengthHelper(paths,x,y+1);
        if(currentLength > maxLength){
            maxLength = currentLength;
        }
    }
    return maxLength;
}

В операторах if, где значение y изменено, возникает ошибка переполнения стека, однако в частях, где значение x изменяется, ошибки нет. Мне было интересно, почему это было;если бы оба были неправильными, я бы все изменил, но это только во втором и четвертом, если утверждения, что ошибки переполнения стека вызваны рекурсивным вызовом. Первое и третье, если заявления не имеют проблем, и я абсолютно не представляю, что в них отличается.

1 Ответ

1 голос
/ 21 октября 2019

Это потому, что когда ваш код перемещается с 0,0 на 1,0, он снова проверяет 0,0, так как первое if условие выполнено 


public static int[][] visitedNodes;

public static void main(String args[]){
  // when you call the recursive method, also initiate the visitedNodes
   visitedNodes = new int[totalX][totalY];
   for(int i = 0; i < totalX; i++)
     for(int j = 0; j < totalY; i++)
        visitedNodes[i][j] = 0;
   maxPathLengthHelper(myPathList,0,0);
}

public static int maxPathLengthHelper(int[][] paths, int x, int y){
    int maxLength = 0;
    visitedNodes[x][y] = 1;
    if(x > 0 && visitedNodes[x-1][y] == 0 && paths[x-1][y] == 1){
        int currentLength = 1 + maxPathLengthHelper(paths,x-1,y);
        if(currentLength > maxLength){
            maxLength = currentLength;
        }
    }
    if(y > 0 && visitedNodes[x][y-1] == 0  && paths[x][y-1] == 1){
        int currentLength = 1 + maxPathLengthHelper(paths,x,y-1);
        if(currentLength > maxLength){
            maxLength = currentLength;
        }
    }
    if(x < paths.length - 1 && visitedNodes[x+1][y] == 0  && paths[x+1][y] == 1){
        int currentLength = 1 + maxPathLengthHelper(paths,x+1,y);
        if(currentLength > maxLength){
            maxLength = currentLength;
        }
    }
    if(y < paths[0].length - 1 && visitedNodes[x][y+1] == 0  && paths[x][y+1] == 1){
        int currentLength = 1 + maxPathLengthHelper(paths,x,y+1);
        if(currentLength > maxLength){
            maxLength = currentLength;
        }
    }
    return maxLength;
}
...