Этюды на питоне: оптимизация хвостовой рекурсии в python

Взято с habrahabr.ru

Хвостовая рекурсия выделяется из общего случая тем, что в качестве последней операции используется сам рекурсивный вызов. Примечательна она возможностью разворачиваться в обычный императивный цикл. Это ее свойство часто используется  в функциональных языках для оптимизации производительности.

python хоть и мултипарадигмальный, но функциональные возможности не так сильно развиты, как этого бы многим хотелось. В частности оптимизации хвостовой рекурсии в нем по идеологическим соображениям нет. Но можно написать небольшой trampoline, реализующий эту возможность:

class recursion(object):
    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(x, result=0):
    return (sum.call(x - 1, result + x), result)[x == 0]

print(sum(36))

Данный trampoline использует декоратор. Декоратор заменяет функцию на объект, который хранит в себе саму функцию и имеет специальный метод __call__, который позволяет обращаться с объектом как с функцией.