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

[@gribozavr]

Это называется trampoline.

[@middle]

И так реализована хвостовая рекурсия, например, в Clojure.

[@evil_squonk]

Смысл в том, чтобы превратить рекурсивный вызов функции в цикл.

Работает это так:
1. Пишем рабочую функцию — sum_natural.
2. Заворачиваем её в декоратор recursion.
3. Делаем вызов sum_natural(1000000). При этом sum_natural на самом деле уже указывает не на саму функцию, а на декоратор.
4. Вызывается метод __call__ у декоратора.
5. В этом методе вызывается рабочая функция с переданными параметрами (1000000):

result = self.func(*args, **kwargs)

6. Функция выполняет свою логику. Если параметр x == 0, тогда просто возвращаем результат. Если же нет — значит нужно вычислять дальше. В обычной рекурсии функция просто вызвала бы саму себя с новыми параметрами. Здесь же она подготавливает и возвращает лямбду для такого вызова (обращаясь к методу call декоратора):

return sum_natural_x.call(y - 1, result + y)

7. Декоратор получает результат первого вызова. Смотрим, если результат — callable, то нам вернули лямбду для следующего вызова. Вызываем её, получаем результат, и продолжаем делать это в цикле:

while callable(result): result = result()

8. Возвращаем окончательный результат из метода __call__.

[@qmax]

Тогда надо в методе recursion.call возвращать не лямбду,
а функцию с каким-нить кастмным свойством типа __i_am_reqursion ну и проверять его в recursion.__call__
Но это ж некрасиво будет :)

[@Amper]

Вот еще пример trampoline для рекурсии.
Это требует модификации самой функции, так что далеко не везде применимо. Проще тогда переписать саму функцию без использования рекурсии. Для TCO в python полно хаков в виде декораторов, не требущих модификации функций.

[@sebres]

Более того сам Гвидо является противником этого.

И не напрасно — рекурсии зло (особенно в скрипт языках).
Кстати, зато в этих языках очень просто реализовать стековые «рекурсии» на циклах, без всяких лямбд и т.д. Например, на питоне я делаю как-то так:

def recursive_proc (a, b, c):
    stack = []
    while 1:
        ## делаем работу с текущими a, b,c :
        ...
        if next_level:
            ## push - след. уровень, текущие аргументы в стек :
            stack += [[b, c]]
            ## новые b и c
            b, c = ...
            continue;
        else:
            ## pop - возврат в пред. уровень :
            b, c = stack.pop()
            ## окончание рекурсии :
            if not len(stack):
                break

Помоему гораздо читабельнее и проще, и никаких велосипедов с трамплинами и т.д.

[@dmitriid]

> И не напрасно — рекурсии зло (особенно в скрипт языках).

То есть вы, как и Гвидо, не поняли, что такое хвостовая рекурсия.

[@sebres]

Да нет, прекрасно понимаю, и кстати в моем примере она как раз заменена на итерацию по классике жанра. А в чем проблема?

[@dmitriid]

1. Не понимаете, раз утверждаете, что рекурсия — зло
2. Зачем такие извращения? Такие вещи должен делать компилятор, а не человек.

[@sebres]

Очень информативно…
А программировать за вас тоже компилятор должен? В котором месте извращение? Т.е. вы считаете что велосипед с трамплином это не извращение? Сравните код.
И я еще раз повторяю, что прекрасно понимаю, что-такое хвостовая рекурсия. Зло в рекурсиях как раз лишний вызов и сохранение точки возврата + весь активный scope.
Что убирается итерацией — что в примере в статье, что в моем примере, только я в моем примере сам решаю, что сохранять при следующей итерации, а что нет.

Я просто оставлю это здесь:

# пример из статьи:
>>>> timeit.timeit("sum_natural(1000000)", "from __main__ import sum_natural", number = 50) / 50
0.19649668910566448
# мой пример:
>>>> timeit.timeit("sum_natural_stk(1000000)", "from __main__ import sum_natural", number = 50) / 50
0.13872319519680334

И это на pypy. Как оно себя поведет без jit не проверял, но думаю что еще хуже.

[@Amper]

Не пытайтесь переубедить, у dmitriid претензии не к вашему примеру, а к python вообще. Он приверженец erlang. И приблизительно этот спор уже когда-то был на хабре в какой-то теме о python ) все повторяется )

[@dmitriid]

> у dmitriid претензии не к вашему примеру, а к python вообще.

ваш телепатор сломался

> И приблизительно этот спор уже когда-то был на хабре в какой-то теме о python ) все повторяется )

ну-ну. ссылки на тот сор, я предполагаю, не появится. Если спор был похожий, то там шла речь именно о хвостовой рекурсии, а не о том, какой Питон плохой или хороший

[@Amper]

ваш телепатор сломался

Ок

ну-ну. ссылки на тот сор, я предполагаю, не появится. Если спор был похожий, то там шла речь именно о хвостовой рекурсии, а не о том, какой Питон плохой или хороший

Да, речь там шла о хвостовой рекурсии, но вас так эта тема задевает (неумение питоном TRE), что я сделал выводы о нелюбви к питону ) возможно, вывод неверный.

[@dmitriid]

Именно. И там же мой комментарий: habrahabr.ru/post/111768/#comment_3568874

[@dmitriid]

> А программировать за вас тоже компилятор должен?

Нет. Мало того, из моих слов это никак не следует.

> В котором месте извращение?

В ручной раскрутке рекурсии, которой должен заниматься компилятор

> Т.е. вы считаете что велосипед с трамплином это не извращение?

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

> что прекрасно понимаю, что-такое хвостовая рекурсия. Зло в рекурсиях как раз лишний вызов и сохранение точки возврата + весь активный scope.

