4

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!

I want badges
  • 6,155
  • 5
  • 23
  • 38
  • check this http://stackoverflow.com/questions/4138851/recursive-looping-function-in-python – Senthilnathan May 27 '14 at 09:24
  • Are you looking for a [tail call](https://en.wikipedia.org/wiki/Tail_call)? – Alfe May 27 '14 at 09:35
  • 1
    In any case, you might get much better answers if you describe your problem more on the observation level (sth like "this situation is not good for me because I get too deep recursion Errors" or "because it takes too much time" or "because my results are wrong" or similar). There are probably completely different approaches to solving your original issue than you might think of. – Alfe May 27 '14 at 09:36
  • Thank you all. Im actually searching for a solution similar to the suggested code. Im working with a rather unorganized very extense code that could be simplified to the given example. Therefore, I would need a func3() that would do both, 'end the recursion', and call func1 again. – I want badges May 27 '14 at 10:45
  • Thanks everyone, im going to study and try the answers then try them and confirm which one solves the question // accept it. This is a difficult thing for me so maybe it will take me a few days, thanks for everything. – I want badges May 27 '14 at 16:31
  • The package [`tco`](https://github.com/baruchel/tco) can be useful for avoiding recursion depth issues in Python. – 0 _ Jan 27 '21 at 22:10

3 Answers3

5

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:

  1. 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.
  2. 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.

Community
  • 1
  • 1
johncip
  • 2,087
  • 18
  • 24
  • Thank you very much for your answer. But I dont understand how your posted code would solve the problem; while a == 1, the functions will still be nesting themselves one inside another (until a =! 1) How could you do this so the infinite loop wouldn't reach a max depth recursion? – I want badges May 27 '14 at 10:40
  • I've updated the code sample. To clarify, in my example there are no func1 or func2, and func3 never calls anything, so there's no nesting. There is still an infinite loop, since you never break out of the while loop. – johncip May 27 '14 at 10:47
  • 1
    If there's other functionality that you need to preserve, you might have to include some of it in your question. You can't just keep the original sequence of calls and somehow avoid overflowing the stack, but you can rewrite the code so that it does the same things with less function calls. When does the recursion end? What are the base cases? What do the functions do? – johncip May 28 '14 at 08:09
0

Not sure where do you want to stop recursion, but this could be a good point to start:

def func1(parents = []):
    print "func1"
    if func1 not in parents:
        parents.append(func1)
        func2(parents)

def func2(parents = []):
    print "func2"
    if func2 not in parents:
        parents.append(func2)
        func3(parents)

def func3(parents = []):
    print "func3"
    if func3 not in parents:
        parents.append(func3)
        func1(parents)

func1()

Output:

func1
func2
func3
func1
Christian Tapia
  • 33,620
  • 7
  • 56
  • 73
  • Thank you very much for the answer. The idea is not to stop the recursion, but to keep the recursion going without nesting more and more functions inside another until the eventual 'maximum recursion depth exceeded'. Ideally, the script would "end" in func3, and start again in func1, called by func3... – I want badges May 27 '14 at 10:43
0

If you want to repeatedly run the cycle of func1, func2 and func3, but not have it infinitely recurse, you probably want to use a loop rather than recursion.

Try:

def func1():
    pass # do stuff

def func2():
    pass # do more stuff

def func3():
    pass # something completely different

a = 1

while a == 1: # this will loop indefinately, unless one of the functions chages "a"
    func1()
    func2()
    func3()
Blckknght
  • 100,903
  • 11
  • 120
  • 169