Moody_in_a_hoodie's blog

Python can't handle deep recursion even after setting the recursion limit
By Moody_in_a_hoodie, history, 4 years ago, In English

for context: problem link :link

my solution :link

Got RE in 35th case the python AC submissions for this problem are executed using bfs. I looked at some AC submissions in c++. looks like the logic is same. So the problem I guess is with python.

lets say I avoid recursive implementation and go for iterative ones..for example Bfs over dfs. but is it even possible in all cases? And also if you can provide a feasible way to execute deep recursions without runtime error I will be extremely grateful.

Please don't suggest to learn C++ right now. I know it is a great language. But I just can't afford the time now. I am currently working on learning new skills that will help me in web dev. I hope you understand my position.

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

Comments Comments (12)
| Write comment?
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Yes, there is a way to use recursions in python without stack overflow. Put below snippet in your code and then put @bootstrap over recursive function. And replace instances of return with yield. (Credit goes to pajenegod)

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

    It was accepted in no time. thank you!! But i also needed do a slight modification. ~~~~~

    def dfs(node,m):
    visited[node]=1
    if a[node-1]==1:
        m=m+1
    else:
        m=0
    if m>k:
        yield 0
    for v in g[node]:
        if visited[v]!=1:
            yield dfs(v,m) #it was just dfs(v,m) before
    if node in leaf:
        leaf[node]=1
    yield 1

    ~~~~~ without the modification yield was stopping the complete process if it was hitting the leaf node. So now it works. But the same modification if i do on a normal recursion the program is giving WA even for smaller values. I think it has to do something with being stackless. I am keeping this here just so that everyone keeps in mind some slight changes may be needed to be done if you use this version. Thanks again though. :) i am gonna use this code from now on.

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

      Yes, you are right you have to use yield for accepting results from recursion call also. You can refer to examples in the below comment.

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

    I'm trying to get this to work but can't seem to, trying to make it work with some very simple recursive functions and I just get errors. The following code gives me TypeError: unsupported operand type(s) for +: 'generator' and 'generator' on both python 2 and 3:

    fibonacci recursive function

    An even more trivial function that dodges the above error will still error out with File "main.py", line 18, in wrappedfunc to = stack[-1].send(to):

    trivial recursive function

    Is there something obvious I'm missing?

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

      Actually you have to use yield for accepting results from the recursive call as well for returning the value also. It will be more clear from these examples.

      Example 1
      Example 2
      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Note that tail call optimization doesn't work in Python.

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

Here is a version of your solution getting Accepted: 86938135

The solution is wrapped into a function.
This function is run in a new thread.
Before that, the stack limit for new threads is updated.

The trick of starting a new thread to control the stack size in the contests is old.
I first saw it used for Java some time around 2010.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Wow that's really simple and clever!!

    I am so glad I asked this question here. somehow when I searched it on google all answers were like switch to c++ or set recursion limit. But now when I dig deeper specially in codeforces blogs I found the topic of threading mentioned but very vague. All this blogs were about getting stuck on a specific problem statement. So I did not click on it before.

    its sad that even it is an old trick its not very well known as no blog/resource actually exists dedicated to this topic. Thank you so much for answering :)

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

    This code gives Memory limit exceeded in pypy3. You have any trick for pypy3?

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

    how can I use this for multiple test cases? I have no idea about threading and how it works. I am very new at this

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

      Perhaps you want to create a thread once, then solve the problem inside (one test case or many test cases, does not matter).

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

        Hey man sorry for bothering you again. But experimented a little with threading. At first, i was getting runtime error on test case 7. With threading it has improved but its still getting runtime error in test case 10. Can you please help me? Is it possible to optimize it more?

        My solution: https://codeforces.net/contest/1843/submission/266921446

        → Reply