rahulkhairwar's blog

Stack Overflow in java for recursive function and the same code runs properly in c++
By rahulkhairwar, history, 9 years ago, In English

I was solving this question on dp and I use Java as my preferred language for programming.

But, I got a stack overflow error when I submitted the solution in Java, while the same code when converted into C++, ran perfectly fine.

Here is the Java submission : link
and here is the C++ submission : link

So, I searched on the internet and found out that Java's stack space is very less. :/
So, is there any way I could solve this question recursively in Java? I don't want to switch to C++ as I am very comfortable with Java and really like to code in it.

Java users, do you always implement an iterative version of an algorithm which could be solved recursively?

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rahulkhairwar (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Here is the trick:


class Main implements Runnable {
 static void main(...){
  new Thread(null, new Main(), "Main", 1<<28).start();
 }

 public void run() {
  // your code here
 }
}

1<<28 is the stack size, this is enough for most problems.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried this, but I'm unable to take any input in the run() method. :|

    As soon as I run the code, it throws InputMismatchException

    Screenshot : here (see line 39)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Share full code, plz (for example, in pastebin.org)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Here is the link to the code

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Your problem is that 

          new Thread(null, new SamuAndShopping(), "SamuAndShopping", 1 <<28).start();

          Creates thread and send command to run thread. It's doesn't wait until thread run() method will be executed, so you concurrenlty close input stream in main thread and you can't read anything from input.

          You have to solutions for this — move all code about input/output into new instantiated thread or use join() method of the thread for blocking main thread until new thread do its job.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            still getting Runtime error :/

            link

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
              ← Rev. 3   Vote: I like it 0 Vote: I do not like it

              Plz, RTFM about threads before writing code with threads.

              You shouldn't explicitly invoke run() in thread's constuctor. Your specified thread size wouldn't be applied.

              For every thread you have to invoke start() and then join(), as mentioned above.

              http://pastebin.com/SCDy9XEG

              → Reply