How to eliminate recursion in Python function containing control flow

Question

I have a function of the form:

def my_func(my_list):
    for i, thing in enumerate(my_list):
        my_val = another_func(thing)

        if i == 0:
            # do some stuff
        else:
            if my_val == something:
                return my_func(my_list[:-1])
            # do some other stuff

The recursive part is getting called enough that I am getting a RecursionError, so I am trying to replace it with a while loop as explained here, but I can't work out how to reconcile this with the control flow statements in the function. Any help would be gratefully received!

It would be helpful if we knew what these functions actually do — Sweeney Todd, Nov 06 '16 at 17:25
You have to provide all the `return` points in order to convert recursion to iterative. — outoftime, Nov 06 '16 at 17:27

score 2 · Answer 1 · edited May 23 '17 at 12:19

There may be a good exact answer, but the most general (or maybe quick-and-dirty) way to switch from recursion to iteration is to manage the stack yourself. Just do manually what programming language does implicitly and have your own unlimited stack.

In this particular case there is tail recursion. You see, my_func recursive call result is not used by the caller in any way, it is immediately returned. What happens in the end is that the deepest recursive call's result bubbles up and is being returned as it is. This is what makes @outoftime's solution possible. We are only interested in into-recursion pass, as the return-from-recursion pass is trivial. So the into-recursion pass is replaced with iterations.

outoftime · Accepted Answer · 2016-11-06T22:36:29.390

def my_func(my_list):
    run = True
    while run:
        for i, thing in enumerate(my_list):
            my_val = another_func(thing)

            if i == 0:
                # do some stuff
            else:
                if my_val == something:
                    my_list = my_list[:-1]
                    break
                # do some other stuff

This is an iterative method.

Decorator

class TailCall(object):
    def __init__(self, __function__):
        self.__function__ = __function__
        self.args = None
        self.kwargs = None
        self.has_params = False

    def __call__(self, *args, **kwargs):
        self.args = args
        self.kwargs = kwargs
        self.has_params = True
        return self

    def __handle__(self):
        if not self.has_params:
            raise TypeError
        if type(self.__function__) is TailCaller:
            return self.__function__.call(*self.args, **self.kwargs)
        return self.__function__(*self.args, **self.kwargs)


class TailCaller(object):
    def __init__(self, call):
        self.call = call

    def __call__(self, *args, **kwargs):
        ret = self.call(*args, **kwargs)
        while type(ret) is TailCall:
            ret = ret.__handle__()
        return ret

@TailCaller
def factorial(n, prev=1):
    if n < 2:
        return prev
    return TailCall(factorial)(n-1, n * prev)

To use this decorator simply wrap your function with @TailCaller decorator and return TailCall instance initialized with required params.

I'd like to say thank you for inspiration to @o2genum and to Kyle Miller who wrote an excellent article about this problem.

Despite how good is to remove this limitation, probably, you have to be aware of why this feature is not officially supported.

How to eliminate recursion in Python function containing control flow

2 Answers2

Decorator