В этой статье я затрону несколько важных идей, которые помогут вам понять рекурсию в JavaScript. Я не собираюсь давать здесь полное определение, но вы можете взглянуть на определение из Википедии.
Давайте договоримся для целей этой статьи, что мы пытаемся решить проблему с помощью функции, которая затем будет вызывать саму себя.
Задача
В конце раздела Javascript Algorithms and Data Structures – Basic Javascript на freeCodeCamp вы столкнулись с интересной задачей: “Use Recursion to Create a Range of Numbers”, где инструкции следующие:
Мы определили функцию rangeOfNumbers с двумя параметрами. Функция должна возвращать массив целых чисел, который начинается с числа, представленного параметром startNum, и заканчивается числом, представленным параметром endNum. Начальное число всегда будет меньше или равно конечному числу. Ваша функция должна использовать рекурсию, вызывая саму себя, и не использовать циклы любого вида. Она также должна работать в случаях, когда и startNum, и endNum одинаковы.
Звучит достаточно просто – если вы выполните rangeOfNumbers(1, 5), она должна вернуть [1, 2, 3, 4, 5].
Если вы похожи на меня, вы можете интуитивно догадаться об этом, основываясь на предыдущем примере в этом разделе. Но все еще может быть немного непонятно, как все это работает.
Спойлер: ответ вы найдете сразу же ниже. Но это не слишком большой спойлер, поскольку ответ достаточно легко найти в интернете.
Мое решение
Вполне вероятно, что вы можете прочитать код и понять, что когда он переходит к базовому варианту, он возвращает в массив все, что является startNum. Затем он будет продолжать выталкивать другие значения в этот массив, пока не закончит все свои рекурсивные вызовы.
function rangeOfNumbers(startNum, endNum) {
if (startNum === endNum) {
return [startNum];
} else {
const numbers = rangeOfNumbers(startNum, endNum - 1);
numbers.push(endNum);
return numbers;
}
}Что мне показалось сложным, так это понять, как именно работает стек вызовов и как возвращаются мои значения.
Итак, давайте разберемся, как эта функция будет возвращать свое конечное значение.
Стек вызовов
Прежде всего, необходимо понять, как работает стек вызовов. Я отсылаю вас к объяснению Mozilla Developer Network:
Когда скрипт вызывает функцию, интерпретатор добавляет ее в стек вызовов, а затем начинает выполнять функцию.
Любые функции, вызываемые этой функцией, добавляются в стек вызовов дальше и выполняются там, где достигается их вызов.
Когда текущая функция завершается, интерпретатор убирает ее из стека и возобновляет выполнение с того места, где он остановился в последнем листинге кода.
Используя это объяснение, давайте выполним приведенный выше код, используя rangeOfNumbers(1,5).
Сначала создается rangeOfNumbers – Execution Context и выполняется со следующими значениями:
Итак, мы добавили в наш стек неразрешенный вызов функции rangeOfNumbers(1,5). Затем мы переходим к созданию выполнения для rangeOfNumbers(1,4), и так далее, добавляя каждый из этих вызовов в наш стек, пока мы, наконец, не разрешим вызов функции. Тогда интерпретатор уберет эту функцию из стека и перейдет к следующей.
Изучение нашего стека вызовов
В итоге наш стек будет выглядеть следующим образом:
rangeOfNumbers(1,1) rangeOfNumbers(1,2) rangeOfNumbers(1,3) rangeOfNumbers(1,4) rangeOfNumbers(1,5)
rangeOfNumbers(1,1) будет последней в нашем стеке, потому что, наконец, этот вызов ВОЗВРАЩАЕТ значение, позволяющее нам перейти к следующей функции в стеке.
Возвращаемое значение rangeOfNumbers(1,1) – [1], как мы и предполагали, поскольку это наш базовый случай. Теперь мы убираем rangeOfNumbers(1,1) из нашего стека и возвращаемся к тому месту, где остановилась rangeOfNumbers(1,2)…
var numbers = rangeOfNumbers(1,2) // returns an array of [1]
Numbers больше не является неопределенным, и следующим шагом будет вставка endNum, который равен 2, в массив numbers. Это дает нам [1,2] в массиве Numbers, и теперь мы возвращаем значение.
numbers.push(endNum) //numbers now holds an array of [1,2] return numbers; // ends our function and returns [1,2]
Разбираем сложную часть
Итак, мы закончили вызов rangeOfNumbers(1,2), который имел возвращаемое значение [1,2]. Давайте продолжим со следующего вызова в нашем стеке rangeOfNumbers(1,3). Numbers в настоящее время [1,2], потому что это возвращаемое значение rangeOfNumbers(1,2). Это то, что мы подключили при вызове rangeOfNumbers(1,3), потому что, опять же, 3 вычитается из 1, то есть rangeOfNumbers(1,2), который, как мы сказали, возвращает [1,2].
Понятно? Отлично! Если вы не поняли, перечитайте этот параграф, потому что это самая сложная часть для понимания.
Если вы в курсе, давайте продолжим. Если вы прочли эту часть, то все остальное будет довольно легко.
Вернемся к rangeOfNumbers(1,3): массив чисел сейчас [1,2], поэтому мы выталкиваем endNum, который равен 3. Теперь у нас есть [1,2,3], и мы снова возвращаем это значение. Мы удаляем rangeOfNumbers(1,3) из нашего стека, который вернул значение [1,2,3].
Как мы получили rangeOfNumbers(1,3)? Правильно, когда мы вызвали rangeOfNumbers(1,4) и endNumb -1, то есть → 3, и мы знаем, что rangeOfNumbers(1,3) дает нам возвращаемое значение [1,2,3], которое как раз и есть в нашем массиве.
Теперь мы вставляем конечное число (endNum) (также известное как 4) в массив numbers, что дает нам [1,2,3,4], и возвращаем это значение. Давайте снова удалим этот вызов функции из стека, поскольку он дал нам то, что мы хотели.
Собираем все вместе
Теперь перейдем к вызову, с которого все началось: rangeOfNumbers(1,5). Первое, что мы делаем, это определяем, какое значение у нас есть в числах. При вводе rangeOfNumbers(1,4) мы получаем, как мы уже говорили, [1,2,3,4]. Теперь мы можем вставить в массив наше конечное число 5 и получить [1,2,3,4,5], которое мы вернем, и наш стек теперь пуст после последнего вызова.
Итак, давайте быстро рассмотрим, что и в каком порядке возвращало какое значение.
rangeOfNumbers(1,1) → returns [1] rangeOfNumbers(1,2) → returns [1,2] rangeOfNumbers(1,3) → returns [1,2,3] rangeOfNumbers(1,4) → returns [1,2,3,4] rangeOfNumbers(1,5) → returns [1,2,3,4,5]
Если это все еще непонятно, во-первых, я понимаю – это запутанная тема. Далее я бы рекомендовал ввести ваш код в этот замечательный инструмент: http://www.pythontutor.com/javascript.html.
Все это может работать, потому что мы начали с небольшого базового случая и, по сути, построили свой путь назад. Каждый раз наше возвращаемое значение немного больше, чем при предыдущем вызове, точно так же, как если бы вы выполняли эту же операцию с помощью цикла for.
Оригинал: “https://www.freecodecamp.org/news/learn-recursion-in-javascript-by-example/”