Не секрет, что 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 )
ссылка на оригинал статьи http://habrahabr.ru/post/158385/
Добавить комментарий