Please subscribe to the official Codeforces channel in Telegram via the link ×

KadiyalaSaiManoj's blog

By KadiyalaSaiManoj, history, 5 years ago, In English

It seems python has a low recursion Limit creating problems like runtime error. I have faced this problem in the following questions. It seems we have to use sys.setrecursionlimit().

667C - Reberland Linguistics without using sys.setrecursionlimit 18166330.

passed 18165938.

but this is also not working in some cases

445A - DZY Loves Chessboard (python3 runtime-error with limit set) 18166280.

(python2 same code) 18166286

Can anyone shed some light over this topic

did anyone face similar problems with python and why python3 is failing and python2 is passing with eventhough i set recursionlimit explicilty.


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

5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anybody with the same problem or similar problem share it here please.

5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There's another reason why you should switch to C++ ;)

5 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it


Yes, Python has huge problems with recursion limit.

The problem — as far as I remember — is that Python just dies (at least in Windows environment) if some internal stack overflows. There is no warning about it. If my memory service me right you don't even get error message when python thread self-terminates.

To prevent this from happening, there is such thing as sys.setrecursionlimit(X), which will prevent your program from going deeper then X. In this case Python will not self-terminate, but will pop up with error. Which is better. Default parameter X is 1000.

Problem with this approach is that you can still kill python even with low recursion limit if each level of your recursion uses too much stack. Also even if you set sys.setrecusionlimit(1000000) you will not get 1000000, you will just hit stack constraint and python will self-terminate.

I am not sure if I am correct, but it seems that to really increase stack you need to recompile python itself.

So, summing up you have three options:

  • switch to C++
  • switch to Java
  • unroll recursion if you suspect it to go deeper then 1,000 iterations or if it has large stack footprint.

EDIT — noticed your question on Python 2 vs 3. Don't know — possible differences — Python 3 can have larger stack footprint or lower stack space. As explained above setrecursionlimit is just a safeguard and will not prevent code from crashing.

5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Found a solution which works , i dont know if any python user uses this.
For 427C - КПП i have submitted two solutions,
First  18375514 , This submission is not passing due to recursion limit, i have seen submissions in python and many had this problem
Second   18376027. Here i have used threads to make heap size larger. this passes.
Hope this helps.