В обычном коде рекурсия очень распространена, но проблема переполнения стека вызовов, которую она может вызвать, иногда вызывает головную боль:

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

Чтобы решить проблему переполнения стека вызовов во время рекурсии, в дополнение к изменению рекурсивной функции на итеративную форму, измените ее на尾递归Это также может быть решено в виде (хотя многие браузеры в настоящее время не оптимизируют хвостовую рекурсию (вызов хвоста), это все равно приведет к переполнению стека, но все же важно понимать метод оптимизации хвостовой рекурсии. И мы можем используйте унифицированную функцию инструмента, чтобы положить хвостовую рекурсию, преобразованную в форму, которая не переполняется, которая будет раскрыта один за другим ниже).
в обсуждении尾递归Перед этим давайте разбираться尾调用, и как движок js его оптимизирует.

хвостовой вызов

ФункцияaПоследним действием является вызов функцииb, то для функцииbФорма вызова есть尾调用. Например, в следующем кодеfn1Вызов является хвостовым вызовом:

const fn1 = (a) => {
  let b = a + 1;
  return b;
}

const fn2 = (x) => {
  let y = x + 1;
  return fn1(y);        // line A
}

const result = fn2(1);  // line B

Определите, является ли это хвостовым вызовом

const a = () => {
  b();
}

здесьbВызов не является хвостовым вызовом, потому что функцияaвызовbЗатем неявно выполняет абзацreturn undefined, как в следующем коде:

const a = () => {
  b();
  return undefined;
}

const a = () => b() || c();
const a1 = () => b() && c();

здесьaа такжеa1серединаbни один尾调用, потому что после его вызова есть еще действия, чтобы судить и, возможно, дляcпозвони, покаcобе尾调用.

const a = () => {
  let result = b();
  return result;
}

Для этого кода есть статья, в которой говоритсяbнет尾调用, даже если он такой же, какconst a = () => b()эквивалентны, в то время как последний явно является хвостовым вызовом. Это касается вопроса определения, я не думаю, что нужно слишком запутываться.尾调用Настоящая цель - оптимизировать и предотвратить переполнение стека, я протестировал поддержку尾调用Браузер Safari выполняет рекурсивную функцию с аналогичным кодом в строгом режиме, и результат не вызовет переполнения стека, поэтому Safari оптимизирует эту форму кода.

хвостовая рекурсия

Теперь настала очередь главного героя этой статьи-尾递归, это действительно просто尾调用Частный случай , когда каждый рекурсивный вызов尾调用, взгляните на следующий простой рекурсивный код:

const sum = (n) => {
  if (n <= 1) return n;
  return n + sum(n-1)
}

const sum = (n, prevSum = 0) => {
  if (n <= 1) return n + prevSum;
  return sum(n-1, n + prevSum)
}

Даже если большинство браузеров будут поддерживать его в будущем尾调用Оптимизирован, по спецификации es6, будет срабатывать только в строгом режиме, что явно очень неудобно. Но мы можем использовать единый подход к尾递归Функция обрабатывается, чтобы она больше не вызывала переполнение стека.

Trampoline

Trampolineправда尾递归Техника обработки функций. Нам нужно поставить вышеsumПреобразуйте функцию, а затем используйтеtrampolineФункция может справиться с этим:

const sum0 = (n, prevSum = 0) => {
  if (n <= 1) return n + prevSum;
  return () => sum0(n-1, n + prevSum)
}
const trampoline = f => (...args) => {
  let result = f(...args);
  while (typeof result === 'function') {
    result = result();
  }
  return result;
}
const sum = trampoline(sum0);

console.log(sum(1000000)); // 不会栈溢出

