Что такое рекурсия в JS (JavaScript)

Рекурсия в JS (JavaScript)

31.01.2024
259
11 мин.
0
Содержание скрыть
  1. 1 Что такое рекурсивная функция?
  2. 2 Три части рекурсивной функции
    1. 2.1 Как определить рекурсивную функцию
    2. 2.2 Что такое базовое условие?
    3. 2.3 Зачем нужно базовое условие?
  3. 3 Рекурсия в JS: пример функции
  4. 4 Рекурсивный вызов
  5. 5 Рекурсия в JS против циклов
  6. 6 Рекурсия или циклы: что выбрать?
    1. 6.1 Как найти факториал с помощью цикла
    2. 6.2 Как найти факториал с помощью рекурсии
  7. 7 Хвостовая рекурсия в JS
  8. 8 Прочие практические примеры
    1. 8.1 Последовательность Фибоначчи
    2. 8.2 Получение суммы n натуральных чисел
    3. 8.3 Работа со строкой
    4. 8.4 Рекурсия в JS: нахождение экспоненты из чисел
    5. 8.5 Рекурсия массива в JS
    6. 8.6 Рекурсия объекта в JS

Функция, которая вызывает саму себя вновь и вновь, носит название рекурсии. Этот процесс длится до тех пор, пока не прекратится. В общей сложности, в этой статье мы рассмотрим простыми словами, как применяется рекурсия в JS (JavaScript).

Что такое рекурсивная функция?

Ниже приведён базовый пример рекурсивной функции:

function recursiveFunc() {
  // Здесь указываются выполняемые действия в функции
  recursiveFunc()
}

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

Три части рекурсивной функции

При каждом написании рекурсивной функции должны присутствовать три элемента:

  1. Определение функции.
  2. Базовое условие.
  3. Рекурсивный вызов.

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

Как определить рекурсивную функцию

В частности, определение рекурсивной функции происходит так же, как и обычной функции в JavaScript. Например:

function recursiveFunc() {
  // Здесь указываются выполняемые действия в функции.
}

Так или иначе рекурсивные функции отличаются от обычных в JavaScript наличием базового условия и рекурсивного вызова.

Что такое базовое условие?

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

function recursiveFunc() {
  if(base condition) {
    // Прекращение выполнение функции при соблюдении условия
  }
  // В ином случае рекурсия продолжается
  recurse();
}

Зачем нужно базовое условие?

Без него вы столкнётесь с бесконечной рекурсией. В этой ситуации функция будет продолжать свой собственный вызов без остановки, например:

function doSomething(action) {
  console.log(`I am ${action}.`)
  doSomething(action)
}

doSomething('running')

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

Uncaught RangeError: Maximum call stack size exceeded.

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

Рекурсия в JS: пример функции

Давайте рассмотрим простой пример:

function doSomething(n) {
  if(n === 0) {
    console.log("TASK COMPLETED!")
    return
  }
  console.log("I'm doing something.")
  doSomething(n - 1)
}
doSomething(3)

При передачи числа 3 в функцию doSomething в консоль выведется следующий результат:

TASK COMPLETED!.

Базовым условием для функции doSomething является n === 0 . Всякий раз, когда вызывается функция, она сначала проверяет, выполнено ли оно. Если да, она выведет сообщение «TASK COMPLETED!». В противном случае будет продолжаться выполнение остальной части кода в функции. В этом случае она напечатает «I’m doing something.», а затем вызовет саму себя снова.

Рекурсивный вызов

Рекурсивный вызов — это то, что обрабатывает функция, вызывающая себя вновь и вновь. В функции doSomething — это строка ниже:

doSomething(n-1)

Стоит отметить, что происходит, когда функция вызывает саму себя. В неё передаётся новый параметр n — 1. На каждой итерации рекурсивного вызова параметр будет отличаться от параметра предыдущего вызова.

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

Рекурсия в JS против циклов

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

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

Что такое рекурсия в JS (JavaScript)
Для чего можно использовать рекурсию в JS (JavaScript) на практике (изображение создано с помощью ИИ)

Рекурсия или циклы: что выбрать?

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

Как найти факториал с помощью цикла

Чтобы найти факториал с помощью цикла, сначала инициализируется переменная factorial со значением 1. Затем запускается цикл с заданным числом num. Цикл будет продолжаться пока i > 0.

Для каждой итерации текущее значение factorial умножается на i. Значение i при этом уменьшается на 1, пока i оно является больше нуля. После завершения цикла происходит возврат значения факториала.

function findFactorial(num) {
  let factorial = 1
  for (let i = num; i > 0; i--) {
    factorial *= i
  }
  return factorial
}

findFactorial(5) // 120

Как найти факториал с помощью рекурсии

Аналогичное решение доступно и с помощью рекурсивной функции. Например:

function findFactorial(num) {
  if (num === 0) return 1
  let factorial = num * findFactorial(num - 1)
  return factorial;
}

findFactorial(5) // 120

Во-первых, нужно указать базовое условие num === 0. Во-вторых, потребуется рекурсивный вызов findFactorial(num — 1) чтобы гарантировать, что число продолжит уменьшаться при каждом вызове и передачи нового параметра n-1. Затем результат умножается на предыдущее число num * findFactorial(num — 1), пока не будет выполнено базовое условие.

Хвостовая рекурсия в JS

Хвостовая рекурсия — это тип рекурсивной функции, когда последним выполняется рекурсивный вызов. Это упрощённая, более оптимизированная рекурсия.

factorial(5); // шаг 1
5 * factorial(4); // шаг 2
5 * 4 * factorial(3); // шаг 3
5 * 4 * 3 * factorial(2); // шаг 4
5 * 4 * 3 * 2 * factorial(1); // шаг 5
5 * 4 * 3 * 2 * 1; // шаг 6

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

See the Pen
Untitled by Вячелав Демченко (@upsdjzqs-the-reactor)
on CodePen.

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

Прочие практические примеры

Рассмотрим ещё несколько примеров использования рекурсии в js на практике.

Последовательность Фибоначчи

Последовательность Фибоначчи до n-го члена с использованием рекурсии. Каждое число является суммой двух предыдущих чисел в серии чисел. 0, 1, 1, 2, 3, 5, 8, 13, 21, …

function fibonacci(num) {
    if(num < 2) {
        return num;
    }
    else {
        return fibonacci(num-1) + fibonacci(num - 2);
    }
}

// take nth term input from the user
const nTerms = prompt('Enter the number of terms: ');

if(nTerms <=0) {
    console.log('Enter a positive integer.');
}
else {
    for(let i = 0; i < nTerms; i++) {
        console.log(fibonacci(i));
    }
}

Результат:

Enter the number of terms: 5
0
1
1
2
3

Объяснение:

Пользователь должен ввести количество слагаемых, до которых он хочет вывести последовательность Фибоначчи. В этом примере это число равно 5. Условие if-else используется для проверки, является ли входное число больше 0. Каждый член вычисляется рекурсивно с использованием цикла for, в котором снова используется функция fibonacci().

Получение суммы n натуральных чисел

Найдём сумму натуральных чисел:

function sum(num) {
    if(num > 0) {
        return num + sum(num - 1);
    }
    else {
        return num;
    }
 }

// take input from the user
const number = parseInt(prompt('Введите положительное целое число: '));

const result = sum(number);

// display the result
console.log(`The sum is ${result}`);

Вывод:

Введите положительное целое число: 100
Сумма натуральных чисел: 5050

Объяснение:

Если входное число строго равно больше 0, рекурсивная функция вызывает себя снова, уменьшая его значение на 1. Процесс повторяется до тех пор, пока число не станет равным 1. С С другой стороны, код прекращает работу, когда значение становится 0. Если пользователь вводит отрицательное число, возвращается это отрицательное значение, и процесс вычисления останавливается.

Работа со строкой

function stringRev(text) {
    if (text.length == 1) {        // основное условие
        return text;
    }
    else {
        return text.slice(-1) + stringRev(text.slice(0, -1));
    }
}
//slice() возвращает часть строки с заданными начальной и конечной позициями
// удаление последнего символа
console.log(stringRev('Recursion'));

Вывод:

noisruceR

Объяснение:

В базовом случае проверяется, равна ли длина строки 1. Это приводит к возврату той же строка. В противном случае выполняется рекурсивный вызов и в строке удаляется последний символ.

Рекурсия в JS: нахождение экспоненты из чисел

function exponential(num, power){
    //base case
    if (power == 1){
        return num;
    }
    else {
        return num * exponential(num, power - 1);
    }
}
console.log(exponential(4, 2));

Вывод:

16

Объяснение:

В базовом случае, если в любой момент степень становится равной 1, программа выведет число, возведённое в заданную степень. В противном случае она снова вызывает себя с меньшей степенью в качестве аргумента.

Рекурсия массива в JS

Мы можем создать рекурсивную функцию для обработки массива на Javascript. По сути, функция processArrayRecursively принимает массив и индекс (по умолчанию равный 0) и рекурсивно обрабатывает элементы массива. В данном примере она просто выводит элементы массива в консоль.

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

function processArrayRecursively(array, index = 0) {
  // Базовый случай: если индекс выходит за пределы массива, завершаем рекурсию
  if (index >= array.length) {
    return;
  }

  // Ваш код для обработки элемента массива
  console.log(array[index]);

  // Рекурсивный вызов для следующего элемента массива
  processArrayRecursively(array, index + 1);
}

// Запуск рекурсивной функции с массивом arr
processArrayRecursively(arr);

Читайте также: CSS :has() — полное руководство по псевдоселектору.

Рекурсия объекта в JS

Чтобы рекурсивно обработать элементы объекта можно использовать следующий код. Функция processObjectRecursively рекурсивно обходит все ключи объекта и выводит их значения в консоль.

const obj = { key1: 1, key2: 2, key3: 3, key4: 4, key5: 5, key6: 6, key7: 7, key8: 8, key9: 9, key10: 10 };

function processObjectRecursively(obj) {
  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      // Ваш код для обработки значения по ключу
      console.log(obj[key]);

      // Если значение по ключу является объектом, рекурсивно вызываем функцию
      if (typeof obj[key] === 'object' && obj[key] !== null) {
        processObjectRecursively(obj[key]);
      }
    }
  }
}

// Запуск рекурсивной функции с объектом obj
processObjectRecursively(obj);

Вас также может заинтересовать