Recursion depth in java

[poulius]

Hello,

I have a racursive function in my program code. My program stops when recursive function calls itself 1838th time. I get:
Exception in thread "main" java.lang.StackOverflowError
at java.nio.CharBuffer.<init>(Unknown Source)
at java.nio.HeapCharBuffer.<init>(Unknown Source)
at java.nio.CharBuffer.wrap(Unknown Source)
at sun.nio.cs.StreamEncoder$CharsetSE.implWrite(Unkno wn Source)
at sun.nio.cs.StreamEncoder.write(Unknown Source)
at java.io.OutputStreamWriter.write(Unknown Source).....
...

Is it possible to expand the recursion depth in java?

Thank You

[Eranga]

May be you are working on some collection framework, is it? If so what it is? Must capable to grow the size dynamically.

[poulius]

Thank You for the answer.
No I am not using any frameworks.

[Eranga]

Can you show your code segment here to see.

Did you try to change the stack size, with -Xss. I never wants to change this before, so haven't hands dirty on this.

[Fubarable]

Your recursive method likely has a faulty stopping condition, and hence the stack overflow. You'll need to step through your logic to figure out where it is wrong.

[Eranga]

Why I worried about collection frameworks is, using recursion on such is really annoying. Most of the time you cannot avoid this exception in larger applications which are deal with large number of data. Better to avoid recursion if so.

[poulius]

It is rather difficult to explain my algorithm. But I will try :)
I have virtual network of nodes. For example the network of 5 nodes ( A, B, C, D and E ) where:
A is connected to B and C;
B is connected to A and E;
C is connected to A;
D is connected to E;
E is connected to A, B and D;

A---------B
| | |
| | |
C E
|
|
D

My task here is to find average times of hops from all nodes of pairs. For example I am going randomly from A to B, from A to D. To go from A to D I can get two hops ( A -> E -> D ) or three hops ( A-> B -> E -> D) or four hops ( A -> C -> A -> E -> D).
My algorithm works perfect for small networks, but when I have a network of 20 nodes I get :

Exception in thread "main" java.lang.StackOverflowError
at java.nio.Buffer.limit(Unknown Source)
at java.nio.Buffer.<init>(Unknown Source)
at java.nio.CharBuffer.<init>(Unknown Source)
...............

A part of my code.
Loop in loop ( this.n is the size of the network ):
for (int i=0; i < this.n; i++) {
for (int j=0; j < this.n; j++) {

int ii = i;
int jj = j;

//this.counter = 0;
count = 0;
policy1(i, j, ii, jj, k, count);
count = 0;
}
}


public void policy1(int i, int j, int ii, int jj, int k, int count) {

if (i != jj) {
int setSize = neighbours[i].size();
r = randomNumber(0, setSize);
count++;


g = (Integer)neighbours[i].get(r);

if (count > 1400)
System.out.println(count);
policy1(g, j, ii, jj, k, count);
}
else {
this.hopsMatrix[k][ii][jj] = count;

count = 0;
}
}

[neilcoffey]

Without following all of the details of what you're doing, if I understand you correctly, the maximum recursion depth that you'd expect is essentially the number of nodes (minus 1). So if you're doing more recursions, it sounds like you're following paths round in a loop. When you choose the next node in your random path through the network, how are you making sure it's not a node already visited?

[poulius]

I have to implement several algorithms. One of them is not allowed to visit already visited nodes. In this case the maximum depth is n-1. But the second algorithm ( maybe better to call it policy ) is allowed to visit every node as much times as I want. I going in the network randomly. I can go from A to B, than back from B to A, again from A to B and finally from B to C. So there could be thousands of hops in 20 nodes network.

[neilcoffey]

OK, if you're sure your algorithm is correct, then you have a few options:
- just increase the stack size of the thread that's running the algorithm
- makes the variables that you pass to each invocation take up less space on the stack
- last resort that I don't think should be necessary: don't actually use recursion, but run your algorithm in a loop and implement your own stack.
To increase the stack size, you can either:
- add -Xss4m (for example, to set to 4 MB) to your Java command line -- this will set the stack size for ALL threads in your program -- I think this should be enough for a depth of tens of thousands
- call your method inside its own Thread, to which you pass a stack size for that single thread (see Thread constructor)
Each variable to the method takes up 4 bytes on the stack (unless they're longs or doubles). So you could save space by, e.g. packing two node numbers into a single int, or even 4 byte-sized values into a single int. In principle, each local variable also takes up a similar amount of memory, so if javac/your JIT compiler doesn't already make this optimisation, you'll get a slight saving by writing "r = randomNumber(0, neighbours[i].size())" as one line.
But if you are sure your algorithm is not flawed and you don't care about it taking up a lot of memory for the stack then I think you can just set a massive stack size and not worry about doing anything fancier.

[poulius]

wow thank you for ideas.
I tried to increase stack size, but it did not help me. I am using eclipse, so I defined in eclipse.ini file . My eclipse.ini file looks:
-showsplash
org.eclipse.platform
--launcher.XXMaxPermSize
1024M
-framework
plugins\org.eclipse.osgi_3.4.2.R34x_v20080826-1230.jar
-vm
C:\Program Files\Java\jdk1.5.0_17\bin\javaw.exe
-vmargs
-Dosgi.requiredJavaVersion=1.5
-Xss4m
-Xms80m
-Xmx512m

Maybe here is something wrong?

[CJSLMAN]

Have you tried running from the command prompt ? Any differences ?

Luck,
CJSL

[neilcoffey]

No, it's not the eclipse ini file you need to change. When you go to run your project (as I recall, via the "Run As" menu option), there should be a whole window that appears allowing you to change various runtime options, including "VM parameters" or some such like. That's where you need to add the -Xss option.

[poulius]

I connot increase stack size. I tried to write -Xss4m or -Xss8m, but I get the error at the same place. I mean the program stops at the same depth of recursion.

I tried to do the mistake, I wrote -Yss4m, I got the error "Could not create Java virtual mashine". I did this only to check if my program reacts to this variable. I did not get error when I write -Xss4m.

This is screenshot: saltupys.lt/xss.jpg

[neilcoffey]

What you're typing looks OK. I did a quick test in Eclipse myself and it appears to work -- setting the stack size to, say, 2m increases significantly the possible recursion depth.

Can you tell us EXACTLY which line you're getting the stack overflow error on -- in your example, you appear to be getting it when you do println(), but that was just debugging, wasn't it? If you take that out, where do you get the error, and what depth of recursion does it get to?

[poulius]

Yes, that "println" was just debugging. I get the overflow error on the line where method invokes itself, that is :
policy1(g, j, ii, jj, k, count);

First of all the recursion was stopping at 1450 ( I do not remember prcisely the numnber ). Now I reduced the number of variables in method and recursion stops at 2674 time invoking itself ( everytime the same number ).

If take out the code where the error occurs, than the program of course works without errors, but than the program does not go through my network.

[neilcoffey]

If Eclipse is messing you about, you can always just create a new thread to run your method in with the stack size you want:

Runnable r = new Runnable() {
  public void run() {
    runMyMethod();
  }
};
long stackSizeBytes = 4 * 1024 * 1024;
Thread thr = new Thread(null, r, "My Thread", stackSizeBytes);
thr.start();
thr.join();

[poulius]

Thanky You very much, neilcoffey. The last thing works for me :) . Of course I am very thankful for all of you who helped to manage my problem