Results 1 to 18 of 18
  1. #1
    poulius is offline Member
    Join Date
    Dec 2008
    Posts
    8
    Rep Power
    0

    Default Recursion depth in java

    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

  2. #2
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,371
    Blog Entries
    1
    Rep Power
    20

    Default

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

  3. #3
    poulius is offline Member
    Join Date
    Dec 2008
    Posts
    8
    Rep Power
    0

    Default

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

  4. #4
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,371
    Blog Entries
    1
    Rep Power
    20

    Default

    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.

  5. #5
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,315
    Blog Entries
    1
    Rep Power
    26

    Default

    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.

  6. #6
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,371
    Blog Entries
    1
    Rep Power
    20

    Default

    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.

  7. #7
    poulius is offline Member
    Join Date
    Dec 2008
    Posts
    8
    Rep Power
    0

    Default

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

  8. #8
    neilcoffey is offline Senior Member
    Join Date
    Nov 2008
    Posts
    286
    Rep Power
    7

    Default

    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?

  9. #9
    poulius is offline Member
    Join Date
    Dec 2008
    Posts
    8
    Rep Power
    0

    Default

    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.

  10. #10
    neilcoffey is offline Senior Member
    Join Date
    Nov 2008
    Posts
    286
    Rep Power
    7

    Default

    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.
    Last edited by neilcoffey; 01-03-2009 at 04:19 AM. Reason: Extra info; typos

  11. #11
    poulius is offline Member
    Join Date
    Dec 2008
    Posts
    8
    Rep Power
    0

    Default

    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?

  12. #12
    CJSLMAN's Avatar
    CJSLMAN is offline Moderator
    Join Date
    Oct 2008
    Location
    Mexico
    Posts
    1,159
    Rep Power
    8

    Default From command prompt?

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

    Luck,
    CJSL
    Chris S.
    Difficult? This is Mission Impossible, not Mission Difficult. Difficult should be easy.

  13. #13
    neilcoffey is offline Senior Member
    Join Date
    Nov 2008
    Posts
    286
    Rep Power
    7

    Default

    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.

  14. #14
    poulius is offline Member
    Join Date
    Dec 2008
    Posts
    8
    Rep Power
    0

    Default

    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

  15. #15
    neilcoffey is offline Senior Member
    Join Date
    Nov 2008
    Posts
    286
    Rep Power
    7

    Default

    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?

  16. #16
    poulius is offline Member
    Join Date
    Dec 2008
    Posts
    8
    Rep Power
    0

    Default

    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.

  17. #17
    neilcoffey is offline Senior Member
    Join Date
    Nov 2008
    Posts
    286
    Rep Power
    7

    Default

    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:

    Java Code:
    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();

  18. #18
    poulius is offline Member
    Join Date
    Dec 2008
    Posts
    8
    Rep Power
    0

    Default

    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

Similar Threads

  1. java program for recursion
    By oshiru in forum New To Java
    Replies: 4
    Last Post: 11-27-2008, 05:34 AM
  2. Recursion in Java ..
    By Java01 in forum New To Java
    Replies: 6
    Last Post: 10-24-2008, 12:42 PM
  3. i could not get the recursion in java
    By sivasayanth in forum New To Java
    Replies: 3
    Last Post: 04-23-2008, 09:08 AM
  4. Replies: 0
    Last Post: 04-09-2008, 07:44 PM
  5. Recursion in java
    By lenny in forum Advanced Java
    Replies: 1
    Last Post: 08-07-2007, 07:23 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •