Is there a generic way to make deep recursive functions work without changing system recursion limit?

Question

We have a Python codebase containing quite a lot recursive functions, they may run into deep recursions and break the recursion limit with default Python interpreter settings. We have used sys.setrecursionlimit() to make them work well in the past. But now these functions need to be put into a shared module and run in other user's environment. We realized that calling sys.setrecursionlimit() within the shared module's code may not be a good idea, because that will change our user's global setting. Even if we always change the setting back before the functions return, users may be running a muti-threaded program and call our functions just in one of the threads, they may not want the other threads to be affected by a setting change. (If I'm wrong with this understanding, please correct me)

So, we are expecting for some approaches that can make our recursive functions work, while keeping the system recursion limit unchanged.

Before asking this question, I've searched the Internet and found a lot of information. They are really useful, I can get two conclusions from those resourses by now:

1. If possible, use sys.setrecursionlimit() to change recursion limit, or use tricks like context manager to change this setting and then revert back. -- As said before, we don't think this is the best choice for a shared module.

2. Change resursive functions' code into iterative. Most of the posts suggest changing code manually, by studying the functions first, and then refactor them case by case. This is possible but it needs substantial manual work, as our codebase is not small, and some recursive functions are quite complex. This post shows an example of how tough it can be to change a complex recursive function into iterative. But of course, we will rely on this last resort if we have to, but now we are finding some other generic way.

When saying "generic", I mean that only simple changes are needed, without deep understanding of the functions' logic and designing iterative code thoroughly by hand. "Generic" here does not imply small code change, it means more about less manual work, or, "automatic".

In some posts, I found that tail recursions can be eliminated by using a library named TCO. Thus all tail recursion functions can be changed just by adding a decorator and doing some generic text replacement. This is very close to the solution we are looking for. I also learned trampoline which applys to tail recursions as well. However, our codebase includes not only tail recursions.

Here is the question: Without calling sys.setrecursionlimit(), is there a way to make deep recursive functions (not only tail recusive functions) work, with minimum manual effort to change the legacy code? Is there any automatic refactoring tool that can do this?

Answer 1

If you're using Python3, and the recursive functions contain no yield expression for now, there is a generic way by just changing every recursive function call with yield added, and using an executor function as client code's invoking entry point. After modification, the orginal call stack of interpreter will be replace by an explicit list (only for the functions modified), and recursion limit only depends on the maximum size of a list.

Pre-Knowledge about yield expression

Let's take an example to see the function of yield first:

def func():
    y = yield 1
    return y


f = func()

try:
    x = next(f)
    print(x)
    f.send(x + 1)
except StopIteration as e:
    print(e.value)

When a function contains a yield expression, the return value of the function automatically becomes a generator. Note the f = func() line, which looks like it's executing the code in the func function, but it doesn't, it just returns a generator that contains the parameters and states of the func function, but doesn't execute any line inside func.

This is important, and this feature will be used to eliminate recursive calls.

After next(f) is executed in the subsequent try block, the code in func is actually executed. next causes func to run from the entry until the yield expression is encountered. In this case, the value following yield is assigned to x as the return value of next(f), and the execution of func is suspended at yield 1.

f.send(x + 1) passes the value of x + 1 to where func function was last paused and lets func continue execution from that place. Inside func, x + 1 is assigned to y as the value of yield 1, then return y is executed.

Instead of returning a value, return y in func throws a StopIteration exception. The value attribute in the exception object contains the value following return. Therefore, after the return statement is executed, execution will enter into except StopIteration as e: code block. At last, the return value 2 is printed.

Modification of recursive functions

Suppose that we have a recursive function like this:

def recursive_add(x):
    return 0 if x == 0 else x + recursive_add(x - 1)

through using yield, we modify the previous recursive function as follows (with an executor function and calling example also added):

def recursive_add(x):
    return 0 if x == 0 else x + (yield recursive_add(x - 1))


