Иногда для решении задачи приходится использовать Рекурсию, в которой есть свои плюсы и минусы. Я столкнулся с проблемой переполнения стека.
Максимальная глубина рекурсии ограничена движком JavaScript. Точно можно рассчитывать на 10000 вложенных вызовов, некоторые интерпретаторы допускают и больше, но для большинства из них 100000 вызовов – за пределами возможностей. Существуют автоматические оптимизации, помогающие избежать переполнения стека вызовов («оптимизация хвостовой рекурсии»), но они ещё не поддерживаются везде и работают только для простых случаев.
Пример рекурсивной функции:
function sum(n) {
return n === 0 ? 0 : n + sum(n - 1)
}
sum(5) // 1 + 2 + 3 + 4 + 5 = 15
sum(100000) // Error: Maximum call stack size exceeded.Хвостовая рекурсия позволяет оптимизировать вызовы компилятором и уже есть в стандарте ES6, но поддержка браузерами оставляет желать лучшего.
Пример хвостовой рекурсивной функции:
function sum(number, s = 0){
return number === 0 ? s : sum(number - 1, s + number)
}Но, без поддержки браузерами мы столкнемся с той же проблемой — переполнения стека. Можем попробовать использовать вместе с Trampolining.
Напишем декоратор, который будет принимать измененную рекурсивную функцию(следующий шаг) и исполнять ее в цикле, без увеличения глубины вызовов.
function trampoline(fn) {
return function(...args) {
let result = fn.apply(fn.context, args)
while (typeof result === 'function') {
result = result()
}
return result
}
}Теперь наша рекурсивная функция должна возвращать функцию, которая будет сразу исполняться декоратором. Таким способом, мы условно сделаем массив функций и исполним их по очереди. Но поскольку мы каждый раз возвращаем новую анонимную функцию, этот код будет работать несколько медленнее.
function sum(number, s = 0) {
return number === 0 ? s : () => sum(number - 1, s + number)
}Используем:
const trampolineSum = trampoline(sum)
trampolineSum(100000) // 5000050000Это моя первая статья. Я старался не пересказывать понятия и указывал ссылку на источники. Тема не уникальная и давно существует на англоязычных сайтах, к сожалению на русском не нашел.
Спасибо, за внимание. Хорошего дня :)
Update
Производительность:
#1 Рекурсия
function sum(n) {
return n === 0 ? 0 : n + sum(n - 1)
}
console.time("run")
sum(1000)
console.timeEnd("run")[Debug] run: 0.281ms
[Debug] run: 0.305ms
[Debug] run: 0.315ms
[Debug] run: 0.319ms
[Debug] run: 0.231ms
[Debug] run: 0.255ms
[Debug] run: 0.334ms
[Debug] run: 0.370ms
[Debug] run: 0.274ms
[Debug] run: 0.260ms
run: 0.101806640625ms
run: 0.099853515625ms
run: 0.10205078125ms
run: 0.10302734375ms
run: 0.099853515625ms
run: 0.106201171875ms
run: 0.103759765625ms
run: 0.105224609375ms
run: 0.262939453125ms
run: 0.136962890625ms
run: 0.10107421875ms
run: 0.10302734375ms
#2 Итерация
function sum(n) {
let sum = 0
for (let i = 1; i <= n; i++) {
sum += i
}
return sum
}
console.time("run")
sum(1000)
console.timeEnd("run")[Debug] run: 0.552ms
[Debug] run: 0.502ms
[Debug] run: 0.527ms
[Debug] run: 0.434ms
[Debug] run: 0.462ms
[Debug] run: 0.511ms
[Debug] run: 0.528ms
[Debug] run: 0.549ms
[Debug] run: 0.475ms
[Debug] run: 0.530ms
[Debug] run: 0.494ms
run: 0.751953125ms
run: 0.4580078125ms
run: 0.678955078125ms
run: 0.424072265625ms
run: 0.505859375ms
run: 0.563720703125ms
run: 0.404052734375ms
run: 0.411865234375ms
run: 0.634033203125ms
run: 0.4169921875ms
run: 0.390869140625ms
run: 0.464111328125ms
#3 Хвостовая рекурсия и «батут»
function trampoline(fn) {
return function(...args) {
let result = fn.apply(fn.context, args)
while (typeof result === 'function') {
result = result()
}
return result
}
}
function sum(number, s = 0) {
return number === 0 ? s : () => sum(number - 1, s + number)
}
const trampolineSum = trampoline(sum)
console.time("run")
trampolineSum(1000)
console.timeEnd("run")[Debug] run: 0.792ms
[Debug] run: 0.882ms
[Debug] run: 0.826ms
[Debug] run: 0.968ms
[Debug] run: 0.818ms
[Debug] run: 1.681ms
[Debug] run: 0.777ms
[Debug] run: 1.109ms
[Debug] run: 0.832ms
[Debug] run: 0.826ms
run: 0.989990234375ms
run: 0.567138671875ms
run: 0.56005859375ms
run: 1.0087890625ms
run: 0.5400390625ms
run: 0.578125ms
run: 0.541015625ms
run: 0.557861328125ms
run: 1.97607421875ms
run: 0.570068359375ms
run: 0.593017578125ms
run: 0.530029296875ms
run: 0.89794921875ms
run: 0.590087890625ms
#4 Хвостовая рекурсия и «батут» (большое число)
function trampoline(fn) {
return function(...args) {
let result = fn.apply(fn.context, args)
while (typeof result === 'function') {
result = result()
}
return result
}
}
function sum(number, s = 0) {
return number === 0 ? s : () => sum(number - 1, s + number)
}
const trampolineSum = trampoline(sum)
console.time("run")
trampolineSum(100000)
console.timeEnd("run")[Debug] run: 24.564ms
[Debug] run: 25.313ms
[Debug] run: 23.262ms
[Debug] run: 24.848ms
[Debug] run: 23.909ms
[Debug] run: 24.248ms
[Debug] run: 32.416ms
[Debug] run: 24.090ms
[Debug] run: 23.986ms
run: 33.955078125ms
run: 40.907958984375ms
run: 37.693115234375ms
run: 28.929931640625ms
run: 30.7548828125ms
run: 29.720947265625ms
run: 40.8310546875ms
run: 31.5830078125ms
run: 30.712890625ms
run: 30.162841796875ms
run: 31.56103515625ms
По результатам мы видим, что наш декоратор хоть и позволяет избежать ошибки переполнения стека, но работает он медленнее чем рекурсивный и итеративный вариант. Так что данный способ стоит использовать только если вы не можете заменить рекурсию на итерацию или боитесь переполнения стека при выполнении вашей рекурсивной функции.
Комментарии (31)
Focushift
25.08.2019 13:17+1И? остановились на самом главном.
Почему декоратор? что он делает и т.п.?
Я вижу только увеличение глубины вызовов функции.
MikeMoore Автор
25.08.2019 13:29Декоратор возвращает функцию, которая в цикле выполняет нашу функцию, без увеличения глубины вызовов как при рекурсии. В функцию передаются параметры и она сразу может быть вызвана вернув результат или другую функцию, которую мы будем вызывать на следующей итерации. Если кратно, мы просто в цикле выполняем якобы рекурсивную функцию, просто подставляя результат прошлой итерации.
CoolCmd
25.08.2019 13:30+1данные хранятся не в стеке, а в куче в виде неименованной функции.
на каждой итерации создается новая функция, так что производительность скорее всего будет так себе.
Gibrrr
25.08.2019 13:37+1Спасибо за статью, но хотелось бы чуть более развернутых объяснений, что в показанном подходе позволило избавиться от переполнения стека, какие недостатки есть у данного подхода, как он по скорости, другие альтернативы и т.п.
MikeMoore Автор
25.08.2019 13:41Спасибо за комментарии, вижу уже несколько недостатков статьи, поэтому постараюсь ближайшем времени дополнить информацию и провести тесты производительности.
python273
25.08.2019 13:40Только это не будет работать если нужно сделать больше одного рекурсивного вызова в функции
Как-то делал обход глубины стека через генераторы на python:
https://github.com/python273/precursion
Mingun
25.08.2019 13:47С концептуальной точки зрения будет, только нужно еще немного руками функцию доработать (а хотелось бы, конечно, чтобы это делал движок): просто вместо одного параметра-аккумулятора (
s = 0в статье) функция должна принимать вектор и сама стать векторной, на каждой итерации вычисляя сразу пачку значений. Тогда для основного алгоритма разворачивания рекурсии в цикл у нас остается всего один хвостовой вызов
xGromMx
25.08.2019 13:44Умеющий искать да найдет
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 из коробки
dem0n3d
25.08.2019 13:46Подробный разбор темы на HolyJS 2019 Piter.
acupofspirt
25.08.2019 16:01+1Вячеслава Егорова на вас нет. Кто же так меряет производительность как у вас в примерах. Надо хотя бы показать интерпретатору что используете результат вызова функции. Иначе рискуете между вызовами time и timeEnd получить стрекотание сверчков при чистой функции)
neurocore
25.08.2019 17:21-2Рекурсия в JS? Вы же не собираетесь на нём шахматный движок писать, это не подходящий инструмент. Остальные случаи прекрасно обходятся правильными алгоритмами.
vlanko
25.08.2019 18:06Firefox 63 лимит 32-37000 (рандом)
И на таких больших числах почему-то бутут быстрее…
impwx
25.08.2019 20:13То есть:
- Поддерживает только один рекурсивный вызов
- Не работает без модификации исходной функции
- Не работает с функциями, возвращающими некий тип (function оказывается зарезервирован под рекурсивный вызов)
С такими ограничениями проще вообще обходить рекурсию стороной, всегда разворачивая ее в итеративную форму вручную.
aamonster
25.08.2019 22:46Дык вся суть хвостовой рекурсии – что у нас единственный вызов, причём он выполняется последним.
aamonster
26.08.2019 10:55А эта схема с трамплином вообще работает? Да, рекурсия устраняется. Но, т.к. вы возвращаете из функции замыкание – оно сохраняет контекст. Когда на следующем проходе вы его вызываете – опять возвращается замыкание. С контекстом и ссылкой на контекст создавшей его функции (вдруг понадобятся переменные оттуда?). И так далее – создавая целый "стек" контекстов.
Я где-то неправ?
Pand5461
26.08.2019 13:19+1Т.к. рекурсия хвостовая, то переменные создавшей функции уже не нужны. Если транслятор достаточно умный, чтобы это понять — то ссылки на внешний контекст не будет, и созданные замыкания уходят сборщику мусора, как только они отработали.
aamonster
26.08.2019 14:08Если транслятор достаточно умный – то может просто соптимизировать хвостовую рекурсию без трамплина, нет?
aamonster
26.08.2019 18:33Иными словами, мне интересно, есть ли реализации JS, которые оптимизируют цепочку контекстов, удаляя ненужные – но почему-то не оптимизируют Tail Call.
force
26.08.2019 14:01Всегда хотел спросить, а что курили авторы ES6, когда включали оптимизиацию хвостовой рекурсии в стандарт? Т.е. это не возможности языка, а свойство рантайма. При этом его ещё особо и не проверить. Да и заполифиллить его нормальным образом нельзя. В результате получается фича, которую использовать нельзя, потому что на неподдерживаемом браузере всё развалится.
unel
26.08.2019 16:48ну, почему не проверить? немного наивный механизм, предполагающий константную максимальную глубину стека, но всё же:
— сперва выполнить функцию, заведомо выполняющую переполнение стека вызова, тем самым, узнав его глубину
— потом выполнить функцию с tco, с той же или чуть большей глубиной. если произошло переполнение стека вызовов — значит, tco нет, иначе — есть)
вот с полифилами — да, беда. разве что только на уровне транспайлеров определять и преобразовывать в код с «трамплинами»
но в целом, конкретно в JS, овчинка выделки не стоит)force
26.08.2019 17:08Ну, глубина стека не определена, да и попытка её переполнить может привести к временному эпическому потреблению памяти или браузер от ужаса прибьёт все скрипты на странице. Опасненький такой способ. :) И опять же, писать две ветки кода, одна на случай оптимизации, другая циклом — достаточно бестолковое времяпрепровождение. Раз уж написали универсальный код, зачем поддерживать код с хвостами.
unel
26.08.2019 17:58function 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, хотя на самом деле это не такunel
26.08.2019 18:03Ещё одна забавная вариация :-)
function dd() { try { return 1 + dd() } catch (e) { return 0; } } dd(); // 12541force
26.08.2019 18:34Firefox. Очень забавный результат. Каждый раз разный :)
function dd(deep = 0) { try { return dd(deep + 1) } catch (e) { return deep; } } dd(); 21393 dd(); 21089 dd() 21269 dd() 23559 dd() 23559 dd() 23559 dd() 23408 dd() 23573 dd()
Mingun
26.08.2019 18:06Все правильно сделали. Это напрашивающаяся сама собой оптимизация для языка, нацеленного на широкое использование функционального подхода.
А зачем вам проверять это свойство? Вы хотите написать 2 версии кода с надеждой на хвостовую рекурсию и без нее? А зачем? Обычная версия будет работать везде, поэтому если у вас стоят требования, работать там, где такой оптимизации нет, то ставите себе линтер на запрет рекурсивных вызовов и нет проблем.
Я даже не представляю, что значить полифиллить хвостовую рекурсию. А для
classили для геттеров/сеттеров таких вопросов не возникало?force
26.08.2019 18:30> Все правильно сделали. Это напрашивающаяся сама собой оптимизация для языка, нацеленного на широкое использование функционального подхода.
Тут разница в том, что это не свойство языка, ни синтаксис, ничего. Это некое абстрактное свойство рантайма, при этом оно живёт не в статусе работает/не работает. А в статусе работает хорошо/работает плохо и иногда падает по OOM.
При этом в реальности — хром вначале добавил эту оптимизацию, потом выпилил. Т.е. если кто-то заточился на эту фичу, поимел грабли. Код развалился просто так.
> то ставите себе линтер на запрет рекурсивных вызовов и нет проблем.
Рекурсия вполне может использоваться и в обычном виде, запрещать рекурсию саму по себе — это очень странно. А линтёр, определяющий хвостовую рекурсию… ну такое…
> Я даже не представляю, что значить полифиллить хвостовую рекурсию. А для class или для геттеров/сеттеров таких вопросов не возникало?
Я тоже. Но для классов — вполне себе всё полифилится. Хотя, я может неправильно термин подобрал. Наверное транспайлинг тут лучше звучит.Mingun
26.08.2019 18:41При этом в реальности — хром вначале добавил эту оптимизацию, потом выпилил.
Ну так не используйте/не затачивайтесь на бажные реализации. Когда допилят и вы сможете себе позволить поддерживать их, тогда и начинайте использовать новые фишки, если все так плохо. Но понимаете, без стандартизации хорошо не будет никогда. А так есть надежда, что через 5 лет у всех все будет работать.
Рекурсия вполне может использоваться и в обычном виде, запрещать рекурсию саму по себе — это очень странно.
Любую рекурсию можно свести к хвостовой, а хвостовую — развернуть в цикл. Так что либо запрещать всю, либо никакую.
Наверное транспайлинг тут лучше звучит.
Вот транспайлинг — это да, тогда ясно. Рекурсия точно также транспайлится — берется, и разворачивается в цикл. Т.е. теперь этой оптимизацией будет заниматься не рантайм, а транспайлер.
Rsa97
Если мне не изменяет склероз, то хвостовую рекурсию практически всегда можно преобразовать в итерацию. Возможно, что запись функции при этом станет не такой красивой, но переполнения стека из-за рекурсии не будет.
Pand5461
Не изменяет, причём не практически всегда, а всегда.
Насчёт того, что запись станет некрасивой — вряд ли. Преобразование к хвостовой рекурсии само по себе "портит" внешний вид. Даже сравнить примеры из статьи — в первом очевидно, что делает рекурсия, во втором мысленно всё равно нужно развернуть её в цикл, чтобы понять, что происходит.
Zenitchik
Пример из статьи — очень упрощённый.
Практически интересен пример, когда функций несколько, и они могут вызывать друг друга, причём. Я обычно такое преобразовываю в возврат предыдущей функцией ссылки на следующую, а саму функцию выполняет цикл. ИМХО, настоящая хвостовая рекурсия — была бы красивее.