Оптимизация хвостовой рекурсии в JavaScript

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

Максимальная глубина рекурсии ограничена движком 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")

#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")

#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")

#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")

По результатам мы видим, что наш декоратор хоть и позволяет избежать ошибки переполнение стека, но работает он медленнее чем рекурсивный и итеративный вариант. Так что данный способ стоит использовать только если вы не можете заменить рекурсию на итерацию или боитесь переполнение стека при выполнении вашей рекурсивной функции.