JAVA - Stack Size - Recursion Limit

general
, ,
#1

There are many problems requiring deep recursion. Usually it’s graph problems with big limitations which are solved by DFS (or solving recurrence of Dynamic Programming recursively). But deep recursion requires large stack size, often several megabytes.

The default Java stack size is quite small. Most of the times it would give Runtime error on Codechef, SPOJ. But when I see the solutions of other user in C++ they don’t have such issue.

It results in writing non-recursive DFS which is sad itself.

Is there any way to run these recursive codes in Java without NZEC errors?

2 Likes
#2

You cannot explicitly increase the stack size. But if you could somehow manage to covert your code to end tail recursion, you are done because in end tail recursion stacking of elements doesn’t take place.

This is my aced iterative solution:

http://pastebin.com/VL8zN7ta

#3

This post was flagged by the community and is temporarily hidden.

#4

Actually there is a known way to set stack size in java.
Do it like this:

 new Thread(null, new Runnable() {
        public void run() {
            new Main().run();
        }
    }, "1", 1 << 23).start();

See this post http://codeforces.com/blog/entry/166

3 Likes
#5

Adding to other answers…

The maximum heap size can be determined by running the following command on the
corresponding platform:

Windows: java -XX:+PrintFlagsFinal -version | findstr HeapSize

Linux/MacOS: java -XX:+PrintFlagsFinal -version | grep HeapSize

#6

I am explicitly not looking for DFS. I know iterative version of DFS. My question is there any way to run those recursion codes in Java without getting NZEC errors. I mean recursive codes like in C++ not changing it to iteration.

#7

@ankurverma1994
can you share that c++ code.

#8

@arpit728 I don’t think you are getting my point. I am saying the recursive solution in Java gives NZEC whereas same code gets AC in C++. DFS is an example of such recursive codes.
You can look at some codes

Java NZEC(recursive code)

Java AC(iterative)

C++ AC (recursive)

#9

Similarly, there are many such examples like dynamic programming problems where recursive solution results to NZEC error. So I have to write iterative version of it. But when I see solution of users in C++ there recursive solution gets AC.