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



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

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

Максимальная глубина рекурсии ограничена движком 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 Рекурсия
Код #1
function sum(n) {
  return n === 0 ? 0 : n + sum(n - 1)
}

console.time("run")
sum(1000)
console.timeEnd("run")


Результат #1 Safari 12.1.2
[Debug] run: 0.353ms
[Debug] run: 0.281ms
[Debug] run: 0.305ms
[Debug] run: 0.315ms
[Debug] run: 0.319ms
[Debug] run: 0.231ms
[Debug] run: 0.255ms
[Debug] run: 0.334ms
[Debug] run: 0.370ms
[Debug] run: 0.274ms
[Debug] run: 0.260ms

Результат #1 Google Chrome 78.0.3892.0
run: 0.118896484375ms
run: 0.101806640625ms
run: 0.099853515625ms
run: 0.10205078125ms
run: 0.10302734375ms
run: 0.099853515625ms
run: 0.106201171875ms
run: 0.103759765625ms
run: 0.105224609375ms
run: 0.262939453125ms
run: 0.136962890625ms
run: 0.10107421875ms
run: 0.10302734375ms


#2 Итерация
Код #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")


Результат #2 Safari 12.1.2
[Debug] run: 0.562ms
[Debug] run: 0.552ms
[Debug] run: 0.502ms
[Debug] run: 0.527ms
[Debug] run: 0.434ms
[Debug] run: 0.462ms
[Debug] run: 0.511ms
[Debug] run: 0.528ms
[Debug] run: 0.549ms
[Debug] run: 0.475ms
[Debug] run: 0.530ms
[Debug] run: 0.494ms

Результат #2 Google Chrome 78.0.3892.0
run: 0.932861328125ms
run: 0.751953125ms
run: 0.4580078125ms
run: 0.678955078125ms
run: 0.424072265625ms
run: 0.505859375ms
run: 0.563720703125ms
run: 0.404052734375ms
run: 0.411865234375ms
run: 0.634033203125ms
run: 0.4169921875ms
run: 0.390869140625ms
run: 0.464111328125ms


#3 Хвостовая рекурсия и «батут»
Код #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")


Результат #3 Safari 12.1.2
[Debug] run: 0.936ms
[Debug] run: 0.792ms
[Debug] run: 0.882ms
[Debug] run: 0.826ms
[Debug] run: 0.968ms
[Debug] run: 0.818ms
[Debug] run: 1.681ms
[Debug] run: 0.777ms
[Debug] run: 1.109ms
[Debug] run: 0.832ms
[Debug] run: 0.826ms

Результат #3 Google Chrome 78.0.3892.0
run: 0.60888671875ms
run: 0.989990234375ms
run: 0.567138671875ms
run: 0.56005859375ms
run: 1.0087890625ms
run: 0.5400390625ms
run: 0.578125ms
run: 0.541015625ms
run: 0.557861328125ms
run: 1.97607421875ms
run: 0.570068359375ms
run: 0.593017578125ms
run: 0.530029296875ms
run: 0.89794921875ms
run: 0.590087890625ms


#4 Хвостовая рекурсия и «батут» (большое число)
Код #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")


Результат #4 Safari 12.1.2
[Debug] run: 33.693ms
[Debug] run: 24.564ms
[Debug] run: 25.313ms
[Debug] run: 23.262ms
[Debug] run: 24.848ms
[Debug] run: 23.909ms
[Debug] run: 24.248ms
[Debug] run: 32.416ms
[Debug] run: 24.090ms
[Debug] run: 23.986ms

