How to avoid depth recursion in nested functions with python

Say we have this code:

a = 1

def func1():
    if a == 1:
        func2()

def func2():
    if a == 1:
        func3()

def func3():
    func1()

Is there a way we could make func3 call func1 stepping out of the 'parent functions' it already incurred in? Meaning, going back to 'recursion depth 0', as if it was starting fresh?

Thank you!

Solution

Some languages offer tail-call optimization, which amounts to throwing away the previous stack frame before creating the new one. It's only possible when the recursive call is the last operation that happens (otherwise you need the stack frame because it points to the rest of the operations). Python doesn't, however.

You have two options:

If the function is recursive but the recursion isn't done with tail calls, often it's simple to convert to tail recursion by adding parameters to the function signature. (The code in your example is already in this form, though.) Once all the recursion is done with tail calls, it's often simple to convert it to an iterative style.
If you would like to avoid doing the above, you can also convert the code into an iterative style which explicitly uses a stack to store things, since the size of your stack will be more or less unbounded, whereas the call stack is usually pretty small (which is what causes the recursion depth limit).

Note that both of these things are trickier to do when you have, say, three functions which call each other recursively. But the overall idea is to come up with new code that preserves the behavior of the old code without using recursion, and obviously how you do that is going to differ depending on the starting code, although the general patterns (linked above) remain the same.

In your case, the code either goes into an infinite loop or doesn't, depending on a, so

 a = 1

 def func3():
     while a == 1:
       pass

 func3()

would suffice.

As a side note: for some algorithms, memoization can reduce the number of calls. If the results for large inputs to a function are always composed out of the results of smaller inputs, which are repeatedly calculated ("overlapping subproblems"), then you can keep a global cache of returned values and check the cache before making new calls. Generic memoization code can be written in Python using decorators.