java.lang.StackOverflowError

[Will]

This is partially a question and partially a rant. I am currently
running Sun's SDK/JRE 1.3.1 on a Windows XP machine with 512MB of
toatl RAM. I have a program which requires a lot of recursion since
the linked lists that it operates on are very long (8192 elements
apiece). These linked lists are generated from text files that are
all the same size (same number of columns and rows, all containing
either zeros or ones. I'm implementing a Quine-McClusky algorithm for
reducing boolean functions from exhaustive input/output lists.) My
problem is a few of these files seem to consistently cause a
StackOverFlowError while some do not. Since they are the same format
and the same number of characters, why would one be different than
another. Out of eight generated files (8bit x 8bit inputs -> 8
subfiles of 8192 lines each) six work fine, and two cause the error.
I found a work-around by increasing the stack size using java.exe
-Xss65536K but why is this only needed on two of the eight files? To
note, this exception occurs after I have read in the 8192 lines,
tagged each with a line number, and then perform a count on the number
of lines. I print this out so that I have a running tally of how many
lines I have left relative to the start of the program. My counting
method looks like:

1) public int countNodes(){
2) if(next == null)
3) return 1;
4) else
5) return next.countNodes()+1;
6) }

Predictably, it always fails on line 5.

Befuddled....
-Will

 

[Jezuch]

U¿ytkownik Will napisa³:

1) public int countNodes(){
2) if(next == null)
3) return 1;
4) else
5) return next.countNodes()+1;
6) }

Predictably, it always fails on line 5.

Recursion on lists looks suspicious. Is it absolutely necessary?

 

[Chris Uppal]

1) public int countNodes(){
2) if(next == null)
3) return 1;
4) else
5) return next.countNodes()+1;
6) }

Predictably, it always fails on line 5.

I can't address the problem of why if fails on some files rather than others,
but I have to ask:

Why are you using recursion for something so simple ? Converting the above
into an iterative loop is trivially simple, entirely natural, and -- most
importantly -- it will then run in bounded space instead of space (stack size)
proportional to the length of the list.

public int
countNodes()
{
int count = 0;
Node each = this;
while (each != null)
{
count = count + 1;
each = each.next;
}
return count;
}

-- chris

 

[Eric Sosman]

[...] My counting
method looks like:

1) public int countNodes(){
2) if(next == null)
3) return 1;
4) else
5) return next.countNodes()+1;
6) }

Predictably, it always fails on line 5.

That's pretty much as expected if the lists are
long, because there's a new nested method invocation
for every node. Try an iterative approach instead,
something along the lines of:

public int countNodes() {
int count = 1;
for (Node node = next; node != null; node = node.next)
++count;
return count;
}

 

[Tim Ward]

1) public int countNodes(){
2) if(next == null)
3) return 1;
4) else
5) return next.countNodes()+1;
6) }

"Do not use recursive algorithms on real-world data" is something one
frequently has to teach computer science graduates starting their first
jobs.

 

[Adam Jenkins]

"Do not use recursive algorithms on real-world data" is something one
frequently has to teach computer science graduates starting their first
jobs.

Not true at all, that's just silly superstition, caused by people who
learn techniques by rote without really understanding why they work or
where they're appropriate. You just need to understand your algorithm
well enough to know how deep the recursion will go, and whether
recursion is really an appropriate solution. Take a look at the
std::map implementation in your C++ library, or Sun's java.util.TreeMap
implementation and you'll see recursive functions. There are plenty of
problems where a recursive solution is more elegant than an iterative
solution, and where the iterative version would have the same order of
memory requirements as the recursive version.

Also, you need to realize that some functional languages, such as Scheme
or ML, guarantee that tail-recursive function calls will be optimized
away into iteration, whereas Java or C/C++ make no such guarantees. So
while it's completely reasonable and portable to use recursion to
iterate over a list in Scheme or ML, Java or C++ programs should use
iteration for that, since most compilers for these languages don't
optimize away tail-recursion.

 

[Tim Ward]

Not true at all, that's just silly superstition, caused by people who
learn techniques by rote without really understanding why they work or
where they're appropriate. You just need to understand your algorithm
well enough to know how deep the recursion will go, and whether
recursion is really an appropriate solution.

Exactly. But until people have learnt how to do that, telling them not to
use recursion without thinking about it is a good starting point.

 

[Adam Jenkins]

Exactly. But until people have learnt how to do that, telling them not to
use recursion without thinking about it is a good starting point.

This is a very different statement from the one I was responding to.
The way I understand your original statement (quoted above), you were
basically saying that recursion is just an academic technique which
isn't applicable to real-world problems. This is a seriously misleading
statement to make, since there are many real problems where a recursive
solution really is the best solution.

Now you're softening your statement to just say that people who don't
understand recursion shouldn't use recursion. Well, I guess I can agree
with that, but what are they going to do if they need to implement some
kind of tree search algorithm for instance? They're going to have to
learn about recursion. Suppose someone created a database table with a
lot of records, and didn't put indexes on the right columns, so queries
were taking too long. I assume you wouldn't respond by recommending
that people shouldn't put lots of rows in a table. Rather, you'd say
they need to learn about indexes and SQL queries. Similarly, recursion
is too basic and valuable a technique to just state that it should never
be used, just because it's possible to misuse it through ignorance.