Конечно, если метод можно записать как尾递归В виде , его также можно записать в итеративной форме (на самом деле все рекурсии теоретически могут быть записаны в итеративной форме, но некоторые из них очень сложно реализовать с помощью итерации), но в некоторых сценариях может быть более интуитивно понятно использовать рекурсию, если ее можно преобразовать в尾递归, вы можете напрямую использоватьtrampolineфункцию, либо переписать ее как итерационный метод (или в особых случаях в поддержку尾调用запускать в строгом режиме в оптимизированных браузерах)

Ссылаться на:

blog.log rocket.com/using-tramp…
2 али ненавидит.com/2015/06/тоже…
Ууху. Call.com/question/30…

---------продлить---------

Эй, разве это не должно быть кончено, почему еще есть контент!

Следующее содержание - это всего лишь приемы и уловки, и не обязательно могут быть применены на практике.Они предназначены только для развлечения или развития идей (следующее не является серьезным содержанием этой статьи, поэтому стиль рисования может быть другим, просто пишите это по желанию~)

странные трюки

Воспользуемся преимуществами асинхронного механизма js! Поместите рекурсивный вызов в settimeout для асинхронного выполнения и поместите следующий рекурсивный вызов в settimeout после завершения каждого рекурсивного выполнения. Таким образом, после того, как функция будет выполнена один раз, она вернется напрямую, выйдет из стека вызовов, а следующая функция рекурсивного вызова будет помещена в очередь обратного вызова по settimeout.В очереди обратного вызова js всегда будет должна выполняться не более одной функции.Конечно, в стеке вызовов функций всегда есть не более одной функции~ (если не учитывать другие функции)

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

sum2 = (num, callback, sum = 0) => {
  if (num < 1) {
    callback(sum);
    return;
  }

  setTimeout(() => sum2(num-1, callback, sum + num), 0);
}

sum2(1000, v => console.log(v));

бегать!

Почему так медленно?

Поскольку у settimeout есть задержка, минимум составляет 4 мс, поэтому каждая рекурсия задерживается settimeout на некоторое время, и производительность сильно снижается! Хотя это всего лишь трюк, но такая низкая производительность все равно раздражает и требует оптимизации! (*￣︿￣)

Подумайте еще раз, каждый settimeout можно понимать как очистку текущего стека вызовов, а затем выполнение функции в settimeout. Тогда мы не сможем совместить синхронный рекурсивный вызов с settimeout! Каждые 5000 слоев рекурсии, settimeout один раз! (5000 — это просто относительно безопасное число, которое может обрабатываться по-разному для верхнего предела разных браузеров)

sum3 = (num, callback, sum = 0, batchLeft = 5000) => {
  if (num < 1) {
    callback(sum);
    return;
  }
  batchLeft--;
  if (batchLeft > 0) 
  sum3(num-1, callback, sum + num, batchLeft)
  else setTimeout(() => sum3(num-1, callback, sum + num, 5000), 0);}

sum3(30000, v => console.log(v));

(Если вы действительно хотите ее использовать, лучше всего инкапсулировать эту функцию и не раскрывать две переменные sum и batchLeft)

Таким образом, мы используем js для реализации рекурсивной функции, которая никогда не вызовет переполнения стека! Батут не нужен! Нет необходимости менять итерации! Это настоящая рекурсия! (Даже вызовы в settimeout рекурсивны, но с задержкой). Просто метод написания очень многословен, а функции, которые могут выполняться синхронно, были заменены проблемными асинхронными функциями.

На самом деле, давайте подумаем еще раз. Сама эта форма вызова settimeout является своего рода хвостовой рекурсией. Мы используем settimeout для задержки выполнения рекурсивной функции до конца, и она откладывается до тех пор, пока не закончится выполнение предыдущей функции и стек извлекается, что можно понимать как мы. Используя характеристики самой асинхронности js, движок js выполняет нетрадиционную «оптимизацию хвостового вызова». Разве не интересно σ`∀´)σ

(Это так интересно, почему вы не обращаете внимания? σ`∀´)σ В будущем я напишу более интересный контент σ`∀´)σ