Reputation: 1531

java stackoverflow error

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

Upvotes: 0

Answers (7)

rsp

Reputation: 23373

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.

Upvotes: 0

Jason Tholstrup

Reputation: 2056

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.

Upvotes: 1

djna

Reputation: 55897

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;

Upvotes: 0

Peter Recore

Reputation: 14187

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.

Upvotes: 1