Python — оптимизация хвостовой рекурсии
Не секрет, что Python не оптимизирует хвостовую рекурсию. Более того сам Гвидо является противником этого. Но если кому нужно, есть небольшое изящное решение. Под катом…
Кстати, можно вызывать функции друг из друга в любом порядке. Код отрабатывает этот случай прекрасно:
Вот такая получилась частица Erlang в 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 )
Comments 27
Only users with full accounts can post comments. Log in, please.