CODEWITHSUNDEEP
recursioniteration
Dogan_79
Dogan_79

Reputation: 41

Converting a bunch of nested recursive functions to iterative funcs

I have read that it is in principle possible to convert a recursive function to an iterative function. I have some bunch of functions calling each other. I constructed the structure of the code looking at my flowchart and it was kind of obvious to do it by recursive style. It runs good for small size problems but gives segmentation fault for bigger scale. So I am trying to switch to iterative style but I cannot imagine a way to do it technically since the branching structure confuses me. Can someone give me a clue to handle it? The code is something like that in python:

def main_function(parameters):
    if condition0:
       ....
       if condition1:
           ....
           if condition2:
               ....
               return function1(parameters)
           else:
               ....
               return function2(parameters)
       else:
           return function1(parameters)
    else:
       return function2(parameters)
#############################################
def function1(parameters):
    if condition3:
       ...
       return function3(parameters)   ### yet another function.. so messed up? :-(((
    else:
       return main_function(parameters)
##############################################
def function2(parameters):
    if condition4:
       ...
       return main_function(parameters)
    else:
       return function1(parameters)
###############################################
def function3(parameters):
   if condition5
      if condition6:
         ...
         return function3(parameters)
      else:
         ...
         return main_function(parameters)
   else:
      return RESULTS   # The only way out!

Any idea would be greatly appreciated, thank you very much in advance.

Upvotes: 1

Views: 169

Answers (2)

Rajendran T
Rajendran T

Reputation: 1553

Since every recursive call is initiated in return statements. You don't need to hold up the old stack. For example, when function1() calls return function3(), function1 stack can be removed. This way you won't get RuntimeError: maximum recursion depth exceeded.

You can achieve this by returning the successive function to call with parameters, instead of calling recursively.

def main_function(parameters):
if condition0:
   if condition1:
       if condition2:
           return function1, parameters # return function to call next with arguments
       else:
           ....
           return function2, parameters
   else:
       return function1, parameters
else:
   return function2, parameters

You should change the other functions to a similar way. Now you can call the main_function() as follows:

next_function, next_fun_param = main_function(parameters)
while hasattr(next_function, '__call__')
    next_function, next_fun_param = next_function(next_fun_param)
# got the RESULT

Upvotes: 0

NPE
NPE

Reputation: 500853

Since every return statement that you've shown is essentially a return some_other_function(), it seems that a state machine would be a natural way to model this. There would be a state corresponding to each function, and the return statements would become state transitions.

Upvotes: 1

Related Questions