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

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

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

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

Источник ^[2]