Часть первая: простое введение

Первый пример рекурсии, с которым сталкивается большинство начинающих разработчиков, — это рекурсивный алгоритм Фибоначчи. В качестве введения в рекурсию алгоритм излишне сложен. В этой быстрой статье мы, напротив, получим представление о рекурсии, рассмотрев простые примеры, а затем пройдем путь к каноническому алгоритму Фибоначчи во второй части.

Основы: почему рекурсия работает в первую очередь

Внутренний список задач 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 в стеке вызовов. Начните с передачи различных начальных значений для аргумента «повторить».

Во второй части мы рассмотрим канонический алгоритм Фибоначчи. Перед этим вы, возможно, захотите прочитать немного больше о поведении стека вызовов последним пришел, первым обслужен здесь.