Comments 27
Это называется trampoline.
+8
UFO just landed and posted this here
Смысл в том, чтобы превратить рекурсивный вызов функции в цикл.
Работает это так:
1. Пишем рабочую функцию — sum_natural.
2. Заворачиваем её в декоратор recursion.
3. Делаем вызов sum_natural(1000000). При этом sum_natural на самом деле уже указывает не на саму функцию, а на декоратор.
4. Вызывается метод __call__ у декоратора.
5. В этом методе вызывается рабочая функция с переданными параметрами (1000000):
6. Функция выполняет свою логику. Если параметр x == 0, тогда просто возвращаем результат. Если же нет — значит нужно вычислять дальше. В обычной рекурсии функция просто вызвала бы саму себя с новыми параметрами. Здесь же она подготавливает и возвращает лямбду для такого вызова (обращаясь к методу call декоратора):
7. Декоратор получает результат первого вызова. Смотрим, если результат — callable, то нам вернули лямбду для следующего вызова. Вызываем её, получаем результат, и продолжаем делать это в цикле:
8. Возвращаем окончательный результат из метода __call__.
Работает это так:
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__.
+17
UFO just landed and posted this here
Более того сам Гвидо является противником этого.И не напрасно — рекурсии зло (особенно в скрипт языках).
Кстати, зато в этих языках очень просто реализовать стековые «рекурсии» на циклах, без всяких лямбд и т.д. Например, на питоне я делаю как-то так:
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
Помоему гораздо читабельнее и проще, и никаких велосипедов с трамплинами и т.д.
-5
> И не напрасно — рекурсии зло (особенно в скрипт языках).
То есть вы, как и Гвидо, не поняли, что такое хвостовая рекурсия.
То есть вы, как и Гвидо, не поняли, что такое хвостовая рекурсия.
+5
Да нет, прекрасно понимаю, и кстати в моем примере она как раз заменена на итерацию по классике жанра. А в чем проблема?
-3
1. Не понимаете, раз утверждаете, что рекурсия — зло
2. Зачем такие извращения? Такие вещи должен делать компилятор, а не человек.
2. Зачем такие извращения? Такие вещи должен делать компилятор, а не человек.
0
Очень информативно…
А программировать за вас тоже компилятор должен? В котором месте извращение? Т.е. вы считаете что велосипед с трамплином это не извращение? Сравните код.
И я еще раз повторяю, что прекрасно понимаю, что-такое хвостовая рекурсия. Зло в рекурсиях как раз лишний вызов и сохранение точки возврата + весь активный scope.
Что убирается итерацией — что в примере в статье, что в моем примере, только я в моем примере сам решаю, что сохранять при следующей итерации, а что нет.
Я просто оставлю это здесь:
И это на pypy. Как оно себя поведет без jit не проверял, но думаю что еще хуже.
А программировать за вас тоже компилятор должен? В котором месте извращение? Т.е. вы считаете что велосипед с трамплином это не извращение? Сравните код.
И я еще раз повторяю, что прекрасно понимаю, что-такое хвостовая рекурсия. Зло в рекурсиях как раз лишний вызов и сохранение точки возврата + весь активный 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 не проверял, но думаю что еще хуже.
-1
> у dmitriid претензии не к вашему примеру, а к python вообще.
ваш телепатор сломался
> И приблизительно этот спор уже когда-то был на хабре в какой-то теме о python ) все повторяется )
ну-ну. ссылки на тот сор, я предполагаю, не появится. Если спор был похожий, то там шла речь именно о хвостовой рекурсии, а не о том, какой Питон плохой или хороший
ваш телепатор сломался
> И приблизительно этот спор уже когда-то был на хабре в какой-то теме о python ) все повторяется )
ну-ну. ссылки на тот сор, я предполагаю, не появится. Если спор был похожий, то там шла речь именно о хвостовой рекурсии, а не о том, какой Питон плохой или хороший
+1
ваш телепатор сломалсяОк
ну-ну. ссылки на тот сор, я предполагаю, не появится. Если спор был похожий, то там шла речь именно о хвостовой рекурсии, а не о том, какой Питон плохой или хорошийДа, речь там шла о хвостовой рекурсии, но вас так эта тема задевает (неумение питоном TRE), что я сделал выводы о нелюбви к питону ) возможно, вывод неверный.
0
Именно. И там же мой комментарий: habrahabr.ru/post/111768/#comment_3568874
+3
> А программировать за вас тоже компилятор должен?
Нет. Мало того, из моих слов это никак не следует.
> В котором месте извращение?
В ручной раскрутке рекурсии, которой должен заниматься компилятор
> Т.е. вы считаете что велосипед с трамплином это не извращение?
Нет, я тоже считаю это извращением. Потому что оптимизацию хвостовой рекурсии должен выполнять компилятор
> что прекрасно понимаю, что-такое хвостовая рекурсия. Зло в рекурсиях как раз лишний вызов и сохранение точки возврата + весь активный scope.
То есть вы не понимаете, что такое хвостовая рекурсия. Точки возврата в хвостовой рекрусии нет
> Что убирается итерацией — что в примере в статье, что в моем примере, только я в моем примере сам решаю, что сохранять при следующей итерации, а что нет.
То есть вы предпочитаете выполнять тупую механическую работу, с которой прекрасно справится компилятор. Ок.
Нет. Мало того, из моих слов это никак не следует.
> В котором месте извращение?
В ручной раскрутке рекурсии, которой должен заниматься компилятор
> Т.е. вы считаете что велосипед с трамплином это не извращение?
Нет, я тоже считаю это извращением. Потому что оптимизацию хвостовой рекурсии должен выполнять компилятор
> что прекрасно понимаю, что-такое хвостовая рекурсия. Зло в рекурсиях как раз лишний вызов и сохранение точки возврата + весь активный scope.
То есть вы не понимаете, что такое хвостовая рекурсия. Точки возврата в хвостовой рекрусии нет
> Что убирается итерацией — что в примере в статье, что в моем примере, только я в моем примере сам решаю, что сохранять при следующей итерации, а что нет.
То есть вы предпочитаете выполнять тупую механическую работу, с которой прекрасно справится компилятор. Ок.
+2
То есть вы не понимаете, что такое хвостовая рекурсия. Точки возврата в хвостовой рекрусии нетДа нет, в процедурной реализации рекурсии всегда есть точка возврата… Просто это вы не поняли: именно это критиковал van Rossum.
В программировании когда говорится о рекурсии по умолчанию исторически подразумевается процедурная реализация оной. Независимо хвостовая она или нет. Не как в эрланге :) Потому и зло.
То есть вы предпочитаете выполнять тупую механическую работу, с которой прекрасно справится компилятор.Ну где вы видите работу в двух трех строчках. Просто я предпочитаю держать рекурсию под своим контролем.
ЗЫ. Эрланг я кстати тоже люблю и уважаю, но здесь разговор все-таки о питоне…
-2
> Да нет, в процедурной реализации рекурсии всегда есть точка возврата… Просто это вы не поняли: именно это критиковал van Rossum.
Нет. van Rossum говорил примерно следующее: в питоне не будет оптимизации хвостовой рекурсии потому что я не хочу и не понимаю, что это такое. Это был примерно уровень его аргументов.
> В программировании когда говорится о рекурсии по умолчанию исторически подразумевается процедурная реализация оной.
Когда говорится о хвостовой рекурсии и ее оптимизации, говорится о хвостовой рекурсии и ее оптимизации, а не о ваших фантазиях
> Ну где вы видите работу в двух трех строчках.
В том, что это никому не нужная механическая работа за компилятор.
> Эрланг я кстати тоже люблю и уважаю, но здесь разговор все-таки о питоне…
Осталось только понять, где я говорю про Erlang, но в глубинах чужих фантазий я не разбираюсь, увы.
Нет. van Rossum говорил примерно следующее: в питоне не будет оптимизации хвостовой рекурсии потому что я не хочу и не понимаю, что это такое. Это был примерно уровень его аргументов.
> В программировании когда говорится о рекурсии по умолчанию исторически подразумевается процедурная реализация оной.
Когда говорится о хвостовой рекурсии и ее оптимизации, говорится о хвостовой рекурсии и ее оптимизации, а не о ваших фантазиях
Не секрет, что Python не оптимизирует хвостовую рекурсию. Более того сам Гвидо является противником этого.
> Ну где вы видите работу в двух трех строчках.
В том, что это никому не нужная механическая работа за компилятор.
> Эрланг я кстати тоже люблю и уважаю, но здесь разговор все-таки о питоне…
Осталось только понять, где я говорю про Erlang, но в глубинах чужих фантазий я не разбираюсь, увы.
+1
Нет. van Rossum говорил примерно следующее: в питоне не будет оптимизации хвостовой рекурсии потому что я не хочу и не понимаю, что это такое.Короче мы с Гвидо не понимаем что токое хвостовая рекурсия… :)
Хотя на самом деле мы с ним не понимаем необходимости оптимизации последней. Это такая точка зрения — можно ее разделять, можно нет.
Но не надо тупо, по детски, тыкать «непониманием» проблемы.
Мои слова "держать рекурсию под своим контролем" вы полностью проигнорировали. А в этом суть…
Понятливый Вы наш…
0
> Но не надо тупо, по детски, тыкать «непониманием» проблемы.
А чем еще тыкать? Если вы утверждаете — максимально безапелляционно — что «рекурсия зло», например. И предлагаете вместо того, чтобы вводить оптимизацию, заниматься тупой механической работой, которая нужна хорошо, если в 1% случаев.
Ну или речь об оптимизации хвостовой рекурсии, а вы упорно гнете «в рекурсии всегда надо сохранять точку выхода», «говоря про рекурсию мы всегда говорим только про дин тип рекурсии» и т.п. Что-то понимания в ваших словах не заметно вообще.
> Мои слова «держать рекурсию под своим контролем» вы полностью проигнорировали. А в этом суть…
Нет в этом никакой сути. Наличие в языке оптимизации хвостовой рекурсии как-то отнимает у вас право писать собственный код со стеком? Нет.
Это к вопросу о вашем «понимании».
Остальное я давно сказал тут: habrahabr.ru/post/111768/#comment_3568874
А чем еще тыкать? Если вы утверждаете — максимально безапелляционно — что «рекурсия зло», например. И предлагаете вместо того, чтобы вводить оптимизацию, заниматься тупой механической работой, которая нужна хорошо, если в 1% случаев.
Ну или речь об оптимизации хвостовой рекурсии, а вы упорно гнете «в рекурсии всегда надо сохранять точку выхода», «говоря про рекурсию мы всегда говорим только про дин тип рекурсии» и т.п. Что-то понимания в ваших словах не заметно вообще.
> Мои слова «держать рекурсию под своим контролем» вы полностью проигнорировали. А в этом суть…
Нет в этом никакой сути. Наличие в языке оптимизации хвостовой рекурсии как-то отнимает у вас право писать собственный код со стеком? Нет.
Это к вопросу о вашем «понимании».
Остальное я давно сказал тут: habrahabr.ru/post/111768/#comment_3568874
0
Нет в этом никакой сути. Наличие в языке оптимизации хвостовой рекурсии как-то отнимает у вас право писать собственный код со стеком? Нет.Вот в тикле 8.6 ввели tailcall, (кстати, я как один из разрабов tcl был против) — так вот после потянулась череда правок в ядре, воркараундов и исключений, чтобы это хозяйство коректно работало с очень гибким функционалом тикля. Теперь это все крутится в namespace scope, а не в scope текущей процедуры.
Я к тому, что только человек со стороны, не вникая во все тонкости конструкций языка и работе ядра оного и не разбирающийся в питоне так как Гвидо, может кричать на каждом углу «дескать он не понимает» и «все это бред».
Вы хоть раз в исходники питона заглядывали? А надо было бы, прежде чем городить огород в приведенном выше комменте.
+1
> Я к тому, что только человек со стороны, не вникая во все тонкости конструкций языка и работе ядра оного и не разбирающийся в питоне так как Гвидо, может кричать на каждом углу «дескать он не понимает» и «все это бред»
Я опираюсь на «аргументы», которые привел Гвидо. Если бы он привел хоть один аргумент, похожий на тот, что вы привели с тиклем, был бы другой разговор.
Я опираюсь на «аргументы», которые привел Гвидо. Если бы он привел хоть один аргумент, похожий на тот, что вы привели с тиклем, был бы другой разговор.
0
ЗЫ
> Ну где вы видите работу в двух трех строчках. Просто я предпочитаю держать рекурсию под своим контролем.
Этот пример никак не доказаывает, что рекурсия зло, и что хвостовую рекурсию не нужно оптимизировать
> Ну где вы видите работу в двух трех строчках. Просто я предпочитаю держать рекурсию под своим контролем.
Этот пример никак не доказаывает, что рекурсия зло, и что хвостовую рекурсию не нужно оптимизировать
-2
Просто отлично.
+1
Only those users with full accounts are able to leave comments. Log in, please.
Python — оптимизация хвостовой рекурсии