Знаете ли вы, что рекурсию можно оптимизировать с помощью концепции, которая работает подобно тому, как мы прыгаем на батуте.
Позвольте мне уточнить, что в рекурсии функция вызывает себя, не завершая собственное выполнение. Поскольку выполнение не может быть завершено до тех пор, пока следующий вызов функции не вернется (или не завершит выполнение), и это продолжается для дальнейших вызовов функций. Это создает стек незавершенных вызовов функций, и из-за ограничений памяти может быть только определенный предел вызовов функций, разрешенных в стеке. Но ситуации с большим количеством вызовов рекурсии в javascript не приводят к переполнению стека, javascript предотвращает достижение этого предела, выдавая ошибку диапазона.
Рассмотрим этот пример,
function increment(test) {
try {
if (test > 1000000) return test;
return increment(++test);
} catch {
console.log("test===>", test);
}
}
Если вы запустите приведенный выше код, он довольно скоро попадет в блок catch. На macbook air 2k19 максимальное значение составило около 10 тысяч. Это означает, что произошло переполнение стека.
Что ж, в приведенном выше примере функция increment вызывает сама себя в операторе return, это добавляет в стек еще один вызов функции increment, и этот вызов снова добавит к складывать еще один вызов функции для increment, и это продолжается до тех пор, пока не будет достигнуто базовое условие, когда initialValue станет больше, чем 1000000, но это никогда не произойдет. бывает.
Но здесь, если вы заметили, что вызов рекурсии является хвостовым вызовом. Хвостовой вызов — это когда рекурсивный вызов происходит только в конце функции в операторе return.
Почему нам нужно беспокоиться о хвостовом звонке и какое это имеет значение?
Техника батута, которую мы собираемся изучить, работает только тогда, когда у нас есть рекурсия, определенная как хвостовой вызов. Это станет более ясно, когда мы посмотрим на батут, давайте запрыгнем на него.
Батут рекурсии» предоставлен Кайлом Симпсоном. Батут — это не что иное, как оболочка нашей рекурсивной функции. В рекурсии мы вызываем функцию из функции. В батутной рекурсии мы вызываем функцию, которая, в свою очередь, возвращает функцию (не вызов функции и, следовательно, завершение текущего выполнения функции), и эта возвращенная функция снова вызывает нашу рекурсивную функцию.
Это немного сбивает с толку, я знаю, но прочитайте еще раз, я уверен, что вы поймете. Вот так выглядит обертка батута,
function trampoline(f) {
return function enclose(...args) {
let result = f(...args);
while (typeof result === "function") {
result = result();
}
return result;
};
}
Приведенная выше функция батута принимает функцию в качестве аргумента и возвращает функцию с именем enclose, вы можете называть ее как угодно.
Чтобы использовать вышеуказанную оболочку, нам нужно немного изменить нашу рекурсивную функцию.
function increment(test) {
try {
if (test > 1000000000) return test;
return () => increment(++test);
} catch {
console.log("test===>", test);
}
}
Вы заметили разницу? Мы изменили наш хвостовой вызов, вместо этого возвращая анонимную функцию. Так что это больше не вызов функции, а возвращает функцию, которая вызывает нашу рекурсивную функцию, которая в данном случае является инкрементной.
Теперь, если мы передадим вышеуказанную функцию нашей оболочке батута, наш код будет выглядеть так.
const trampolinedIncrement = trampoline(function increment(test) {
try {
if (test > 1000000000) return test;
return () => increment(++test);
} catch {
console.log("test===>", test);
}
});
console.log(trampolinedIncrement(1));
Когда вы запустите приведенный выше код, ошибки диапазона не будет, и вы получите 1000000001 в качестве вывода. Приведенный выше код занял около 20 секунд на Macbook Air.
Но что только что произошло?
Наш код только что встал на батут, LOL! Вот весь код,
function trampoline(f) {
return function enclose(...args) {
let result = f(...args);
while (typeof result === "function") {
result = result();
}
return result;
};
}
const trampolinedIncrement = trampoline(function increment(test) {
try {
if (test > 1000000000) return test;
return () => increment(++test);
} catch {
console.log("test===>", test);
}
});
console.log(trampolinedIncrement(1));
Когда мы трамплинили функцию increment, мы получили определение функции enclose в trampolinedIncrementгде fявляется функцией инкремента. Итак, теперь, когда мы вызываем trampolinedIncrement
с начальными аргументами, она вызывает f, а результатом этого выполнения является анонимная функция, которая сохраняется в результате. Затем мы продолжаем вызывать функцию result, пока она не вернет функцию typeof и в конце вернет результат.
Если вы все еще запутались, просто спросите в комментариях, я уточню. Вы можете связаться со мной в твиттере @heypran.
Подводя итог, в обычной рекурсии размер стека продолжает увеличиваться, потому что текущий вызов функции еще не завершил свое выполнение, но вызывает другую функцию. Эта функция снова вызывает другую функцию, и это продолжает повторяться. Это приводит к переполнению стека.
В батутном сценарии мы не вызываем рекурсивную функцию напрямую, вместо этого мы завершаем текущий вызов функции, возвращая функцию, которая, в свою очередь, вызывает нашу рекурсивную функцию. Это приводит к тому, что размер нашего стека всегда увеличивается только на единицу, а когда он заканчивается, он снова уменьшается на единицу. Этот переход между функциями называется батут. Я нахожу это довольно крутым!
Ваше здоровье!
Счастливый день!