Результат #4 Google Chrome 78.0.3892.0
run: 40.73681640625ms
run: 33.955078125ms
run: 40.907958984375ms
run: 37.693115234375ms
run: 28.929931640625ms
run: 30.7548828125ms
run: 29.720947265625ms
run: 40.8310546875ms
run: 31.5830078125ms
run: 30.712890625ms
run: 30.162841796875ms
run: 31.56103515625ms


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

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (31):

  1. Rsa97
    /#20547951

    Если мне не изменяет склероз, то хвостовую рекурсию практически всегда можно преобразовать в итерацию. Возможно, что запись функции при этом станет не такой красивой, но переполнения стека из-за рекурсии не будет.

    • Pand5461
      /#20548471 / +1

      Не изменяет, причём не практически всегда, а всегда.
      Насчёт того, что запись станет некрасивой — вряд ли. Преобразование к хвостовой рекурсии само по себе "портит" внешний вид. Даже сравнить примеры из статьи — в первом очевидно, что делает рекурсия, во втором мысленно всё равно нужно развернуть её в цикл, чтобы понять, что происходит.

      • Zenitchik
        /#20550865

        Пример из статьи — очень упрощённый.
        Практически интересен пример, когда функций несколько, и они могут вызывать друг друга, причём. Я обычно такое преобразовываю в возврат предыдущей функцией ссылки на следующую, а саму функцию выполняет цикл. ИМХО, настоящая хвостовая рекурсия — была бы красивее.

  2. Focushift
    /#20547953 / +1

    И? остановились на самом главном.
    Почему декоратор? что он делает и т.п.?
    Я вижу только увеличение глубины вызовов функции.

    • MikeMoore
      /#20547973

      Декоратор возвращает функцию, которая в цикле выполняет нашу функцию, без увеличения глубины вызовов как при рекурсии. В функцию передаются параметры и она сразу может быть вызвана вернув результат или другую функцию, которую мы будем вызывать на следующей итерации. Если кратно, мы просто в цикле выполняем якобы рекурсивную функцию, просто подставляя результат прошлой итерации.

    • CoolCmd
      /#20547979 / +1

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

  3. Mnemonik
    /#20547991 / +1

    генератор уже советовали вместо велосипеда с циклом?

  4. Gibrrr
    /#20547993 / +1

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

    • MikeMoore
      /#20548003

      Спасибо за комментарии, вижу уже несколько недостатков статьи, поэтому постараюсь ближайшем времени дополнить информацию и провести тесты производительности.

  5. python273
    /#20547999

    Только это не будет работать если нужно сделать больше одного рекурсивного вызова в функции


    Как-то делал обход глубины стека через генераторы на python:
    https://github.com/python273/precursion

    • Mingun
      /#20548025

      С концептуальной точки зрения будет, только нужно еще немного руками функцию доработать (а хотелось бы, конечно, чтобы это делал движок): просто вместо одного параметра-аккумулятора (s = 0 в статье) функция должна принимать вектор и сама стать векторной, на каждой итерации вычисляя сразу пачку значений. Тогда для основного алгоритма разворачивания рекурсии в цикл у нас остается всего один хвостовой вызов

  6. dem0n3d
    /#20548021

    Подробный разбор темы на HolyJS 2019 Piter.


  7. acupofspirt
    /#20548253 / +1

    Вячеслава Егорова на вас нет. Кто же так меряет производительность как у вас в примерах. Надо хотя бы показать интерпретатору что используете результат вызова функции. Иначе рискуете между вызовами time и timeEnd получить стрекотание сверчков при чистой функции)

  8. neurocore
    /#20548405 / -2

    Рекурсия в JS? Вы же не собираетесь на нём шахматный движок писать, это не подходящий инструмент. Остальные случаи прекрасно обходятся правильными алгоритмами.

  9. vlanko
    /#20548473

    Firefox 63 лимит 32-37000 (рандом)
    И на таких больших числах почему-то бутут быстрее…

  10. impwx
    /#20548695

    То есть:


    • Поддерживает только один рекурсивный вызов
    • Не работает без модификации исходной функции
    • Не работает с функциями, возвращающими некий тип (function оказывается зарезервирован под рекурсивный вызов)

    С такими ограничениями проще вообще обходить рекурсию стороной, всегда разворачивая ее в итеративную форму вручную.

    • aamonster
      /#20548945

      Дык вся суть хвостовой рекурсии – что у нас единственный вызов, причём он выполняется последним.

  11. aamonster
    /#20549895

    А эта схема с трамплином вообще работает? Да, рекурсия устраняется. Но, т.к. вы возвращаете из функции замыкание – оно сохраняет контекст. Когда на следующем проходе вы его вызываете – опять возвращается замыкание. С контекстом и ссылкой на контекст создавшей его функции (вдруг понадобятся переменные оттуда?). И так далее – создавая целый "стек" контекстов.
    Я где-то неправ?

    • Pand5461
      /#20550473 / +1

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

      • aamonster
        /#20550711

        Если транслятор достаточно умный – то может просто соптимизировать хвостовую рекурсию без трамплина, нет?

        • aamonster
          /#20551877

          Иными словами, мне интересно, есть ли реализации JS, которые оптимизируют цепочку контекстов, удаляя ненужные – но почему-то не оптимизируют Tail Call.

  12. force
    /#20550673

    Всегда хотел спросить, а что курили авторы ES6, когда включали оптимизиацию хвостовой рекурсии в стандарт? Т.е. это не возможности языка, а свойство рантайма. При этом его ещё особо и не проверить. Да и заполифиллить его нормальным образом нельзя. В результате получается фича, которую использовать нельзя, потому что на неподдерживаемом браузере всё развалится.

    • unel
      /#20551465

      ну, почему не проверить? немного наивный механизм, предполагающий константную максимальную глубину стека, но всё же:
      — сперва выполнить функцию, заведомо выполняющую переполнение стека вызова, тем самым, узнав его глубину
      — потом выполнить функцию с tco, с той же или чуть большей глубиной. если произошло переполнение стека вызовов — значит, tco нет, иначе — есть)

      вот с полифилами — да, беда. разве что только на уровне транспайлеров определять и преобразовывать в код с «трамплинами»

      но в целом, конкретно в JS, овчинка выделки не стоит)

      • force
        /#20551543

        Ну, глубина стека не определена, да и попытка её переполнить может привести к временному эпическому потреблению памяти или браузер от ужаса прибьёт все скрипты на странице. Опасненький такой способ. :) И опять же, писать две ветки кода, одна на случай оптимизации, другая циклом — достаточно бестолковое времяпрепровождение. Раз уж написали универсальный код, зачем поддерживать код с хвостами.

        • unel
          /#20551761

          function dd(deep = 0) { try { return dd(deep + 1) } catch (e) { return deep; } }
          dd(); // 10450
          
          function dd(deep = 0) { try { return 0 + dd(deep + 1) } catch (e) { return deep; } }
          dd(); // 9646
          
          function dd(deep = 0) { try { return 0 + 0 + dd(deep + 1) } catch (e) { return deep; } }
          dd(); // 9646
          


          У меня ничего не взвыло и не упало (но, конечно, единичный случай — не показатель) =)

          Самое забавное, что код «с TCO» (первый) вызывается с чуть большей глубиной, нежели «без TCO».

          Т.е. мой «наивный» алгоритм решит, что в данном случае браузер поддерживает TCO, хотя на самом деле это не так

          • unel
            /#20551771

            Ещё одна забавная вариация :-)

            function dd() { try { return 1 + dd() } catch (e) { return 0; } }
            dd(); // 12541
            

            • force
              /#20551885

              Firefox. Очень забавный результат. Каждый раз разный :)

              function dd(deep = 0) { try { return dd(deep + 1) } catch (e) { return deep; } }
              dd();
              21393
              dd();
              21089
              dd()
              21269
              dd()
              23559
              dd()
              23559
              dd()
              23559
              dd()
              23408
              dd()
              23573
              dd()
              

    • Mingun
      /#20551783

      Все правильно сделали. Это напрашивающаяся сама собой оптимизация для языка, нацеленного на широкое использование функционального подхода.


      А зачем вам проверять это свойство? Вы хотите написать 2 версии кода с надеждой на хвостовую рекурсию и без нее? А зачем? Обычная версия будет работать везде, поэтому если у вас стоят требования, работать там, где такой оптимизации нет, то ставите себе линтер на запрет рекурсивных вызовов и нет проблем.


      Я даже не представляю, что значить полифиллить хвостовую рекурсию. А для class или для геттеров/сеттеров таких вопросов не возникало?

      • force
        /#20551857

        > Все правильно сделали. Это напрашивающаяся сама собой оптимизация для языка, нацеленного на широкое использование функционального подхода.
        Тут разница в том, что это не свойство языка, ни синтаксис, ничего. Это некое абстрактное свойство рантайма, при этом оно живёт не в статусе работает/не работает. А в статусе работает хорошо/работает плохо и иногда падает по OOM.
        При этом в реальности — хром вначале добавил эту оптимизацию, потом выпилил. Т.е. если кто-то заточился на эту фичу, поимел грабли. Код развалился просто так.

        > то ставите себе линтер на запрет рекурсивных вызовов и нет проблем.
        Рекурсия вполне может использоваться и в обычном виде, запрещать рекурсию саму по себе — это очень странно. А линтёр, определяющий хвостовую рекурсию… ну такое…

        > Я даже не представляю, что значить полифиллить хвостовую рекурсию. А для class или для геттеров/сеттеров таких вопросов не возникало?
        Я тоже. Но для классов — вполне себе всё полифилится. Хотя, я может неправильно термин подобрал. Наверное транспайлинг тут лучше звучит.

        • Mingun
          /#20551907

          При этом в реальности — хром вначале добавил эту оптимизацию, потом выпилил.

          Ну так не используйте/не затачивайтесь на бажные реализации. Когда допилят и вы сможете себе позволить поддерживать их, тогда и начинайте использовать новые фишки, если все так плохо. Но понимаете, без стандартизации хорошо не будет никогда. А так есть надежда, что через 5 лет у всех все будет работать.


          Рекурсия вполне может использоваться и в обычном виде, запрещать рекурсию саму по себе — это очень странно.

          Любую рекурсию можно свести к хвостовой, а хвостовую — развернуть в цикл. Так что либо запрещать всю, либо никакую.


          Наверное транспайлинг тут лучше звучит.

          Вот транспайлинг — это да, тогда ясно. Рекурсия точно также транспайлится — берется, и разворачивается в цикл. Т.е. теперь этой оптимизацией будет заниматься не рантайм, а транспайлер.