Python — оптимизация хвостовой рекурсии

Не секрет, что Python не оптимизирует хвостовую рекурсию. Более того сам Гвидо является противником этого. Но если кому нужно, есть небольшое изящное решение. Под катом…

Простое решение

class recursion(object):
    "Can call other methods inside..."
    def __init__(self, func):
        self.func = func

    def __call__(self, *args, **kwargs):
        result = self.func(*args, **kwargs)
        while callable(result): result = result()
        return result

    def call(self, *args, **kwargs):
        return lambda: self.func(*args, **kwargs)


@recursion
def sum_natural(x, result=0):
    if x == 0:
        return result
    else:
        return sum_natural.call(x - 1, result + x)

# Даже такой вызов не заканчивается исключением
# RuntimeError: maximum recursion depth exceeded
print(sum_natural(1000000))

Кстати, можно вызывать функции друг из друга в любом порядке. Код отрабатывает этот случай прекрасно:

@recursion
def sum_natural_x(x, result=0):
    if x == 0:
        return result
    else:
        return sum_natural_y.call(x - 1, result + x)

@recursion
def sum_natural_y(y, result=0):
    if y == 0:
        return result
    else:
        return sum_natural_x.call(y - 1, result + y)

print(sum_natural_x(1000000))

Вот такая получилась частица Erlang в Python )

Автор: deko

Источник