Stack Overflow Error java

Question

I'm trying to solve a problem that calls for recursive backtracking and my solution produces a stackoverflow error. I understand that this error often indicates a bad termination condition, but my ternimation condition appears correct. Is there anything other than a bad termination condition that would be likely to cause a stackoverflow error? How can I figure out what the problem is?

EDIT: sorry tried to post the code but its too ugly..

It would help if you posted what problem you are trying to solve, the code that you are currently using to solve it, and what the expected results/output is. — Thomas Owens, Jun 07 '11 at 22:31
The condition might not be bad in an abstract airy-fairy sense. But it needs too many recursive calls to resolve itself within the limitations of the language and hardware. — Owen, Jun 07 '11 at 22:32
I'd like to post the code but it's a complicated problem and I'd have to post the entire text of it........ — user658168, Jun 07 '11 at 22:33
@user658168, it is your question, if you can not bother to even explain it then why should we bother answering you? — SJuan76, Jun 07 '11 at 22:35
I didn't ask you to solve my problem for me. I asked for advice on how to figure out how to solve it myself. Knowing more about what kinds of things can cause a stackoverflow error would help with that. — user658168, Jun 07 '11 at 22:38
Instrument your code to print out how many times it recurses and whether the terminate condition really is terminating (i.e., insert lots of System.out.println's in your code) — nos, Jun 07 '11 at 22:39
"Deep recursions" as in too many possibilities/calls in the recursive case? — user658168, Jun 07 '11 at 22:39
Look at: http://stackoverflow.com/questions/214741/what-is-a-stack-overflow-error — Franklin Hirata, Mar 17 '14 at 18:59

score 6 · Answer 1 · answered Jun 07 '11 at 22:41

As @irreputable says, even if your code has a correct termination condition, it could be that the problem is simply too big for the stack (so that the stack is exhausted before the condition is reached). There is also a third possibility: that your recursion has entered into a loop. For example, in a depth-first search through a graph, if you forget to mark nodes as visited, you'll end up going in circles, revisiting nodes that you have already seen.

How can you determine which of these three situations you are in? Try to make a way to describe the "location" of each recursive call (this will typically involve the function parameters). For instance, if you are writing a graph algorithm where a function calls itself on neighbouring nodes, then the node name or node index is a good description of where the recursive function is. In the top of the recursive function, you can print the description, and then you'll see what the function does, and perhaps you can tell whether it does the right thing or not, or whether it goes in circles. You can also store the descriptions in a HashMap in order to detect whether you have entered a circle.

+1. Also, I've found placing breakpoints and stepping through my code in the debug environment to be the single most effective way to debug stack overflow exceptions. — StriplingWarrior, Jun 07 '11 at 23:11
@StriplingWarrior: Of course; not sure why I forgot to mention that. Debugging gives you a very detailed view of the execution, while the method I describe gives a very convenient, quick glance at how the recursion proceeds. Doing both in combination will often be useful. — Aasmund Eldhuset, Jun 07 '11 at 23:36

score 3 · Answer 2 · answered Jun 07 '11 at 23:04

Instead of using recursion, you could always have a loop which uses a stack. E.g. instead of (pseudo-code):

function sum(n){
  if n == 0, return 0
  return n + sum(n-1)
}

Use:

function sum(n){
  Stack stack
  while(n > 0){
    stack.push(n)
    n--
  }
  localSum = 0
  while(stack not empty){
    localSum += stack.pop()
  }
  return localSum
}

In a nutshell, simulate recursion by saving the state in a local stack.

score 1 · Answer 3 · answered Feb 05 '15 at 23:45

As the other fellas already mentioned, there might be few reasons for that:

Your code has problem by nature or in the logic of the recursion. It has to be a stoping condition, base case or termination point for any recursive function.
Your memory is too small to keep the number of recursive calls into the stack. Big Fibonacci numbers might be good example here. Just FYI Fibonacci is as follows (sometimes starts at zero):

1,1,2,3,5,8,13,...

Fn = Fn-1 + Fn-2

F0 = 1, F1 = 1, n>=2

score 1 · Answer 4 · answered Jun 07 '11 at 22:44

1

You can use the -Xss option to give your stack more memory if your problem is too large to fix in the default stack limit size.

answered Jun 07 '11 at 22:44

JustinKSU

4,875
2
29
51

score 0 · Answer 5 · answered Jun 07 '11 at 22:36

0

If your code is correct, then the stack is simply too small for your problem. We don't have real Turing machines.

answered Jun 07 '11 at 22:36

irreputable

44,725
9
65
93

3

Just a nitpick: Turing machines don't do recursion, they are basically iterative. – Paŭlo Ebermann Jun 07 '11 at 23:06
Yes, but recursion is here only emulated by iteration. You should use some recursive machine model (with unlimited stack) for this assertion. (After all, most real life problems with a too small Java stack can be simply transformed in iterative versions, using the Heap instead. Of course, also the Heap may be limited.) – Paŭlo Ebermann Jun 08 '11 at 00:10

score 0 · Answer 6 · answered Jun 07 '11 at 23:20

There are two common coding errors that could cause your program to get into an infinite loop (and therefore cause a stack overflow):

Bad termination condition
Bad recursion call

Example:

public static int factorial( int n ){
    if( n < n ) // Bad termination condition
        return 1;
    else
        return n*factorial(n+1); // Bad recursion call
}

Otherwise, your program could just be functioning properly and the stack is too small.

Stack Overflow Error java

6 Answers6