### Moody_in_a_hoodie's blog

By Moody_in_a_hoodie, history, 3 years ago, 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.  Comments (9)
| Write comment?
 » 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) Spoilerfrom types import GeneratorType def bootstrap(f, stack=[]): def wrappedfunc(*args, **kwargs): if stack: return f(*args, **kwargs) else: to = f(*args, **kwargs) while True: if type(to) is GeneratorType: stack.append(to) to = next(to) else: stack.pop() if not stack: break to = stack[-1].send(to) return to return wrappedfunc 
•  » » 3 years ago, # ^ | ← Rev. 2 →   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.
•  » » » 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.
•  » » 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@bootstrap def recurse(n): if (n < 2): yield n yield recurse(n-1) + recurse(n-2) print(recurse(20)) 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@bootstrap def recurse(n): if (n == 0): yield 1 yield recurse(n-1) Is there something obvious I'm missing?
•  » » » 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@bootstrap def recurse(n): if (n < 2): yield n yield (yield recurse(n-1)) + (yield recurse(n-2))  Example 2@bootstrap def recurse(n): if (n == 0): yield 1 yield (yield recurse(n-1)) 
 » Note that tail call optimization doesn't work in Python.
 » Here is a version of your solution getting Accepted: 86938135The 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.
•  » » 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 :)
•  » » This code gives Memory limit exceeded in pypy3. You have any trick for pypy3?