Рекурсія #01

Факторіалом числа n називається добуток чисел від 1 до n:

n! = 1 · 2 · … · (n – 1) · n

Слід запам'ятати, що факторіал нуля дорівнює одиниці:

0! = 1

Наприклад:

1! = 1

2! = 1 · 2 = 2

3! = 1 · 2 · 3 = 6

4! = 1 · 2 · 3 · 4 = 24

Зауважимо, що наприклад

5! = (1 · 2 · 3 · 4) · 5 = 4! · 5

n! = (n – 1)! · n

Розбір коду 

1. Базовий випадок: якщо n == 0, повертаємо 1.

2. Рекурсивний випадок: n * factorial(n - 1), де кожен наступний виклик зменшує n, поки не досягнемо 0.

Як виконується код?

Виклики відкладаються в стек:

factorial(5) = 5 * factorial(4)

factorial(4) = 4 * factorial(3)

factorial(3) = 3 * factorial(2)

factorial(2) = 2 * factorial(1)

factorial(1) = 1 * factorial(0)

factorial(0) = 1  (базовий випадок)

Після досягнення базового випадку значення починають повертатися у зворотному порядку:

factorial(1) = 1 * 1 = 1

factorial(2) = 2 * 1 = 2

factorial(3) = 3 * 2 = 6

factorial(4) = 4 * 6 = 24

factorial(5) = 5 * 24 = 120

Результат: 120

Схематично (робота стеку викликів)

Кожен виклик додається у стек, а після базового випадку значення "розкручуються":

factorial(5)  # чекає

  factorial(4)  # чекає

    factorial(3)  # чекає

      factorial(2)  # чекає

        factorial(1)  # чекає

          factorial(0)  # повертає 1

        factorial(1) = 1 * 1 = 1

      factorial(2) = 2 * 1 = 2

    factorial(3) = 3 * 2 = 6

  factorial(4) = 4 * 6 = 24

factorial(5) = 5 * 24 = 120  # кінцевий результат

Важливі моменти

• Рекурсія працює через стек викликів, і кожен виклик відкладається у пам’яті.

• Базовий випадок зупиняє рекурсію – без нього виникне нескінченний цикл.

• Рекурсія може бути неефективною (наприклад, при обчисленні без оптимізації багаторазово повторюються одні й ті ж виклики - про це далі).