Комментарии 32
Не изменяет, причём не практически всегда, а всегда.
Насчёт того, что запись станет некрасивой — вряд ли. Преобразование к хвостовой рекурсии само по себе "портит" внешний вид. Даже сравнить примеры из статьи — в первом очевидно, что делает рекурсия, во втором мысленно всё равно нужно развернуть её в цикл, чтобы понять, что происходит.
Почему декоратор? что он делает и т.п.?
Я вижу только увеличение глубины вызовов функции.
данные хранятся не в стеке, а в куче в виде неименованной функции.
на каждой итерации создается новая функция, так что производительность скорее всего будет так себе.
генератор уже советовали вместо велосипеда с циклом?
Только это не будет работать если нужно сделать больше одного рекурсивного вызова в функции
Как-то делал обход глубины стека через генераторы на python:
https://github.com/python273/precursion
С концептуальной точки зрения будет, только нужно еще немного руками функцию доработать (а хотелось бы, конечно, чтобы это делал движок): просто вместо одного параметра-аккумулятора (s = 0 в статье) функция должна принимать вектор и сама стать векторной, на каждой итерации вычисляя сразу пачку значений. Тогда для основного алгоритма разворачивания рекурсии в цикл у нас остается всего один хвостовой вызов
raganwald.com/2013/03/28/trampolines-in-javascript.html
blog.logrocket.com/using-trampolines-to-manage-large-recursive-loops-in-javascript-d8c9db095ae3
stackoverflow.com/a/27704484/3042847
marmelab.com/blog/2018/02/12/understanding-recursion.html
github.com/getify/Functional-Light-JS/blob/master/manuscript/ch8.md
sqrtt.pro/trampolines-in-javascript-ru
blog.csssr.ru/2018/09/06/recursion
purescript имеет TCO из коробки
Подробный разбор темы на HolyJS 2019 Piter.
И на таких больших числах почему-то бутут быстрее…
То есть:
- Поддерживает только один рекурсивный вызов
- Не работает без модификации исходной функции
- Не работает с функциями, возвращающими некий тип (function оказывается зарезервирован под рекурсивный вызов)
С такими ограничениями проще вообще обходить рекурсию стороной, всегда разворачивая ее в итеративную форму вручную.
А эта схема с трамплином вообще работает? Да, рекурсия устраняется. Но, т.к. вы возвращаете из функции замыкание – оно сохраняет контекст. Когда на следующем проходе вы его вызываете – опять возвращается замыкание. С контекстом и ссылкой на контекст создавшей его функции (вдруг понадобятся переменные оттуда?). И так далее – создавая целый "стек" контекстов.
Я где-то неправ?
— сперва выполнить функцию, заведомо выполняющую переполнение стека вызова, тем самым, узнав его глубину
— потом выполнить функцию с tco, с той же или чуть большей глубиной. если произошло переполнение стека вызовов — значит, tco нет, иначе — есть)
вот с полифилами — да, беда. разве что только на уровне транспайлеров определять и преобразовывать в код с «трамплинами»
но в целом, конкретно в JS, овчинка выделки не стоит)
function dd(deep = 0) { try { return dd(deep + 1) } catch (e) { return deep; } }
dd(); // 10450
function dd(deep = 0) { try { return 0 + dd(deep + 1) } catch (e) { return deep; } }
dd(); // 9646
function dd(deep = 0) { try { return 0 + 0 + dd(deep + 1) } catch (e) { return deep; } }
dd(); // 9646
У меня ничего не взвыло и не упало (но, конечно, единичный случай — не показатель) =)
Самое забавное, что код «с TCO» (первый) вызывается с чуть большей глубиной, нежели «без TCO».
Т.е. мой «наивный» алгоритм решит, что в данном случае браузер поддерживает TCO, хотя на самом деле это не так
function dd() { try { return 1 + dd() } catch (e) { return 0; } }
dd(); // 12541
Все правильно сделали. Это напрашивающаяся сама собой оптимизация для языка, нацеленного на широкое использование функционального подхода.
А зачем вам проверять это свойство? Вы хотите написать 2 версии кода с надеждой на хвостовую рекурсию и без нее? А зачем? Обычная версия будет работать везде, поэтому если у вас стоят требования, работать там, где такой оптимизации нет, то ставите себе линтер на запрет рекурсивных вызовов и нет проблем.
Я даже не представляю, что значить полифиллить хвостовую рекурсию. А для class или для геттеров/сеттеров таких вопросов не возникало?
Тут разница в том, что это не свойство языка, ни синтаксис, ничего. Это некое абстрактное свойство рантайма, при этом оно живёт не в статусе работает/не работает. А в статусе работает хорошо/работает плохо и иногда падает по OOM.
При этом в реальности — хром вначале добавил эту оптимизацию, потом выпилил. Т.е. если кто-то заточился на эту фичу, поимел грабли. Код развалился просто так.
> то ставите себе линтер на запрет рекурсивных вызовов и нет проблем.
Рекурсия вполне может использоваться и в обычном виде, запрещать рекурсию саму по себе — это очень странно. А линтёр, определяющий хвостовую рекурсию… ну такое…
> Я даже не представляю, что значить полифиллить хвостовую рекурсию. А для class или для геттеров/сеттеров таких вопросов не возникало?
Я тоже. Но для классов — вполне себе всё полифилится. Хотя, я может неправильно термин подобрал. Наверное транспайлинг тут лучше звучит.
При этом в реальности — хром вначале добавил эту оптимизацию, потом выпилил.
Ну так не используйте/не затачивайтесь на бажные реализации. Когда допилят и вы сможете себе позволить поддерживать их, тогда и начинайте использовать новые фишки, если все так плохо. Но понимаете, без стандартизации хорошо не будет никогда. А так есть надежда, что через 5 лет у всех все будет работать.
Рекурсия вполне может использоваться и в обычном виде, запрещать рекурсию саму по себе — это очень странно.
Любую рекурсию можно свести к хвостовой, а хвостовую — развернуть в цикл. Так что либо запрещать всю, либо никакую.
Наверное транспайлинг тут лучше звучит.
Вот транспайлинг — это да, тогда ясно. Рекурсия точно также транспайлится — берется, и разворачивается в цикл. Т.е. теперь этой оптимизацией будет заниматься не рантайм, а транспайлер.
Оптимизация хвостовой рекурсии в JavaScript