Recursive function StackOverflowError

Question

I am coding Zombies infect people in a city whereas: 2: There is no person 1: Uninfected people 0: Zombies

Zombies will infect all normal people that are around Zombies. Below is my Java program but I am getting the error: 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)

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

you don't `return` when you call your recursive methods, is this what you intend? — Boris the Spider, Feb 08 '14 at 14:05
Possible duplicate of [What is a StackOverflowError?](http://stackoverflow.com/questions/214741/what-is-a-stackoverflowerror) — Raedwald, Jan 22 '16 at 13:28

Erwin Bolwidt · Accepted Answer · 2014-02-08T14:28:02.183

Recursion only works if you have terminating conditions. You don't have them. Look at this part of your code:

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

The first if statement will recurse until you've hit the end of the grid on the current line. At that point, it will go to the second if statement and recurse again, but one step back to the left. But on the next recursion, it will go one step to the right again, ad infinitum.

That's why you get the error - you never terminate your recursion.

Now that you explained that you are trying to do a flood fill, I can see which terminating condition you need:

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

Should be:

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

Otherwise you keep filling the same squares with zombies over and over again.

But thinking more about your problem of zombies, it is a bit different from an ordinary fill. In a fill, if a pixel already has the colour your want, you can stop the recursion. For zombies that is not true for the first zombie - from this zombie it spreads out. So the first iteration should not check whether it is already a zombie, but any further iteration of the recursion should check, or else it doesn't terminate.

You can do it like this:

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

And the invocation from the main method should read:

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

Thank you Erwin Bolwidt. The program I am coding is to simulate the process of infecting people who are neighbors of each Zombies. And the algorithm I am applying for my program is Recursive Flood Fill. (My English is not very good, so if there is any grammatical mistakes, please sympathize me) — Long Uni, Feb 08 '14 at 14:19
I added some more information to the answer in response to your comment. — Erwin Bolwidt, Feb 08 '14 at 14:28
I have done my program according to your code and I have had succesfully! Thank you once again. — Long Uni, Feb 08 '14 at 14:35

score 0 · Answer 2 · answered Feb 08 '14 at 14:06

0

You stuck here:

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

Because x is always the first or second if- condition.

answered Feb 08 '14 at 14:06

pL4Gu33

2,045
16
38

Yes. You're correct. I am getting the problem here. Can you give me some advice to resolve this? I am using FillFlood Algorithm to do my assignment but I am not very sure. – Long Uni Feb 08 '14 at 14:09

score 0 · Answer 3 · answered Feb 08 '14 at 14:23

0

You should use better variable names. Use something that describes the variable instead of x, y, z.

answered Feb 08 '14 at 14:23

Jeroen

413
1
4
16

Thank you. I am newly acquainted with programming. Your advice would be my experience. – Long Uni Feb 08 '14 at 14:29

Recursive function StackOverflowError

3 Answers3