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 )