Рекурсия JavaScript: изучите основы рекурсии в JavaScript

Что такое рекурсия?

Рекурсия - это метод программирования, который решает сложные проблемы, элегантно упрощая повторяющееся выполнение на более мелкие исполнения аналогичного характера.

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

Но не будем забегать вперед. Для начала давайте сначала определим рекурсию. Рекурсия - это функция, которая вызывает сама себя.

Например, вот псевдокод, показывающий, как работает рекурсия:

function recursion() {
return recursion()
}
recursion()

Обратите внимание, что мы выполняем нашу функцию рекурсии дважды, один раз в рамках нашей функции и снова за пределами глобальной области.

Сначала мы выполняем функцию рекурсии в глобальной области видимости, которая затем запускает сценарий функции рекурсии, который затем вызывает функцию рекурсии из нашей функции рекурсии. Это, в свою очередь, снова запускает функцию, которая снова вызывает рекурсию - непрерывно добавляя рекурсию в наш стек вызовов, тем самым создавая цикл.

При таком исходном коде в стек вызовов добавляется бесконечный цикл вложенных функций.

Стек вызовов - это область, обеспечивающая непрерывную память, которая учитывает локальный контекст и отслеживает несколько функций. Затем цикл событий контролирует стек вызовов и отправляет события или обратные вызовы функций всякий раз, когда стек вызовов пуст.

Если бы мы запустили описанную выше функцию рекурсии в консоли разработчика, мы бы получили следующую ошибку:

Это подводит нас к тому, как мы устанавливаем рекурсивный шаблон в функции.

Предоставляя базовый вариант нашей рекурсивной функции, мы можем регулировать стек вызовов наших вложенных функций. Базовый случай - это наше условие, которое мы можем написать, чтобы переключить наш стек вызовов с рекурсивного запуска на размотку.

Примеры рекурсивных функций JavaScript

Давайте рассмотрим несколько примеров использования рекурсивных функций.

1) Простой пример рекурсивной функции JavaScript

Предположим, вам нужно разработать функцию, которая ведет обратный отсчет от указанного числа до 1. Например, для обратного отсчета от 10 до 1:

3
2
1

Ниже показана countDown() функция:

function countDown(fromNumber) {
    console.log(fromNumber);
}

countDown(3);

Это countDown(3) показывает только цифру 3.

Чтобы отсчитать от числа 3 до 1, вы можете:

  1. показать цифру 3.
  2. и позвоните в countDown(2) тот, который показывает цифру 2.
  3. и позвоните в countDown(1) тот, который показывает цифру 1.

Следующее изменяет countDown() рекурсивную функцию:

function countDown(fromNumber) {
    console.log(fromNumber);
    countDown(fromNumber-1);
}

countDown(3);

Это countDown(3) будет выполняться до тех пор, пока не будет превышен размер стека вызовов, например:

Uncaught RangeError: Maximum call stack size exceeded.

… Потому что у него нет условия перестать называть себя.

Обратный отсчет остановится, когда следующее число будет равно нулю, поэтому мы добавляем условие if следующим образом:

function countDown(fromNumber) {
    console.log(fromNumber);

    let nextNumber = fromNumber - 1;

    if (nextNumber > 0) {
        countDown(nextNumber);
    }
}
countDown(3);

Вывод:

3
2
1

Кажется, countDown() работает как ожидалось.

Однако, как упоминалось в руководстве по типу функции, имя функции является ссылкой на фактический объект функции.

Если где-то в коде для имени функции установлено значение null, рекурсивная функция перестанет работать.

Например, следующий код приведет к ошибке:

let newYearCountDown = countDown;
// somewhere in the code
countDown = null;
// the following function call will cause an error
newYearCountDown(10);

Ошибка:

Uncaught TypeError: countDown is not a function

Как работает скрипт:

  • Сначала присвойте countDown переменной имя функции newYearCountDown.
  • Во-вторых, установите countDown ссылку на функцию на null.
  • В-третьих, вызовите newYearCountDown функцию.

Код вызывает ошибку, потому что тело countDown() функции ссылается на countDown имя функции, которое было установлено null во время вызова функции.

Чтобы исправить это, вы можете использовать именованное выражение функции следующим образом:

let countDown = function f(fromNumber) {
    console.log(fromNumber);

    let nextNumber = fromNumber - 1;

    if (nextNumber > 0) {
        f(nextNumber);
    }
}

let newYearCountDown = countDown;
countDown = null;
newYearCountDown(10);

2) Вычислите сумму цифр примера числа

Для числа, например, 324, вычислите сумму цифр 3 + 2 + 4 = 9.

Чтобы применить рекурсивную технику, вы можете использовать следующие шаги:

f(324) = 4 + f(32)
f(32)  = 2 + f(3)
f(3)   = 3  + 0 (stop here)

Так

f(324) = 4 + f(32) 
f(324) = 4 + 2 + f(3) 
f(324) = 4 + 2 + 3

Следующее иллюстрирует sumOfDigits() рекурсивную функцию:

function sumOfDigits(num) {
    if (num == 0) {
        return 0;
    }
    return num % 10 + sumOfDigits(Math.floor(num / 10));
}

Как это устроено:

  • num%10 возвращает остаток от числа после того, как делится на 10, например: 324 % 10 = 4
  • В Math.floor(num / 10)возвращает целую часть , num / 10 например: Math.floor(324 / 10) = 32
  • Это if(num == 0) условие, которое прекращает вызов функции.

Резюме

  • Рекурсия - это когда функция вызывает сама себя, пока кто-то ее не остановит.
  • У рекурсивной функции всегда есть условие, которое не позволяет функции вызывать саму себя.

Спасибо за прочтение.

Читайте также

Комментарии ()

    Написать комментарий