In most cases there's no way to algorithmically say "If I perform these operations on this recursive function, it changes to iterative." Instead you need to look at the whole of the program and see how it works, then understand how you can make it work without recursion. For instance, let's write a recursive solution to flatten a list (containing lists as well as numbers and etc)
def recurse_flatten(target):
"""recurse_flatten(list_of_lists) -> flat list"""
accumulator = list()
for element in target:
if hasattr(element,"__iter__"):
accumulator.extend(recurse_flatten(element))
else:
accumulator.append(element)
return accumulator
As you can see, the function calls itself if the top-level element has the attribute "__iter__"
, which just means that it's iterable. Instead, we could do this:
def iter_flatten(target):
"""iter_flatten(list_of_lists) -> flat list"""
depth = 0
targets = [iter(target)]
accumulator = list()
while True:
try:
element = next(targets[depth])
except StopIteration:
if depth == 0: return accumulator
else:
depth -= 1
targets.pop()
else:
if hasattr(element,"__iter__"):
targets.append(iter(element))
depth += 1
else: accumulator.append(element)
As you can see, the iterative version is much longer and more verbose, but it never nests. That can be a good thing if you have limited stack space, but generally (at least if you're writing Python) the more readable the code is, the better it is and let me tell you right now that the recursive code is much MORE READABLE. Timing wise, you'll have to test it yourself. On MY system:
# TEST DATA: [1, 2, [3, 4, 5, 6], 7, [8, [9, 10, 11]]]
# timeit.timeit(recurse_flatten)
10.985460426787078
# timeit.timeit(iter_flatten)
16.635406831330158