Рекурсия Flashcards
Рекурсия
Стек - (Первый пришел последний вышел)
CallStack - функция, если она внутри вызывает другую функцию, то та другая функция кладется сверху (как стопка тарелок) и пока она не выполнится, нижняя тоже не сможет выполниться
- шарж рекурсия
- условия выхода из рекурсии
Рекурсия - функция, когда вызывает саму себя, пока не выполнится условие.
Если условие не выполнится?
Постоянно будет вызываться функция, пока не переполнится call stack и появится ошибка.
Перед тем как разбирать как работает рекурсия надо понимать что такое стек. Стек - это структура данных работающая по принципу LIFO. Именно на стеке идет выполнение нашего кода. И так как js однопоточный язык программирования то для выполнения нашего кода выделяется только один стек.
Принцип работы стека:
- Когда скрипт вызывает функцию, интерпретатор добавляет её в стек вызовов и потом начинает её обработку.
- Любые функции, вызванные этой функцией, добавляются в стек вызовов и выполняются, как только происходит их вызов.
- Когда выполнение основной функции завершено, интерпретатор снимает её со стека вызовов и возобновляет выполнение кода в списке основного кода с той точки, где остановился до этого.
- Если стек занимает больше места, чем ему было присвоено, это приводит к ошибке переполнения стека (“stack overflow” error).
Пример.
const pow = (x, n) => {
if (n === 1) {
return x
} else {
return x * pow(x, n - 1)
}
}
// 2(4) === 2 * 2(3) === 2 * 2 * 2(2) === 2 * 2 * 2 * 2(1)
