Часть первая: простое введение
Первый пример рекурсии, с которым сталкивается большинство начинающих разработчиков, — это рекурсивный алгоритм Фибоначчи. В качестве введения в рекурсию алгоритм излишне сложен. В этой быстрой статье мы, напротив, получим представление о рекурсии, рассмотрев простые примеры, а затем пройдем путь к каноническому алгоритму Фибоначчи во второй части.
Основы: почему рекурсия работает в первую очередь
Внутренний список задач JavaScript называется стеком вызовов. Каждый элемент в стеке вызовов является вызовом функции. Порядок, в котором функции добавляются и удаляются из стека вызовов, делает возможной рекурсию.
Давайте посмотрим на порядок событий стека вызовов для этого файла JavaScript:
//callHelloWorld.js function helloWorld() { console.log("Hello World"); } function callHelloWorld(){ helloWorld(); console.log("Wrapping up") }; callHelloWorld();
Вот порядок стека вызовов:
callHelloWorld
добавляется в стек вызовов- Функция
callhelloWorld
начинает выполнение helloWorld
добавляется в стек вызовов- выполнение перемещено в тело функции
helloWorld
- «Hello World» регистрируется в консоли
helloWorld
удаляется из стека вызовов- выполнение возвращается туда, где оно было остановлено в теле функции
callHelloWorld
- «Подведение итогов» регистрируется в консоли
callHelloWorld
удаляется из стека вызовов
Порядок, который мы здесь видим, называется «последний пришел, первый вышел» или LIFO. Это означает, что последняя функция, добавленная в стек вызовов, будет первой удаленной функцией. Другими словами, если стек вызовов включает в себя несколько функций, последняя добавляемая функция — это место, где начинается выполнение, а затем JavaScript переходит к исходной функции.
Великолепно!
Рекурсия и стек вызовов
Рекурсивная функция — это функция, которая вызывает сама себя из собственного тела функции. Это означает, что рекурсивная функция будет многократно добавлять свои экземпляры в стек вызовов. Рассмотрим порядок стека вызовов этой функции:
//repeatDesire.js function repeatDesire(){ console.log("I want to go to Red Lobster.") repeatDesire() }
repeatDesire
добавляется в стек вызовов- «Я хочу пойти в Red Lobster». зарегистрирован в консоли
- в стек вызовов добавляется новый экземпляр
repeatDesire
- «Я хочу пойти в Red Lobster». зарегистрирован в консоли
- в стек вызовов добавляется новый экземпляр
repeatDesire
- …и так далее и тому подобное, пока размер стека вызовов не достигнет предела памяти
Поскольку JavaScript выполняется так быстро, стек вызовов мгновенно достигает своего предела памяти, что мы называем «переполнением стека» (да, как в случае с переполнением стека). Рекурсия полезна, но переполнение - нет. Чтобы сохранить первое и удалить второе, нам нужен так называемый «базовый случай» — способ сообщить рекурсивной функции, чтобы она прекратила вызывать себя.
Чтобы понять это на практическом уровне, мы создадим новую функцию с именем dynamicRepeatDesire
, которая успешно включает базовый случай.
О чудо: dynamicRepeatDesire
function dynamicRepeatDesire(repeat) { if (repeat === 0) { console.log("I'm done here...") } else { console.log("I want to wrap up this article") dynamicRepeatDesire(repeat - 1) } } dynamicRepeat(2) //Console Output "I want to wrap up this article" "I want to wrap up this article" "I'm done here..."
Новая функция dynamicRepeatDesire
принимает аргумент «повторить», указывающий, сколько раз сообщение «Я хочу завершить эту статью» выводится на консоль. Кроме того, тело функции dynamicRepeatDesire
включает условное выражение, которое проверяет значение «repeat», чтобы определить, следует ли выводить на консоль сообщение «Я здесь закончил…» или следует вызывать dynamicRepeatDesire
еще раз. И, наконец, если dynamicRepeatDesire
is вызывается еще раз, ему передается новое значение в качестве аргумента «повторить» — результат вычитания единицы из текущего значения.
dynamicRepeatDesire
избегает переполнения стека, комбинируя два элемента: 1) начиная тело функции с условной проверки, чтобы определить, удовлетворяет ли аргумент «повторение» нашему базовому случаю (когда «повторение» равно нулю), и 2) если нет, рекурсивно вызывая себя с новым значением аргумента «повторить», равным текущему значению минус один. Другими словами, с каждым новым экземпляром dynamicRepeatDesire
в стеке вызовов значение «repeat» становится на единицу меньше, чем в предыдущем экземпляре.
Точно так же мы гарантируем, что наша функция всегда попадет в базовый случай и избежит переполнения стека. Если непонятно, как это работает, попробуйте проследить значение «repeat» через каждый экземпляр dynamicRepeatDesire
в стеке вызовов. Начните с передачи различных начальных значений для аргумента «повторить».
Во второй части мы рассмотрим канонический алгоритм Фибоначчи. Перед этим вы, возможно, захотите прочитать немного больше о поведении стека вызовов последним пришел, первым обслужен здесь.