То есть вы не понимаете, что такое хвостовая рекурсия. Точки возврата в хвостовой рекрусии нет

> Что убирается итерацией — что в примере в статье, что в моем примере, только я в моем примере сам решаю, что сохранять при следующей итерации, а что нет.

То есть вы предпочитаете выполнять тупую механическую работу, с которой прекрасно справится компилятор. Ок.

[@sebres]

То есть вы не понимаете, что такое хвостовая рекурсия. Точки возврата в хвостовой рекрусии нет

Да нет, в процедурной реализации рекурсии всегда есть точка возврата… Просто это вы не поняли: именно это критиковал van Rossum.
В программировании когда говорится о рекурсии по умолчанию исторически подразумевается процедурная реализация оной. Независимо хвостовая она или нет. Не как в эрланге :) Потому и зло.

То есть вы предпочитаете выполнять тупую механическую работу, с которой прекрасно справится компилятор.

Ну где вы видите работу в двух трех строчках. Просто я предпочитаю держать рекурсию под своим контролем.

ЗЫ. Эрланг я кстати тоже люблю и уважаю, но здесь разговор все-таки о питоне…

[@dmitriid]

> Да нет, в процедурной реализации рекурсии всегда есть точка возврата… Просто это вы не поняли: именно это критиковал van Rossum.

Нет. van Rossum говорил примерно следующее: в питоне не будет оптимизации хвостовой рекурсии потому что я не хочу и не понимаю, что это такое. Это был примерно уровень его аргументов.

> В программировании когда говорится о рекурсии по умолчанию исторически подразумевается процедурная реализация оной.

Когда говорится о хвостовой рекурсии и ее оптимизации, говорится о хвостовой рекурсии и ее оптимизации, а не о ваших фантазиях

Не секрет, что Python не оптимизирует хвостовую рекурсию. Более того сам Гвидо является противником этого.

> Ну где вы видите работу в двух трех строчках.

В том, что это никому не нужная механическая работа за компилятор.

> Эрланг я кстати тоже люблю и уважаю, но здесь разговор все-таки о питоне…

Осталось только понять, где я говорю про Erlang, но в глубинах чужих фантазий я не разбираюсь, увы.

[@sebres]

Нет. van Rossum говорил примерно следующее: в питоне не будет оптимизации хвостовой рекурсии потому что я не хочу и не понимаю, что это такое.

Короче мы с Гвидо не понимаем что токое хвостовая рекурсия… :)
Хотя на самом деле мы с ним не понимаем необходимости оптимизации последней. Это такая точка зрения — можно ее разделять, можно нет.
Но не надо тупо, по детски, тыкать «непониманием» проблемы.
Мои слова "держать рекурсию под своим контролем" вы полностью проигнорировали. А в этом суть…
Понятливый Вы наш…

[@dmitriid]

> Но не надо тупо, по детски, тыкать «непониманием» проблемы.

А чем еще тыкать? Если вы утверждаете — максимально безапелляционно — что «рекурсия зло», например. И предлагаете вместо того, чтобы вводить оптимизацию, заниматься тупой механической работой, которая нужна хорошо, если в 1% случаев.

Ну или речь об оптимизации хвостовой рекурсии, а вы упорно гнете «в рекурсии всегда надо сохранять точку выхода», «говоря про рекурсию мы всегда говорим только про дин тип рекурсии» и т.п. Что-то понимания в ваших словах не заметно вообще.

> Мои слова «держать рекурсию под своим контролем» вы полностью проигнорировали. А в этом суть…

Нет в этом никакой сути. Наличие в языке оптимизации хвостовой рекурсии как-то отнимает у вас право писать собственный код со стеком? Нет.

Это к вопросу о вашем «понимании».

Остальное я давно сказал тут: habrahabr.ru/post/111768/#comment_3568874

[@sebres]

Нет в этом никакой сути. Наличие в языке оптимизации хвостовой рекурсии как-то отнимает у вас право писать собственный код со стеком? Нет.

Вот в тикле 8.6 ввели tailcall, (кстати, я как один из разрабов tcl был против) — так вот после потянулась череда правок в ядре, воркараундов и исключений, чтобы это хозяйство коректно работало с очень гибким функционалом тикля. Теперь это все крутится в namespace scope, а не в scope текущей процедуры.
Я к тому, что только человек со стороны, не вникая во все тонкости конструкций языка и работе ядра оного и не разбирающийся в питоне так как Гвидо, может кричать на каждом углу «дескать он не понимает» и «все это бред».
Вы хоть раз в исходники питона заглядывали? А надо было бы, прежде чем городить огород в приведенном выше комменте.

[@dmitriid]

> Я к тому, что только человек со стороны, не вникая во все тонкости конструкций языка и работе ядра оного и не разбирающийся в питоне так как Гвидо, может кричать на каждом углу «дескать он не понимает» и «все это бред»

Я опираюсь на «аргументы», которые привел Гвидо. Если бы он привел хоть один аргумент, похожий на тот, что вы привели с тиклем, был бы другой разговор.

[@MuLLtiQ]

Ну он и привел: neopythonic.blogspot.ru/2009/04/tail-recursion-elimination.html

[@dmitriid]

habrahabr.ru/post/111768/#comment_3568874

Это не аргументы

[@dmitriid]

ЗЫ

> Ну где вы видите работу в двух трех строчках. Просто я предпочитаю держать рекурсию под своим контролем.

Этот пример никак не доказаывает, что рекурсия зло, и что хвостовую рекурсию не нужно оптимизировать

[@nwalker]

Просто отлично.