Понимание рекурсии в JavaScript

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

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

Функция, вызывающая саму себя, называется рекурсивной функцией. Пример рекурсивной функции:

function helloWorld() {
  console.log('Hello world')
  helloWorld()
}

Сравнение цикла и рекурсии в JavaScript

Рекурсия — это альтернативный способ записи цикла while.

Цикл while выглядит так:

while (true) {
  console.log('Hello world')
}

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

while (true) {
  console.log('Hello world')
}

В результате в консоли появится множество сообщений Hello world. Кроме того, браузер зависнет, поскольку функция вызывает сама себя слишком быстро и слишком много раз.

Создавая функцию, вызывающую саму себя, фактически создаётся бесконечный цикл while.

// Тот же результат, что и с бесконечным циклом while, приведённым выше.
function helloWorld() {
  console.log('Hello world')
  helloWorld()
}

Правильное использование циклов while

Если необходимо завершить цикл while, нужно изменить условие так, чтобы оно в какой-то момент стало false. Предположим, что цикл нужно выполнить 3 раза. Можно написать следующее:

// Выводит в консоль три сообщения `Hello world`.
let count = 0
while (count < 3) {
  console.log('Hello world')
  count = count + 1
}

Эту же логику можно применить к рекурсивным функциям.

// Цикл выполнится только три раза
let count = 0
function helloWorld() {
  console.log('Hello world')
  count = count + 1
  if (count < 3) {
    helloWorld()
  }
}

Рекурсия без внешних переменных

Нет необходимости заранее объявлять count = 0. Можно передать count в рекурсивную функцию в качестве аргумента.

helloWorld(0)

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

function helloWorld(count) {
  console.log('Hello world')
  count = count + 1
  if (count < 3) {
    helloWorld()
  }
}

Рекурсия без жёсткого кодирования

Мы жёстко прописали три цикла в helloWorld, поскольку использовали число 3. Если нужно позволить пользователю контролировать количество циклов, необходимо использовать число, переданное пользователем.

// В результате должно быть выведено пять раз `Hello world`.
helloWorld(5)

В этом случае аргументом становится количество раз, сколько нужно повторить цикл.

function helloWorld(timesToLoop) {
  // ...
}

После каждого вывода hello world значение timesToLoop необходимо уменьшить на 1.

function helloWorld(timesToLoop) {
  console.log('hello world')
  timesToLoop = timesToLoop - 1
}

Со временем timesToLoop достигнет 0.

• Если оно достигнет 0, то ничего не делаем. Рекурсия заканчивается здесь.
• Но если timesToLoop не равно 0, то необходимо снова запустить helloWorld.

function helloWorld(timesToLoop) {
  console.log('hello world')
  timesToLoop = timesToLoop - 1

  if (timesToLoop === 0) {
    // Ничего не делаем, рекурсия закончилась
  } else {
    helloWorld(timesToLoop)
  }
}

Возвращение значений из рекурсивных функций

Если необходимо вернуть число из рекурсивной функции, каждая ветвь в операторе if должна возвращать значение.

• Хотя бы одна из ветвей должна завершать рекурсию
• Хотя бы одна из ветвей должна вызывать рекурсивную функцию

function recursiveFunction(parameter) {
  if (условие) {
    return значение // Завершение рекурсии
  } else {
    return recursiveFunction(/*...*/) // Продолжение рекурсии
  }
}

Пример: факториал с рекурсией

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

Как работают факториалы. (Примечание: факториалы в математике обозначаются символом !):

• 1!: 1 = 1
• 2!: 1 * 2 = 2
• 3!: 1 * 2 * 3 = 6
• 4!: 1 * 2 * 3 * 4 = 6

Чтобы вычислить факториал числа, пользователь передаёт число в функцию.

factorial(4) // Результат 24

Поскольку нам нужно 4!, имеет смысл инвертировать вычисление (как это было сделано выше с timesToLoop).

• 4!: 4 * 3 * 2 * 1 = 6
• 3!: 3 * 2 * 1 = 6
• 2!: 2 * 1 = 2
• 1!: 1 = 1

В некоторых случаях рекурсия больше не требуется. Такой случай часто называют конечным состоянием. В данном случае условием является n === 1. Когда n === 1, всегда возвращается число 1.

function factorial(num) {
  if (num === 1) {
    return 1
  }
}

Рассмотрим оставшиеся цифры:

• 4!: 4 * 3 * 2 * 1 = 6
• 3!: 3 * 2 * 1 = 6
• 2!: 2 * 1 = 2

Теперь представьте, что мы передали 4 в функцию. Чтобы получить 4!, необходимо умножить 4 на 3!:

• 4!: 4 * 3!
• 3!: 3 * 2!
• 2!: 2 * 1!

Обратите внимание, что мы умножаем num на факториал num - 1? Можно внести это наблюдение в функцию factorial.

function factorial(num) {
  if (num === 1) {
    return 1
  } else {
    return num * factorial(num - 1)
  }
}

Можно немного очистить её с помощью раннего возврата (раннего выхода из функции).

function factorial(num) {
  if (n === 1) return 1
  return num * factorial(num - 1)
}

Рекурсия без конечного состояния

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

// Сниппет с CSS-Tricks
function repeatOften() {
  requestAnimationFrame(repeatOften)
}

requestAnimationFrame(repeatOften)

Chris Coyier создал демонстрацию этого в своей статье о requestAnimationFrame.

See the Pen

Подведение итогов

Рекурсии — это функции, вызывающие сами себя снова и снова. Большинство рекурсий требуют конечного состояния (например, factorial).

Иногда встречаются рекурсии, работающие достаточно медленно, чтобы не требовать конечного состояния (например, requestAnimationFrame).

Когда использовать рекурсию в JavaScript

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

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