10_24

Поняття рекурсії. Рекурентні послідовності

🔹 Поняття рекурсії

Рекурсія — це спосіб визначення функції (або алгоритму), коли вона викликає сама себе.
Для роботи рекурсії обов’язково потрібно:

1. Базовий випадок (умова виходу) — коли виклик припиняється.

2. Рекурсивний випадок — коли функція викликає сама себе для розв’язання підзадачі.

📘 Приклад 1. Обчислення факторіалу числа n!

def factorial(n):
    if n == 0 or n == 1:   # базовий випадок
        return 1
    else:
        return n * factorial(n - 1)  # рекурсивний виклик

print(factorial(5))  # 120

Пояснення:
Функція викликає сама себе, поки не дійде до 1.

---

🔹 Рекурентні послідовності

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

📘 Приклад 2. Послідовність Фібоначчі
(0, 1, 1, 2, 3, 5, 8, 13, …)

Рекурентне визначення:

$$F(0) = 0,\quad F(1) = 1,\quad F(n) = F(n-1) + F(n-2)$$

Рекурсивна реалізація:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

for i in range(10):
    print(fib(i), end=" ")

---

🔹 Недоліки рекурсії

• Велика кількість викликів → сповільнення роботи.

• Може призвести до переповнення стеку (Stack Overflow).
  ✅ Тому для великих задач краще використовувати ітераційні алгоритми.

---

4. Закріплення знань (10 хв)

Завдання 1.
Напишіть рекурсивну функцію для обчислення суми чисел від 1 до n.

Приклад: sum(5) = 1 + 2 + 3 + 4 + 5 = 15

def sum_n(n):
    if n == 1:
        return 1
    else:
        return n + sum_n(n - 1)

print(sum_n(5))

Завдання 2.
Напишіть рекурсивну функцію, яка обчислює n-й член послідовності:

$$a_1 = 2, \quad a_n = a_{n-1} + 3$$

Очікуваний результат:
a(1)=2, a(2)=5, a(3)=8, a(4)=11, ...