Оптимизация хвостовой рекурсии в 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 Рекурсия




#2 Итерация




#3 Хвостовая рекурсия и «батут»




#4 Хвостовая рекурсия и «батут» (большое число)




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