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

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

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

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

Хвостовая рекурсия ^[2] позволяет оптимизировать вызовы компилятором и уже есть в стандарте ES6 ^[3], но поддержка браузерами оставляет желать лучшего ^[4].

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

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

Но, без поддержки браузерами мы столкнемся с той же проблемой — переполнение стека. Можем попробовать использовать вместе с Trampolining ^[5].

Напишем декоратор:

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

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

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

Автор: Михаил

Источник ^[6]