Bypass recursion limits in python

Question

I had a large issue where I needed thousands of layers of recursion, but python wouldn't let me. As I'm building this on a windows system, it also proved difficult to try and find the solution. In essence the recursion runs on the stack, and in non UNIX based systems it's hard to mess with the stack.

If you're looking for the most simple solution which works on UNIX:

import sys
sys.setrecursionlimit(20000)

However, as I mentioned, this did not work for me on windows. I needed to come up with solution or switch operating systems.

Every recursive code can be rewritten as iteration with an explicit stack. Look here https://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration — VPfB, May 17 '20 at 19:13
While self-answers are encouraged, the original question still needs to be [on-topic](https://stackoverflow.com/help/on-topic) and posed as if it were any other question. There is no question here. Incidentally, the provided answer is very likely a poor solution to the problem, as others have mentioned. See [XY problem](https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem) on meta. — ggorlen, May 17 '20 at 19:48
How would one go about rewriting a backtracking algorithm into an explicit stack? the solution i created seems much easier than managing the conversion. — Cole, May 18 '20 at 11:28
@ggorlen The question i thought was clear was how to bypass recursion limits in python on a windows system. I found a way to do that which i hadent seen posted elsewhere so i figured worth sharing. converting to it from a simple backtracking algorithm seemed more trivial and faster that converting to an explicit stack. — Cole, May 18 '20 at 11:34
That's fine, but threading has tons of overhead, for starters. Starting a new thread per call is extremely expensive. As far as the question, it never says "how do I bypass recursion limits in Python on a windows machine?" or has any other question to speak of. Lastly, `sys.setrecursionlimit(2000)` works fine for me on windows. — ggorlen, May 18 '20 at 14:52

score 0 · Answer 1 · answered May 17 '20 at 18:32

To solve this, I had the wild idea of using multithreading to give me multiple stacks. I didn't honestly know if this would work before I tried it. I hate multithreading generally, but this is a very basic version of that. I'm sure others can improve on it. In my final product I implement multithreading into my backtracking algorithm.

import threading


def recurThread(x,y,z):
    if x <= 1:
        y.append(x)
        if z[0] != 1:
            new_y = []
            z[0] -= 1
            new_t = threading.Thread(target=recurThread, args=(900, new_y, z))
            new_t.start()
            new_t.join()

            y += new_y
        else:
            return

    y.append(x)
    return recurThread(x-1, y, z)


y = []
z = [50]
x = threading.Thread(target=recurThread, args=(900, y, z))
x.start()
x.join()
total = 0
print(len(y))
for i in y:
    total += i

print(total)

This is the basic idea. Things to note are that if you want to get values back from the threads, you need to store them (and pass them) as mutable objects like lists.

The other thing to note if you're unfamiliar with threads (like I was) is that you need to .start() your thread. More importantly, .join() will wait for the thread to finish before continuing. This allows for the program to be run normally, just with this instance of a thread allowing you to cheat the stack limit.

IMO using extra threads as a way to get extra stack space is... a bit bizarre. No doubt, you could make it work, but every time you show it to another programmer, you'll have to explain it all again. Probably a better solution would be to re-write your algorithm to use an explicit operand stack instead of using recursion. It's more _scalable,_ and everybody will understand what you did, and why you did it. — Solomon Slow, May 17 '20 at 18:38
Bizarre as it may be, it works flawlessly. Just an alternative for anyone looking for a different solution. Also, using an explicit operand stack I promise you'll still have to explain the why. As I mentioned, this was integrated into a backtracking algorithm. This approach was much simpler to me than attempting to rewrite that. — Cole, May 18 '20 at 11:26

Bypass recursion limits in python

1 Answers1