macOS java stack overflow error

[seventeen]

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

 

[lee1210]

how deep is the call stack when your program crashes? If i count right, only 5 pointers are getting put on the stack with each call... i don't know if the JVM always uses 32-bit pointers, 64-bit pointers, etc. (i guess you're not supposed to know/care). I don't know what the JVM's default stack size is... but even if it was just 1MB, you'd have 25 or so calls before you exhausted the stack. Some of what i just read suggests it's only 256K (that seems crazy, but maybe that's right), so you may try setting it higher with -Xss=8m (for 8 megabytes, this may be too much, just an example) and see if you have more luck. Otherwise you may need to use a "trampoline" system to call your method, and have some means of telling the caller you've reached a base case. If you have not, it would be called again with new parameters, etc. That way you're only pushing and popping one stack frame over and over instead of diving 100 levels deep, etc.

-Lee

 

[gnasher729]

Is the recursion intentional? And you realise that if you had gazillions of stack space, your method would never return anything but an empty vector of locations?

(Proof: The method has two return statements. The first return statement returns an empty vector. The second return statement returns the result of recursive call. It follows by induction that every execution with a maximum call depth of N will return an empty vector, therefore every execution that returns at all will return an empty vector).

 

[lee1210]

gnasher raises a very good point. I think making loc static might resolve this. The arguments for doing this recursively and not simply using a while loop must be pretty sparse, though. Is recursion a requirement of the assignment? If so, is the distance between the initial from and to strictly bounded?

 

[chown33]

The fundamental design error is that there's no code that accumulates locations in any Vector. It needs to accumulate locations, not create myriad single-location Vectors.

Pass the Vector as a parameter and append a location.

Or if get_line() is specified to take 2 location args and return a Vector, then it needs to be written so it accumulates the contents of a recursively returned sub-Vector to its returned Vector. See Vector.addAll(). This would be tail-recursion.

http://en.wikipedia.org/wiki/Tail_recursion