Рекурсия в 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

За кулисами

- Фибоначчи(5) = Фибоначчи(4) + Фибоначчи(3)
- Фибоначчи(4) = Фибоначчи(3) + Фибоначчи(2)
- Фибоначчи(3) = Фибоначчи(2) + Фибоначчи (1)
- Фибоначчи(2) = Фибоначчи(1) + Фибоначчи(0)
- Фибоначчи(1) = 1
- Фибоначчи(0) = 0