Рекурсивные функции JavaScript — как использовать

В этом руководстве вы узнаете, как использовать технику рекурсии для разработки рекурсивной функции JavaScript, которая представляет собой функцию, которая вызывает сама себя.

Рекурсивная функция — это функция, которая вызывает сама себя до тех пор, пока не прекратится. И этот метод называется рекурсией.

Предположим, у вас есть функция recurse(). Функция recurse() является рекурсивной, если она вызывает себя внутри своего тела, например:

function recurse() { // ... recurse();
 // ... }

Рекурсивная функция всегда имеет условие прекращения вызова самой себя. В противном случае он будет вызывать себя бесконечно. Таким образом, рекурсивная функция обычно выглядит следующим образом:

function recurse() { if(condition) { // stop calling itself //... } else { recurse();
  } }

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

Примеры

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

1) Простой пример

Предположим, вам нужно разработать функцию, которая ведет обратный отсчет от заданного числа до 1. Например, для обратного отсчета от 3 до 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 & gt; 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 & gt; 0) {
        f(nextNumber);
    }
}
let newYearCountDown = countDown;
countDown = null;
newYearCountDown(10);

2) Пример вычисления суммы n натуральных чисел

Предположим, вам нужно вычислить сумму натуральных чисел от 1 до n с помощью метода рекурсии. Для этого вам нужно определить sum() рекурсивно следующим образом:

sum(n) = n + sum(n-1) 
sum(n-1) = n - 1 + sum(n-2) 
... 
sum(1) = 1

Ниже показана рекурсивная функция sum() :

function sum(n) {
    if (n & lt; = 1) {
        return n;
    }
    return n + sum(n - 1);
}

Заключение

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