Хабрахабр

[Из песочницы] Оптимизация хвостовой рекурсии в JavaScript

Привет, читатель.

Я столкнулся с проблемой переполнения стека.
Иногда для решении задачи приходится использовать Рекурсию, в которой есть свои плюсы и минусы.

Точно можно рассчитывать на 10000 вложенных вызовов, некоторые интерпретаторы допускают и больше, но для большинства из них 100000 вызовов – за пределами возможностей. Максимальная глубина рекурсии ограничена движком JavaScript. Существуют автоматические оптимизации, помогающие избежать переполнения стека вызовов («оптимизация хвостовой рекурсии»), но они ещё не поддерживаются везде и работают только для простых случаев.

Пример рекурсивной функции:

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 result }
}

Теперь наша рекурсивная функция должна возвращать функцию для нашего декоратора:

function sum(number, s = 0) { return number === 0 ? s : () => sum(number - 1, s + number)
}

Используем:

const trampolineSum = trampoline(sum)
trampolineSum(100000) // 5000050000

Это моя первая статья. Я старался не пересказывать понятия и указывал ссылку на источники. Тема не уникальная и давно существует на англоязычных сайтах, к сожалению на русском не нашел. Есть несколько реализаций данного способа оптимизации — это один, который я использовал.

Хорошего дня 🙂 Спасибо, за внимание.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть