Рекурсия в JavaScript

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

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

Синтаксис

const recurse = () => {
    recurse();
}

recurse();

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

const recurse = () => {
  if (condition) {
    recurse();
  }
  // stop calling recurse()
};

recurse();

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

Примеры

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

const countDown = (start, end) => {
  console.log(start);
  if (start > end) {
    countDown(start - 1, end);
  }
};

countDown(19, 7); // 19 18 17 16

За кулисами

• countDown(19, 7) печатает 19 и вызывает countDown(18, 7)
• countDown(18, 7) печатает 18 и вызывает countDown(17, 7)
• countDown (17, 7) печатает 17 и вызывает countDown(16, 7)
• countDown (16, 7) печатает 16 и останавливает выполнение.

2- Факториал

• 0! = 1
• 1! = 1
• 2! = 2 * 1
• 3! = 3 * 2 * 1
• 4! = 4 * 3 * 2 * 1
• 5! = 5 * 4 * 3 * 2 * 1

const factorial = (num) => (num < 0 ? -1 : num === 0 ? 1 : num * factorial(num - 1));

console.log(factorial(5)); // 120

За кулисами

• факториал(5) = 5 * факториал(4)
• факториал(4) = 4 * факториал(3)
• факториал(3) = 3 * факториал(2)
• факториал(2) = 2 * факториал(1)
• факториал(1) = 1 * факториал(0)
• факториал(0) = 1

3- Фибоначчи

Последовательность Фибоначчи записывается как:
0, 1, 1, 2, 3, 5, 8, 13, 21, …

Последовательность Фибоначчи — это целочисленная последовательность, в которой первые два члена равны 0 и 1. После этого следующий член определяется как сумма двух предыдущих. Следовательно, n-й член равен сумме (n-1)-го члена и (n-2)-го члена.

Вот код, который возвращает значение числа Фибоначчи по заданному индексу с помощью рекурсии

const fibonacci = (n) => (n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2));

console.log(fibonacci(5)); // 5

За кулисами

• fibonacci(5) = fibonacci(4) + fibonacci(3)
• фибоначчи(4) = фибоначчи(3) + фибоначчи(2)
• фибоначчи(3) = фибоначчи(2) + фибоначчи(1)
• фибоначчи(2) = фибоначчи(1) + фибоначчи(0)
• фибоначчи(1) = 1
• фибоначчи(0) = 0