def run_to_finish(gen):
    call_stack = [gen]
    return_value = None  # Return value of the function at the innermost level

    while call_stack:
        try:
            if return_value is not None:
                inner_call = call_stack[-1].send(return_value)  # Transfer the return value of the inner function to the outer
            else:
                inner_call = next(call_stack[-1])  # The function is just being executed or does not require a return value
            call_stack.append(inner_call)
        except StopIteration as e:  # Inner function exit
            del call_stack[-1]
            return_value = e.value  # Obtains the return value

    return return_value


print(run_to_finish(recursive_add(10000)))

The only difference between modified recursive_add and the original one is that a yield keyword and a pair of parentheses are added to the recursive call (note that the parentheses here cannot be omitted). This general method applies to any other recursive function: change the recursive calls to yield expression, and leave all the other code as it is.

run_to_finish is used to execute the "recursive function" (strictly speaking, it's no long "recursive" as seen by interpreter) after modification. This executor is universal. The code of run_to_finish can be used to invoke any recursive function after modification. You can put run_to_finish's definition into a library and import it when you want to use it.

Let's analyze the execution process of the modified code:

run_to_finish(recursive_add(10000)) passes a generator to run_to_finish executor. Recall that when recursive_add has a yield expression inside, calling recursive_add only returns a generator and does not execute the code inside the function.

run_to_finish starts to run, which places the generator in the call_stack list. call_stack is a data structure that records the logical call chain of functions (with each of their states on the stack, including local variables, etc). It replaces the common call stack of Python interpreter.

Next, as long as call_stack is not empty, always fetch the last generator in call_stack and let it continue to execute. The generators in call_stack are stored in the logical invocation sequence of functions. The last generator represents the current "innermost" executing function.

Because recursive_add has been transformed into a generator, each time yield recursive_add(x - 1) is executed, the function body of recursive_add is not entered right away, instead, a new generator is returned. This generator is assigned to inner_call and saved to call_stack.

return_value records the "return value" of the function exited just previously. (For the generator, it's actually the value contained in StopIteration exception object.) If the return value exists, use send method to pass it to the outer-level generator in the call chain.

If the StopIteration exception is captured, the current innermost function exits. The corresponding generator in call_stack is deleted and the return value is transferred to the "caller function".

When the input parameter of recursive_add is 0, the internal code of recursive_add will not execute the yield expression. In this case, recursive_add still returns a generator. However, this generator throws an exception (the meaning of returning 0) when its next is invoked for the first time.

When all the generators in call_stack are finished, return_value is the final result of the original recursive function.

Another example of traversing binary tree

Here's another example. Notice that the original function of traversing bin-tree is not a tail recursive function, but it can still be modified and run using this method. The run_to_finish executor is exactly the same with the previous one, so the definition is not shown here.

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def dfs(root):
    if root is None:
        return
    print(root.value)  # print value of this node
    yield dfs(root.left)  # traverse left child subtree, only yield is added for modification
    yield dfs(root.right)  # traverse right child subtree, only yield is added for modification


bin_tree = Node(1, Node(2, Node(3), Node(4)), Node(5))
run_to_finish(dfs(bin_tree))

Answer 2

One option is to cache previous results using functools.cache.

Compare the same code without then with caching.

Without:

def bigsum(n):
    if n <= 0:
        return 0
    elif n > 0:
        return n + bigsum(n-1)

for n in (250, 500, 750, 1000):
    print(f"bigsum({n}) = ", end='')
    print(bigsum(n))

# OUTPUT
#
# bigsum(250) = 31375
# bigsum(500) = 125250
# bigsum(750) = 281625
# bigsum(1000) = 
# RecursionError: maximum recursion depth exceeded in comparison

With caching:

from functools import cache

@cache
def bigsum(n):
    if n <= 0:
        return 0
    elif n > 0:
        return n + bigsum(n-1)

for n in (250, 500, 750, 1000):
    print(f"bigsum({n}) = ", end='')
    print(bigsum(n))

# OUTPUT
#
# bigsum(250) = 31375
# bigsum(500) = 125250
# bigsum(750) = 281625
# bigsum(1000) = 500500

What happens under the hood is that all computed values are saved; when you call bigsum(1000) after having already called bigsum(750), the recursion only goes down to 750 instead of going down to 0; and the recursive call to bigsum(750) returns the cached value without recomputing it.