хвостовой вызов
1. Определения
Хвостовой вызов — очень важная концепция в функциональном программировании.Когда функция выполняется, последним шагом является возврат вызова другой функции, который называется хвостовым вызовом.
Обратите внимание, что не имеет значения, как здесь вызывается функция, можно использовать следующие методы:
函数调用: func(···)
方法调用: obj.method(···)
call调用: func.call(···)
apply调用: func.apply(···)
И только следующие выражения будут содержать хвостовые вызовы:
条件操作符: ? :
逻辑或: ||
逻辑与: &&
逗号: ,
Пример:
const a = x => x ? f() : g();
// f() 和 g() 都在尾部。
const a = () => f() || g();
// g()有可能是尾调用，f()不是
// 因为上述写法和下面的写法等效：
const a = () => {
const fResult = f(); // not a tail call
if (fResult) {
return fResult;
} else {
return g(); // tail call
}
}
// 只有当f()的结果为falsey的时候，g()才是尾调用
const a = () => f() && g();
// g()有可能是尾调用，f()不是
// 因为上述写法和下面的写法等效：
const a = () => {
const fResult = f(); // not a tail call
if (fResult) {
return g(); // tail call
} else {
return fResult;
}
}
// 只有当f()的结果为truthy的时候，g()才是尾调用
const a = () => (f() , g());
// g()是尾调用
// 因为上述写法和下面的写法等效：
const a = () => {
f();
return g();
}
2. Оптимизация хвостового вызова
Когда вызывается функция, запись сохраняется в стеке вызовов. Каждая запись называется фреймом вызова. Каждый раз, когда вызывается функция, запись помещается в стек. следующее изображение:
function foo () { console.log(111); }
function bar () { foo(); }
function baz () { bar(); }
baz();
Этот результат объясняется тем, что каждая функция вызывает другую функцию безreturnЭто вызов, поэтому JS-движок будет думать, что вы не закончили выполнение, и сохранит ваш кадр вызова.
baz()внутри вызоваbar()функция, неreturnвызов, поэтому сохраните свой собственный кадр вызова в стеке вызовов, в то время какbar()Фрейм вызова функции генерируется в стеке вызовов.bar()функция вызывается сноваfoo()функция, которая, наконец, выполняется дляfoo()При вызове функции никакие другие функции не вызываются, и здесь не отображается объявление.return, так что здесь по умолчаниюreturn undefined.
foo()После завершения выполнения уничтожить свои записи в стеке вызовов, и уничтожить их в свою очередьbar()а такжеbaz()Кадр вызова и, наконец, завершить весь процесс.
Если приведенный выше пример изменить следующим образом:
function foo () { console.log(111); }
function bar () { return foo(); }
function baz () { return bar(); }
baz();
Обратите внимание:Оптимизация хвостового вызова работает только в строгом режиме.
В нестроенном режиме большинство двигателей будут содержать оба атрибута, чтобы разработчики проверяют стек вызова:
- func.arguments: func параметр, указывающий на недавний вызов, содержащийся
- func.caller: относится к функции, которая последний раз вызывалась для func.
В оптимизации хвостовых вызовов эти свойства больше не используются, поскольку соответствующая информация могла быть удалена и была удалена. Поэтому строгий режим запрещает эти атрибуты, а оптимизация хвостовых вызовов эффективна только в строгом режиме.
Если бы действовала оптимизация хвостовых вызовов, блок-схема выглядела бы так:
Мы можем ясно видеть, что, поскольку хвостовой вызов является последним шагом функции, нет необходимости хранить запись вызова внешней функции, пока запись вызова внутренней функции непосредственно заменяется записью вызова внешней функции. внешняя функция В стеке всегда находится только один фрейм вызова.
это называетсяоптимизация хвостового вызова, если все функции являются хвостовыми вызовами, то в стеке вызовов всегда будет только один кадр вызова, что сэкономит большую часть памяти, что такжеОптимизация хвостовой мелодии.
хвостовая рекурсия
1. Определения
Сначала рассмотрим рекурсию Когда функция вызывает сама себя, это называется рекурсией.
function foo () {
foo();
}
Вышеприведенная операция называется рекурсией, но обратите внимание, что здесь нет конечного условия. Это мертвая рекурсия, поэтому будет сообщено об ошибке переполнения стека. При написании кода обязательно добавьте в рекурсию конечное условие.
Так что же такое хвостовая рекурсия? Ранее мы знали концепцию хвостовых вызовов.Когда функция tail вызывает сама себя, она называетсяхвостовая рекурсия.
function foo () {
return foo();
}
2. Функция
Так в чем же разница между хвостовой рекурсией и рекурсией? Мы просим следующеефакториалВзгляните на пример:
function factorial (num) {
if (num === 1) return 1;
return num * factorial(num - 1);
}
factorial(5); // 120
factorial(10); // 3628800
factorial(500000); // Uncaught RangeError: Maximum call stack size exceeded
Выше приведен пример использования рекурсии для вычисления факториала. Память, выделенная операционной системой для стека вызовов JS-движка, ограничена по размеру. Если вычисленное число достаточно велико, чтобы превысить максимальный диапазон памяти, произойдет ошибка переполнения стека. .
Здесь 500000 не является критическим значением, но я использовал число, достаточное для переполнения стека.
Что, если мы воспользуемся хвостовой рекурсией для вычисления факториалов?
'use strict';
function factorial (num, total) {
if (num === 1) return total;
return factorial(num - 1, num * total);
}
factorial(5, 1); // 120
factorial(10, 1); // 3628800
factorial(500000, 1); // 分情况
// 注意，虽然说这里启用了严格模式，但是经测试，在Chrome和Firefox下，还是会报栈溢出错误，并没有进行尾调用优化
// Safari浏览器进行了尾调用优化，factorial(500000, 1)结果为Infinity，因为结果超出了JS可表示的数字范围
// 如果在node v6版本下执行，需要加--harmony_tailcalls参数，node --harmony_tailcalls test.js
// node最新版本已经移除了--harmony_tailcalls功能
С помощью хвостовой рекурсии мы уменьшаем сложность с O(n) до O(1), что может сэкономить много времени вычислений, если данные достаточно велики. Отсюда видно, чтооптимизация хвостового вызоваРекурсия настолько важна для рекурсивных операций, что некоторые языки функционального программирования записывают ее в спецификацию языка.
Избегайте перезаписи рекурсивных функций
Реализация хвостовой рекурсии часто требует перезаписи рекурсивной функции, чтобы последний шаг вызывал только саму себя. Для этого вам нужно переписать все промежуточные переменные, используемые внутри функции, как параметры функции, точно так же, как функция factorial() выше.
Недостатком этого является то, что семантика неочевидна.Зачем для вычисления факториальной функции передавать еще один параметр, называемый total? Есть два решения этой проблемы:
1. Значение параметра ES6 по умолчанию
'use strict';
function factorial (num, total = 1) {
if (num === 1) return total;
return factorial(num - 1, num * total);
}
factorial(5); // 120
factorial(10); // 3628800
2. Используйте семантически непротиворечивую функцию для вызова переписанной хвостовой рекурсивной функции.
function tailFactorial (num, total) {
if (num === 1) return total;
return tailFactorial(num - 1, num * total);
}
function factorial (num) {
return tailFactorial(num, 1);
}
factorial(5); // 120
factorial(10); // 3628800
Приведенный выше способ написания на самом деле немного похож на каррирование функции, но он не полностью соответствует концепции каррирования.каррирование функцийПреобразует функцию, которая принимает несколько аргументов, в функцию, которая принимает один аргумент (первый аргумент исходной функции), и возвращает новую функцию, которая принимает остальные аргументы и возвращает результат.
Концепция выглядит очень запутанной, давайте возьмем пример, чтобы почувствовать это:
// 普通加法函数
function add (x, y, z) {
return x + y + z;
}
add(1, 2, 3); // 6
// 改写为柯里化加法函数
function add (x) {
return function (y) {
return function (z) {
return x + y + z;
}
}
}
add(1)(2)(3); // 6
Видно, что функция Coridian находит переменную в родительском поле путем закрытия и, наконец, добавляет выходные результаты. На этом примере может быть не видно, почему используется корреляция.В чем преимущества, об этом потом поговорим, сначала приведем концепцию.
— это метод преобразования функции, которая принимает несколько параметров, в функцию, которая принимает один параметр (первый параметр исходной функции) и возвращает новую функцию, которая принимает остальные параметры и возвращает результат.
Если вы перепишете факторный пример с каррированием:
// 柯里化函数
function curry (fn) {
var _fnArgLength = fn.length;
function wrap (...args) {
var _args = args;
var _argLength = _args.length;
// 如果传的是所有参数，直接返回fn调用
if (_fnArgLength === _argLength) {
return fn.apply(null, args);
}
function act (...args) {
_args = _args.concat(args);
if (_args.length === _fnArgLength) {
return fn.apply(null, _args);
}
return act;
}
return act;
}
return wrap;
}
// 尾递归函数
function tailFactorial (num, total) {
if (num === 1) return total;
return tailFactorial(num - 1, num * total);
}
// 改写
var factorial = curry(tailFactorial);
factorial(5)(1); // 120
factorial(10)(1); // 3628800
Это способ письма в соответствии с концепцией каррирования, описанной в статье Руан Ифэн:
function currying(fn, n) {
return function (m) {
return fn.call(this, m, n);
};
}
function tailFactorial(n, total) {
if (n === 1) return total;
return tailFactorial(n - 1, n * total);
}
const factorial = currying(tailFactorial, 1);
factorial(5) // 120
Я лично думаю, что этот способ записи на самом деле не является каррированием, потому что многопараметрический tailFacrotial переписан не для приема одного параметра, а для другого способа записи, который имеет то же значение, что и следующее:
function factorial (num) {
return tailFactorial(num, 1);
}
function tailFactorial (num, total) {
if (num === 1) return total;
return tailFactorial(num - 1, num * total);
}
factorial(5); // 120
factorial(10); // 3628800
конец
В этой статье мы в основном обсуждали оптимизацию хвостовых вызовов и каррирование. Следует отметить, что после тестирования Chrome и Firefox не оптимизируют хвостовые вызовы, а Safari оптимизирует хвостовые вызовы. В более поздних версиях Node также удалена возможность оптимизации хвостовых вызовов с помощью параметра --harmony_tailcalls.
Если у вас есть какие-либо вопросы, вы можете оставить сообщение.мой блог сайт, давай~~
Добро пожаловать, чтобы обратить внимание на мой общедоступный номер
Ссылка на ссылку
Уууу. Руан Ифэн.com/blog/2015/0… nuggets.capable/post/684490… GitHub.com/Ламаду/Ламаду…