### TheNoOneCoder's blog

By TheNoOneCoder, history, 2 months ago,

I was doing this problem in python. I am receiving Runtime error on test 3 with exit code -1073741571. I am not able to understand the fault in my code. Any help is greatly appreciated.

The main part of the code is below:

cnt = 1
d = defaultdict(lambda:0)
travesal = []
subtreesize = defaultdict(lambda:0)

def dfs(node,parent):
travesal.append(node)
ans = 1
if child==parent:
continue
d[child]=cnt
cnt+=1
ans+=dfs(child,node)
subtreesize[node]=ans
return ans

n,q = li()
p = li()
adj = [[] for i in range(200002)]
for i in range(len(p)):
# print(p[i]-1)
dfs(0,-1)
for i in range(len(travesal)):
travesal[i]+=1
for i in range(q):
u,k = li()
u-=1
dis = d[u]
x = dis+k-1
# print("x",x)
if x>=len(travesal) or subtreesize[u]<k:
print(-1)
else:
print(travesal[x])


• +15

 » 2 months ago, # |   0 Auto comment: topic has been updated by TheNoOneCoder (previous revision, new revision, compare).
 » 2 months ago, # |   +22 You are getting stack overflow.The problem here is that sys.setrecursionlimit(10000) does not directly mean you can actually reach a recursion depth of 10000. CPython and PyPy both internally use the standard stack for recursion, which by default is pretty tiny. C++ would have the same problem too, but it doesn't because of the compile flag --stack=268435456.So how do you get around this in Python? A while back made this bootstrapper to completely get around any issues with deep recursion. The way it works is kind of weird but it is pretty easy to use. Here is your submission getting AC using it 118526672.
•  » » 2 months ago, # ^ |   0 Thanks a lot brother
•  » » 2 months ago, # ^ |   +5 Hi pajenegod, can you please tell me how to remove runtime error from my Codejam Round 2 C problem. My code link. My code also uses recursion.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +18 Here is how to use the bootstrapper in your case def find(l, r, val, inde): if l >= r: return 1 x = inde[val][br(inde[val],r) - 1] return comb(r-l,x-l) * find(l,x-1,val,inde) * find(x+1,r,val+1,inde) % mod switch it to @bootstrap def find(l, r, val, inde): if l >= r: yield 1 x = inde[val][br(inde[val],r) - 1] yield comb(r-l,x-l) * (yield find(l,x-1,val,inde)) * (yield find(x+1,r,val+1,inde)) % mod 
•  » » » » 2 months ago, # ^ |   +5 Thanks man, you are a python GOD
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +8 Dear sir pajenegod,I have a question, Which one is faster recursion code vs iterative code(bootstrap on that recursive code)I ran two codes in pypy3First recursive code: recursive It takes around 0.04 seconds every time I runSecond iterative code of the same recursive code(using bootstrap): iterative It takes around 0.4 seconds every time I runThe iterative code using bootstrap is slowing 10 times. So my question is does the bootstrap slow down the code. Or I am making some mistake.Also please tell us how to fasten bootstrap. The bootstrap is very fine library for large recursions. So I wanted to know how to optimise it.Thank you in advance for spending your precious time.
•  » » » » » 7 weeks ago, # ^ |   +6 The bootstrapper definitely slow things down. I've never suggested that it runs fast compared to native recursion. The role of the bootstrapper is to get around the issue of deep recursion. It also uses far less memory compared to native recursion.However, the overhead of using the bootstrapper is still surprisingly small. When I first designed it I thought it was going to be useless because of the overhead. But to my surprise it actually works pretty well.There is always going to be a trade off between usability and overhead. If you really want to lower the overhead, you can for example try this: Bootstrapper (without decorator)from types import GeneratorType def bootstrap(to, stack=[]): 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 def fun(n): if n == 0: yield yield fun(n-1) yield for i in range(10000): bootstrap(fun(400)) Another thing is that if you are ok with even more overhead, then in Python 3 you can do this: Bootstrapper (with returns)def bootstrap(f, stack=[]): def wrappedfunc(*args, **kwargs): if stack: return f(*args, **kwargs) else: to = stack.append(f(*args, **kwargs)) while True: try: to = stack.append(stack[-1].send(to)) except StopIteration as e: stack.pop() to = e.value if not stack: break return to return wrappedfunc @bootstrap def fun(n): if n == 0: return 1 return (yield fun(n-1)) + 1 for i in range(10000): fun(400) 
•  » » » » » » 6 weeks ago, # ^ |   0 Hi pajenegod can you please tell me how to use bootstrapper in this solution since it does not have a return statement in my recursive function. Thanks in advance.
•  » » » » » » » 6 weeks ago, # ^ |   0 There are a lot of examples in this blog already. You should be able to learn from that. But here is your code bootstrapped 119799338.About having no return. The way Python works is that all functions have a return value. If you don't explicitly set a return value, then the function returns None. So to get the same behaviour with the bootstrapper you need to add yield None (or just yield) on the last line in the function.