### Moody_in_a_hoodie's blog

By Moody_in_a_hoodie, history, 4 weeks 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.

• +16

 » 4 weeks ago, # |   +8 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 
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » 4 weeks ago, # ^ |   0 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?
•  » » » 4 weeks ago, # ^ |   0 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))