Рекурсивные функции StackOverflowError

Question

Я кодирования зомби заражать людей в городе, тогда как: 2: Там нет человека 1: Неинфицированные люди 0: Zombies

зомби заражает все нормальные люди, которые вокруг зомби. Ниже представлена ​​моя Java-программа, но я получаю сообщение об ошибке: StackOverflowError.

public class InfectGame { 

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    // TODO Auto-generated method stub 

    int a[][] = { { 1, 1, 1, 1, 2, 2, 2, 1, 1, 0 }, 
      { 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, 
      { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, 
      { 1, 1, 2, 1, 1, 2, 1, 1, 1, 1 }, 
      { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, 
      { 1, 1, 1, 1, 0, 0, 1, 1, 1, 1 }, 
      { 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, 
      { 1, 1, 1, 1, 0, 1, 1, 1, 2, 1 }, 
      { 2, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, 
      { 2, 2, 2, 1, 1, 1, 1, 1, 1, 2 }, }; 

    int i = 0; 
    int j = 0; 
    for (i = 0; i < 10; i++) { 
     for (j = 0; j < 10; j++) { 

      if (a[i][j] == 0) { 
       run_test(i, j, a, 0, 10); 
      } 
     } 
    } 

    i = 0; 
    j = 0; 
    for (i = 0; i < 10; i++) { 
     System.out.print("\n"); 
     for (j = 0; j < 10; j++) { 
      System.out.print(a[i][j] + " "); 
     } 
    } 

} 

public static void run_test(int x, int y, int a[][], int v, int size) { 

    if ((x < 0) || (x >= size)) 
     return; 
    if ((y < 0) || (y >= size)) 
     return; 
    // System.out.print(a[x][y] + " "); 
    // a[x][y] = v; 
    if (a[x][y] != 2) { 
     a[x][y] = v; 
     if (x + 1 < size) { 
      run_test(x + 1, y, a, v, size); 
     } 
     if (x > 0) { 
      run_test(x - 1, y, a, v, size); 
     } 
     if (y + 1 < size) { 
      run_test(x, y + 1, a, v, size); 
     } 
     if (y > 0) { 
      run_test(x, y - 1, a, v, size); 
     } 
    } 

} 

} 


    Exception in thread "main" java.lang.StackOverflowError 
     at InfectGame.run_test(InfectGame.java:55) 
     at InfectGame.run_test(InfectGame.java:58) 
     at InfectGame.run_test(InfectGame.java:55) 
     at InfectGame.run_test(InfectGame.java:58) 
     at InfectGame.run_test(InfectGame.java:55) 
     at InfectGame.run_test(InfectGame.java:58) 
     at InfectGame.run_test(InfectGame.java:55) 
     at InfectGame.run_test(InfectGame.java:58) 
     at InfectGame.run_test(InfectGame.java:55) 
     at InfectGame.run_test(InfectGame.java:58) 
     at InfectGame.run_test(InfectGame.java:55) 
     at InfectGame.run_test(InfectGame.java:58) 
     at InfectGame.run_test(InfectGame.java:55) 
     at InfectGame.run_test(InfectGame.java:58) 
     at InfectGame.run_test(InfectGame.java:55) 
     at InfectGame.run_test(InfectGame.java:58) 
     at InfectGame.run_test(InfectGame.java:55) 
     at InfectGame.run_test(InfectGame.java:58) 
     at InfectGame.run_test(InfectGame.java:55) 
     at InfectGame.run_test(InfectGame.java:58) 
     at InfectGame.run_test(InfectGame.java:55) 
     at InfectGame.run_test(InfectGame.java:58) 

........................................... .............

Answer 1

Рекурсия работает только в том случае, если у вас есть условия завершения. У вас их нет. Посмотрите на эту часть кода:

if (x + 1 < size) { 
     run_test(x + 1, y, a, v, size); 
    } 
    if (x > 0) { 
     run_test(x - 1, y, a, v, size); 
    } 

Первое, если заявление будет рекурсию до тех пор, пока вы попали в конец сетки на текущей строке. В этот момент он перейдет ко второму утверждению if и повторится, но один шаг назад влево. Но при следующей рекурсии он будет идти на один шаг вправо снова, до бесконечности.

Вот почему вы получаете сообщение об ошибке - вы никогда не прекращаете свою рекурсию.

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

if (a[x][y] != 2) { 

Должно быть:

if (a[x][y] != 2 && a[x][y] != v) { 

В противном случае будет заполняться то же квадраты с зомби снова и снова.

Но, думая больше о вашей проблеме зомби, она немного отличается от обычной заливки. При заполнении, если пиксель уже имеет нужный цвет, вы можете остановить рекурсию. Для зомби, что не соответствует первому зомби - от этого зомби он распространяется. Поэтому первая итерация не должна проверять, является ли она уже зомби, но любая дальнейшая итерация рекурсии должна проверяться, иначе она не прекратится.

Вы можете сделать это следующим образом:

public static void run_test(int x, int y, int a[][], int v, int size, boolean first) { 
    if ((x < 0) || (x >= size)) 
     return; 
    if ((y < 0) || (y >= size)) 
     return; 
    if (a[x][y] != 2 && (first || a[x][y] != v)) { 
     a[x][y] = v; 
     if (x + 1 < size) { 
      run_test(x + 1, y, a, v, size, false); 
     } 
     if (x > 0) { 
      run_test(x - 1, y, a, v, size, false); 
     } 
     if (y + 1 < size) { 
      run_test(x, y + 1, a, v, size, false); 
     } 
     if (y > 0) { 
      run_test(x, y - 1, a, v, size, false); 
     } 
    } 
} 

И воззвание от основного метода следует читать:

run_test(i, j, a, 0, 10, true); 

Answer 2

Вы застряли здесь:

if (x + 1 < size) { 
     run_test(x + 1, y, a, v, size); 
    } 
    if (x > 0) { 
     run_test(x - 1, y, a, v, size); 
    } 

Поскольку х всегда первое или второе если- состояние.

Answer 3

Вы должны лучше использовать имена переменных. Используйте то, что описывает переменную вместо x, y, z.