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

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?
-- 
Ecce Jezuch
"Do unto others what has been done to you (...)
Do unto you now what has been done to me." - M. J. Keenan

Will wrote:

> 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

Will wrote:
> 
> [...] 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;
	}

-- 
Eric.Sosman@sun.com

"Will" <larkmore@aol.com> wrote in message
news:5faf6114.0401091226.452f0b8a@posting.google.com...
>
> 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.

--
Tim Ward
Brett Ward Limited - www.brettward.co.uk

Tim Ward wrote:
> "Will" <larkmore@aol.com> wrote in message
> news:5faf6114.0401091226.452f0b8a@posting.google.com...
> 
>>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.

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.

"Adam Jenkins" <adam@remove.thejenkins.me.org> wrote in message
news:4004546C.4050005@remove.thejenkins.me.org...
> Tim Ward wrote:
> > "Will" <larkmore@aol.com> wrote in message
> > news:5faf6114.0401091226.452f0b8a@posting.google.com...
> >
> >>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.
>
> 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.

--
Tim Ward
Brett Ward Limited - www.brettward.co.uk

Tim Ward wrote:
> "Adam Jenkins" <adam@remove.thejenkins.me.org> wrote in message
> news:4004546C.4050005@remove.thejenkins.me.org...
> 
>>Tim Ward wrote:
 >>>
>>>"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.
> 
> 
> 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.