Що таке рекурсія

Рекурсією називають процес, коли функція викликає сама себе. Тобто, оголошується функцію і в її тілі відбувається звернення до неї (вона викликається). Важливою в рекурсії є гранична умова, при виконанні якої функція припинить викликатись і поверне якесь значення. Без цієї умови виникне помилка про переповнення стека викликів:

Uncaught RangeError: Maximum call stack size exceeded

На співбесідах дуже люблять ставити питання про рекурсію або запропонувати вирішити завдання використовуючи її, оскільки це один із базових принципів у програмуванні. Якщо ви Junior Front-End розробник, то дуже висока ймовірність, що на співбесіді спитають щось на цю тему, тому корисно знати, що таке рекурсія.

Приклад рекурсії

Класичний приклад рекурсії — це, звичайно, факторіал, його наводять у всіх книжках з програмування, де згадується рекурсія.

Про всяк випадок згадаємо, що це таке. У математиці факторіал числа n дорівнює добутку всіх позитивних чисел менших або рівних йому, і позначається як n! Формулою можна виразити так:

n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1

Наприклад, факторіал числа 4! = 1 * 2 * 3 * 4 = 24, а для 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720. Факторіал нуля дорівнює одиниці: 0! = 1.

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

function factorial(n) {
  let result = 1;

  for (let i = n; i > 0; i--) {
    result *= i;
  }

  return result;
}

Все досить просто, ініціалізуємо змінну та в циклі все перемножуємо. Але, можна ще простіше та коротше. Цикл йде у зворотному порядку, щоб наблизити його сенс до наступного прикладу.

Давайте тепер розв’яжемо завдання за допомогою рекурсії. Математично рекурсію можна виразити такою формулою:

n! = n * (n - 1)!

або

n! = n * (n - 1) * (n - 2)!

або

n! = n * (n - 1) * (n - 2) * (n - 3)!

І так далі, поки не дійдемо до нуля.

Тепер теж саме, але за допомогою JavaScript.

function factorial(n) {
  if (n === 0) {
    return 1;
  }

  return n * factorial(n - 1);
}

Як бачите цей приклад ще коротший і виглядає простіше. Спочатку описана гранична умова, коли n дорівнює нулю і який результат при цьому має бути. Нагадаю, що без цієї умови виникне помилка.

Рекурсивний виклик цієї функції для конкретного прикладу можна зобразити так:

factorial(4) = 4 * factorial(3);
factorial(4) = 4 * (3 * factorial(2));
factorial(4) = 4 * (3 * (2 * factorial(1)));
factorial(4) = 4 * (3 * (2 * (1 * factorial(0))));
factorial(4) = 4 * (3 * (2 * (1 * 1))));

factorial(0) = 1, тому що ми маємо граничну умову, при n = 0 ми повертаємо 1.

На цьому, про рекурсію в JavaScript, все. Сподіваюся, зміг допомогти веб-розробнику-початківцю зрозуміти, що таке рекурсія.





Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься.