Detail Discussion of RE in python on Recursion

Hey guys,

I was trying to solve Codeforces Round #435 (Div. 2) Problem B on codeForces But I got RE. Can any one please help me why I am getting RE for this solution.

I am not able to think why It’s giving RE right now, even though I increased recursion depth limit.

1 Like

Don’t think memory is issue here… right??

From what I know, recursion in python is costly and should be avoided.

Your conditions etc. seem very correct to me. I am inclined to think its because of recursion being costlier in python than in C++ (i distinctly remember @meooow saying that one should go for iterative version of seg tree, DFS etc. in python), but I got no exact proof.

Waiting for an answer :smiley:

I tried this simple code to generate worst testCase, and it’s giving me RE on local machine too… -_-

n = 100000
print n
for i in range(n-1):
    print i+1,i+2

So memory issues are ruled out, until your pc has really limited memory :stuck_out_tongue:

but not till n~22000

Will use c++ from now on… -_-

Ironically I was thinking about switching from C++ to python…lol XD

One question… costlier in terms of what?? Memory or time?? Because none of them actually crossed limit, from What I am seeing on that solution page…

1 Like

Costly in terms of time. For memory, I am not sure. We already ruled out memory issue since your PC had a lot more than 256 MB of memory and it still gave runtime error. Must be something in-built type being root of RE.

I am not sure but It may be memory issue too, because I think OS does not allow any program to use above a limit. I remember this thing from recent contest when I was writing recursion in C++ and it was giving me RE because of same. I had to run code like this to avoid it…

g++ SUMCUBE.cpp -std=c++14 -Wl,-stack_size,0x10000000,-stack_addr,0xc0000000

But at the same time, I remember when I wrote many ML related codes in Ubuntu and there system used to hang because memory limit exceeded than RAM and It started swapping with main memory which is very costly operation. But in MacOS it’s just RE

I think it’s also related to OS at some level may be… Truly I don’t have any in-depth idea about what and why it is happening…

I dont usually code on local ide, but yes memory limits exist. Eg, if you try to print numbers from 1 to 10^6 in java, you need to pass a flag “-Xdiags::Verbose” else only partial output is shown.

Here are some test submissions I made.
Without setrecursionlimit(), this code cannot go to a depth of 10000.
Using setrecursionlimit(), it does.
However a depth of 100000 results in RE.

My guess is that this comment is correct. The program exceeds the stack limit before a depth of 100000 is reached and the program is terminated with a runtime error. Perhaps this is due to the low memory limit on Codeforces (256 MB).

But memory did not cross limit, from What I am seeing on that solution page… 256 is much bigger compare to what was consumed…

Not sure what I am talking :stuck_out_tongue: but I think answer of this question is somewhere hidden in python’s implementation of recursion, I mean while they are asking for memory to OS or something, I am feeling like it’s not making sense but I don’t know how Interpretive languages are implemented… Never took any compiler courses so… -_-

Oh that’s true, I forgot to take note of the memory consumption. Although it can be that because total memory is only 256 MB, a smaller fraction of that is being reserved for the call stack.
I can’t say for sure, I too don’t know how these languages are implemented.

There are two restrictions for recursion depth. The first is the internal limit by python, which as has been noted, can be increased by setrecursionlimit(). The other is the limit on stack size enforced by the OS.

The default maximal size of the stack in many OS is 8MB, which is quite limited for deep recursion. For a depth of 100000 it means each frame can only hold 80 bytes. So even in C you can easily trigger a stack overflow by using too many local variables. Some OJs have a higher limit than 8MB (I think Codechef has too).

For interpreted languages it’s a design choice of the interpreter if it is using the OS stack for recursion or if it is building its own stack in heap memory. I think CPython is using the OS stack, while Java is not. If the interpreted language is using the OS stack, stack frames might be much larger than the memory use of the local variables, as additional context information might be stored.

To go around this limit you can increase the maximal stack size. Locally in the Linux shell you can use ulimit -s unlimited to lift the restriction on stack size for the shell. In python itself you can use resource.setrlimit() to do the same. It is however not clear whether this will work in an OJ as changing the system enviroment might be prohibited.