java stackoverflow error

Question

Hey guys, I'm working on a program for a university course that uses a method called get_line() to recursively calculate a list of successive locations to get from one point on a grid to another. When I run it, I get a stack overflow at the line of the last return statement in the method. I was wondering if I could someone else to look over the method, and see if anything looks totally wrong. the method is provided below:

Thank you for the help!

location is an object containing a row r and a column c.

private Vector<location> get_line(location from, location to) {
    location nextLoc = new location();
    Vector<location> loc = new Vector<location>();
    Random r = new Random();

    if(to.r == from.r && to.c == from.c) {
        return(loc);
    } else {
        if(to.r > from.r && to.c > from.c) {
            nextLoc.r = from.r + 1;
            nextLoc.c = from.c + 1;
        } else if(to.r < from.r && to.c < from.c) {
            nextLoc.r = from.r - 1;
            nextLoc.c = from.c - 1;
        } else if(to.r < from.r && to.c > from.c) {
            nextLoc.r = from.r - 1;
            nextLoc.c = from.c + 1;
        } else if(to.r > from.r && to.c < from.c) {
            nextLoc.r = from.r + 1;
            nextLoc.c = from.c - 1;
        } else if(to.r == from.r && to.c > from.c) {
            if(r.nextInt(2) == 0) {
                nextLoc.r = from.r + 1;
            } else {
                nextLoc.r = from.r - 1;
            }
            nextLoc.c = from.c + 1;
        } else if(to.r == from.r && to.c < from.c) {
            if(r.nextInt(2) == 0) {
                nextLoc.r = from.r + 1;
            } else {
                nextLoc.r = from.r - 1;
            }
            nextLoc.c = from.c - 1;
        } else if(to.r < from.r && to.c == from.c) {
            nextLoc.r = from.r - 1;
            if(r.nextInt(2) == 0) {
                nextLoc.c = from.c + 1;
            } else {
                nextLoc.c = from.c - 1;
            }
        } else if(to.r > from.r && to.c == from.c) {
            nextLoc.r = from.r + 1;
            if(r.nextInt(2) == 0) {
                nextLoc.c = from.c + 1;
            } else {
                nextLoc.c = from.c - 1;
            }
        }

        loc.add(nextLoc);

        return(get_line(nextLoc,to)); //stack overflow error occurs here.
    }
}

Answer 1

Increase your runtime stack size via -Xss http://forums.sun.com/thread.jspa?threadID=756468

Answer 2

"to.r == from.r && to.c == from.c" never evaluates to true...

Answer 3

What is the condition that where these two parameters will be true:

if(to.r == from.r && to.c == from.c)

In my glancing through it appears that nextloc is always modified, so the statement above will never be true.

Answer 4

If you are getting a stack overflow, you probably have an infinite loop. In other words, your algorithm is never finding the "to" point. Try printing out the "nextLoc" value at the start of the method to see if it is making any progress towards getting to and from to match. Then you can try to figure out where your algorithm went wrong.

Answer 5

You may see the problem more easily if you simpify your code, it has needless duplication in it. Your rows and column manipulations can be independent

    if ( to.r > from.r ){
           nextLoc.r = from.r + 1;
    } else if ( to.r < from.r) {
            nextLoc.r = from.r -1;
    }

    if ( to.c > from.c ){
           nextLoc.c = from.c + 1;
    } else if ( to.c < from.c) {
            nextLoc.c = from.c -1;
    }

I find easier to understand than your equivalent:

    if(to.r > from.r && to.c > from.c) {
        nextLoc.r = from.r + 1;
        nextLoc.c = from.c + 1;
    } else if(to.r < from.r && to.c < from.c) {
        nextLoc.r = from.r - 1;
        nextLoc.c = from.c - 1;
    } else if(to.r < from.r && to.c > from.c) {
        nextLoc.r = from.r - 1;
        nextLoc.c = from.c + 1;
    } else if(to.r > from.r && to.c < from.c) {
        nextLoc.r = from.r + 1;
        nextLoc.c = from.c - 1;

Answer 6

You have a recursive function here. That is a function that calls itself. Every time you make a method call you add a frame to the stack. If your recursive function does not exit in a reasonable number of recursions you will run out of stack space. Thus a stack overflow. As others have said it looks like one of your conditions is always false so you will infinitely recurse (that is until you run out of stack space). This is like an infinite loop except the hardware cannot handle it so it crashes instead of just working forever.

Answer 7

First, you are seeding your random generator every time you enter the method, move:

Random r = new Random();

to an attribute of the class.

Second, it looks like if your method returns, it will only return an empty Vector because you create a new one every time.

Third, you enumerate the 8 possible directions which makes the code more complex than it needs to be, try rewriting it handling the row and columns separately, like:

if (to.c == from.c && to.r == from.r) {
    // reached destination
    return;
}

if (to.c > from.c) {
    // move right
} else if (to.c < from.c) {
    // move left
} else {
    // random step left/right
}

if (to.r > from.r) {
    // move down
} else if (to.r < from.r) {
    // move up
} else {
    // random step up/down
}

// take next step

Edit: your algorithm as it is now can only reach the to location if the last step is diagonal. If your last step is horizontal you always veer off vertically and vise versa, so you will hover around the destination ad infinitum resulting in a stack overflow. A sossible solution would be to use nextInt(3) and not veer off one third of the time.