Привет, читатель.
Иногда для решении задачи приходится использовать Рекурсию, в которой есть свои плюсы и минусы. Я столкнулся с проблемой переполнения стека.
Максимальная глубина рекурсии ограничена движком 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
Это моя первая статья. Я старался не пересказывать понятия и указывал ссылку на источники. Тема не уникальная и давно существует на англоязычных сайтах, к сожалению на русском не нашел. Есть несколько реализаций данного способа оптимизации — это один, который я использовал.
Спасибо, за внимание. Хорошего дня :)
Автор: Михаил