filo's blog

Python solution using DFS gets RTE even with sys.setrecursionlimit set to a high number
By filo, history, 6 years ago, In English

Hi,

Relatively new to Python,

Here are two solutions one gets run time error another one gets accepted, basically the difference between two is that the first one uses DFS and the second one BFS. I know Python has limited stack size by default, that's why I increased it to 2000000, but didn't help, any idea why?

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You need to increase the stack size as well. on top of your code add these 2 lines

import threading

threading.stack_size(2**26)

And call your main function in the end of your code by using the line,

threading.Thread(target=main).start()

If you still get RE, increase the stack size to 2**27 or 2**28, or if you get TLE then decrease it to 2**25 or 2**24 Hope this helps

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

Firstly your BFS solution is definitely not a BFS, it is still a DFS, just written using your own stack. To get BFS you need to use collections.deque with append and popleft...

About recursion in Python, it sucks

Here is the thing, deep recursion in Python just doesn't work. To my understanding Python uses pretty large stack frames, so the stack is going to get filled up very quickly, also Python doesn't do any kind of tail call optimization. So you just simply can't do deep recursion in Python.

The recursion limit is just Pythons way of dying nicely (giving a catchable exception) instead of crashing. So increasing the limit is pretty much just going to make your code go from dying from an exception to crashing. The default limit is set to a 1000 for a reason.

So what if you still want to do deep recursion in Python? The only thing I found feasible is to manually do it with your own stack. Like what you did in your second solution. It's not pretty but that is the only thing I've found to work and be reasonably fast. One nice thing is that this means that you can switch between BFS and DFS without having to change much of the code.

→ Reply