1. Рекурсия
1. Рекурсивное значение:
Процедура или функция в своем определении или описании имеет метод прямого или косвенного вызова самой себя, который обычно преобразует большую и сложную проблему в меньшую проблему, аналогичную исходной задаче, которую необходимо решить.Только рекурсивная стратегия.Небольшое количество программ может быть используется для описания повторяющихся вычислений, необходимых для процесса решения задачи, что значительно сокращает объем кода программы.
2. Преимущества рекурсии
- лаконичный
- В предварительном заезде, внешнему устройству и почтовому прохождению дерева реализация рекурсии, очевидно, намного проще, чем у цикла.
Пример 1
function foo(i) {
if (i < 0)
return;
console.log('begin:' + i);
foo(i - 1);
console.log('end:' + i);
}
foo(3);
// begin:3
// begin:2
// begin:1
// begin:0
// end:0
// end:1
// end:2
// end:3
Чтобы понять приведенный выше код с точки зрения стека функций, выполните следующие действия:
- Входя в функцию foo(3) в первый раз, параметр в это время равен 3, предполагая, что foo1() помещается в стек выполнения Сначала i не меньше 0, начало вывода: 3
- Введите foo(i - 1), параметр равен 3-1 = 2, предполагая, что foo2() помещается в стек выполнения. i не меньше 0, начало вывода: 2
- Введите foo(i - 1), параметр равен 2-1 = 1, предполагая, что foo3() помещается в стек выполнения. i не меньше 0, начало вывода: 1
- Введите foo(i - 1), параметры 1-1 = 0, при условии, что foo4() помещается в стек выполнения. i не меньше 0, начало вывода: 0
- Привод Foo (I - 1), 0-1 = -1 параметр предполагается, что Foo5 () нажата в стек выполнения Я меньше 0 возврата
- Стек выполнения извлекает текущую функцию foo5(), входит в предыдущую функцию foo4() и продолжает выполнение незавершенного кода. выходной конец: 0
- Стек выполнения извлекает текущую функцию foo4(), входит в предыдущую функцию foo3() и продолжает выполнение незавершенного кода. выходной конец: 1
- Стек выполнения извлекает текущую функцию foo3(), входит в предыдущую функцию foo2() и продолжает выполнение незавершенного кода. конец выхода: 2
- Стек выполнения извлекает текущую функцию foo2(), входит в предыдущую функцию foo1() и продолжает выполнение незавершенного кода. Выходной конец: 3
- Стек выполнения извлекает текущую функцию foo1(), и весь стек выполнения выполняется.
Пример 2 Факторная функция
function factorial(n) {
// console.trace()
if (n === 0) {
return 1
}
return n * factorial(n - 1)
}
factorial(5)
// 拆分成分步的函数调用
// factorial(5) = factorial(4) * 5
// factorial(5) = factorial(3) * 4 * 5
// factorial(5) = factorial(2) * 3 * 4 * 5
// factorial(5) = factorial(1) * 2 * 3 * 4 * 5
// factorial(5) = factorial(0) * 1 * 2 * 3 * 4 * 5
// factorial(5) = 1 * 1 * 2 * 3 * 4 * 5
Ниже приведен пример работы вышеуказанной функции
Если вы вставите console.trace() в факториальную функцию, чтобы увидеть состояние стека вызовов каждый раз, когда функция запускается, когда рекурсия достигает вызоваfactorial(5) = factorial(0) * 1 * 2 * 3 * 4 * 5, вывод следующий:
console.trace
factorial @ VM159:2
factorial @ VM159:7
factorial @ VM159:7
factorial @ VM159:7
factorial @ VM159:7
factorial @ VM159:7
(anonymous) @ VM159:10
3. Проблема рекурсии (недостаток)
- представление: Как показано в приведенном выше примере: если предположить, что значение входящего параметра особенно велико, стек вызовов будет очень большим, что в конечном итоге может превысить размер кэша стека вызовов и привести к сбою программы и невозможности ее выполнения. Каждый вызов функции будет выделять место в стеке памяти, а емкость стека каждого процесса ограничена.Когда слоев вызовов слишком много, емкость стека будет превышена, что приведет к переполнению стека.
-
эффективность:
- Рекурсия сама по себе является вызовом функции, а вызовы функций требуют времени и места: каждый вызов функции должен выделять место в стеке памяти для сохранения параметров, возврата адресов и временных переменных, а также для помещения данных и данных в стек. .
- Многие вычисления в рекурсии повторяются.Поскольку его суть состоит в том, чтобы разложить проблему на две или более небольших задач, а несколько небольших задач имеют перекрывающиеся части, существуют повторяющиеся вычисления, такие как рекурсия последовательности Фибоначчи.
Способ решить проблему производительности рекурсии — использовать хвостовую рекурсию.
2. Хвостовая рекурсия
Хвостовая рекурсия — это рекурсивный способ записи, позволяющий избежать постоянного помещения функций в стек, что в конечном итоге приводит к переполнению стека. Установив параметр накопления, и каждый раз текущее значение накапливается, а затем рекурсивно вызывается. С помощью хвостовой рекурсии мы можемУменьшить сложность с O(n) до O(1)
Давайте сначала поговорим о хвостовых вызовах, чтобы понять хвостовую рекурсию.
Хвостовой вызов относится к ситуации, когда последним действием в функции является возврат результата вызова функции, то есть возвращаемое значение нового вызова на последнем шаге напрямую возвращается возвращаемым результатом текущей функции. .
Представление кода:
function f(x) {
a(x)
b(x)
return g(x) //函数执行的最后调用另一个函数
}
1. Основное понимание хвостового вызова
Чтобы увидеть, когда функция вызывает другую функцию,Сама может быть "отпущена"
2. Преимущества хвостового вызова
Возьмите следующий стек вызовов функций и кадр вызова в качестве примера.
function f(x) {
res = g(x)
return res+1
}
function g(x) {
res = r(x)
return res + 1
}
function r(x) {
res = x + 1
return res + 1
}
Решите риск переполнения стека с помощью хвостовых вызовов
function f() {
m = 10
n = 20
return g(m + n)
}
f()
// 等同于
function f() {
return g(30)
}
f()
// 等同于
g(30)
В приведенном выше коде мы видим, что после того, как мы вызвали g, он не имеет ничего общего с f, и функция f завершается, поэтому при выполнении последнего шага запись вызова f() может быть полностью удалена, и только запись звонков g(30) сохраняется Запись звонков.
Значение хвостового звонкаЕсли функция оптимизирована как хвостовой вызов, вполне возможно добиться одного кадра вызова при каждом ее выполнении, что значительно сэкономит память и повысит энергоэффективность.
3. Хвостовая рекурсия = хвостовой вызов + рекурсия
function factorial(n, total = 1) {
// console.trace()
if (n === 0) {
return total
}
return factorial(n - 1, n * total)
}
Шаги для вызова функции factorial(3) следующие:
factorial(3, 1)
factorial(2, 3)
factorial(1, 6)
factorial(0, 6) // n = 0; return 6
Стек вызовов больше не нуждается в многократном добавлении факториала, поскольку каждый рекурсивный вызов больше не зависит от значения предыдущего рекурсивного вызова. Следовательно, сложность пространства равна o(1) вместо 0(n). Проверьте консоль и обнаружите, что результат третьего вывода выглядит следующим образом:
console.trace
factorial @ VM362:2
factorial @ VM362:7
factorial @ VM362:7
factorial @ VM362:7
(anonymous) @ VM362:9
Поскольку сказано, что стек вызовов больше не должен помещать факториал несколько раз, почему результат все еще не помещается в стек каждый раз, когда он вызывается, а только один факториал?
Правильный способ его использования должен быть
'use strict';
function factorial(n, total = 1) {
// console.trace()
if (n === 0) {
return total
}
return factorial(n - 1, n * total)
}
// 注意，虽然说这里启用了严格模式，但是经测试，在Chrome和Firefox下，还是会报栈溢出错误，并没有进行尾调用优化
// Safari浏览器进行了尾调用优化，factorial(500000, 1)结果为Infinity，因为结果超出了JS可表示的数字范围
// 如果在node v6版本下执行，需要加--harmony_tailcalls参数，node --harmony_tailcalls test.js
// 但是node最新版本已经移除了--harmony_tailcalls功能
3. Мемоизация
Мемоизация изначально была методом, используемым для оптимизации компьютерных программ для ускорения вычислений путем сохранения результата вызова функции и возврата результата при передаче одних и тех же аргументов. Большинство из них следует использовать в рекурсивных функциях. Мемоизация — это метод оптимизации, который позволяет избежать ненужных повторных вычислений и может повысить скорость вычислений.
В качестве примера возьмем факториальную функцию:
1. Не используйте мемоизацию
const factorial = n => {
if (n === 1) {
return 1
} else {
return factorial(n - 1) * n
}
}
2. Используйте запоминание
const cache = [] // 定义一个空的存放缓存的数组
const factorial = n => {
if (n === 1) {
return 1
} else if (cache[n - 1]) { // 先从cache数组里查询结果，如果没找到的话再计算
return cache[n - 1]
} else {
let result = factorial(n - 1) * n
cache[n - 1] = result
return result
}
}
3. Используйте мемоизацию с замыканиями
const factorialMemo = () => {
const cache = []
const factorial = n => {
if (n === 1) {
return 1
} else if (cache[n - 1]) {
console.log(`get factorial(${n}) from cache...`)
return cache[n - 1]
} else {
let result = factorial(n - 1) * n
cache[n - 1] = result
return result
}
}
return factorial
}
const factorial = factorialMemo()
4. Резюме
Запоминание может каждый раз сохранять возвращаемое значение функции в массиве или объекте.При следующем вычислении вычисленные и возвращенные данные могут быть напрямую прочитаны без многократного повторения одного и того же вычисления.Это способ изменить пространство на время, этот метод можно использовать в частичной рекурсии для повышения эффективности рекурсии.