Інформатика

Прочитайте!

Рекурсія — це метод програмування, при якому функція викликає саму себе для розв’язання певної задачі. Основна ідея рекурсії полягає в розбитті задачі на менші підзадачі того ж типу.

🔹 Основні компоненти рекурсії:

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

Рекурсивна функція в Python

Функція є рекурсивною, якщо вона містить у своєму тілі виклик самої себе.

Приклад: Обчислення факторіалу числа
Факторіал числа n! визначається як: n!=n×(n−1)!(для n>0), і 0!=1

Реалізація в Python:

Переваги рекурсії:

✔️ Простота коду – зменшує кількість коду в порівнянні з ітеративними підходами.
✔️ Зручність для задач, що природно описуються рекурсивно, наприклад, обхід дерев, пошук у графах, задача Ханойських веж.

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

⚠️ Високе використання пам’яті – кожен рекурсивний виклик створює новий фрейм у стеку викликів.
⚠️ Можливість переповнення стеку (Stack Overflow) – якщо рекурсія не має базового випадку або глибина викликів занадто велика.

Приклад: Числа Фібоначчі

Послідовність Фібоначчі визначається як: F(n)=F(n−1)+F(n−2),деF(0)=0,F(1)=1

Реалізація в Python:

Рекурсія є складним процесом, який вимагає додаткової пам’яті та часу її реалізації. Тому частіше використовується рекурентне обчислення. Однак без рекурсії інколи обійтися досить складно, оскільки без неї алгоритм має заплутану логіку.

Самостійне виконання вправ:

Розробіть програму з рекурсивною функцією обчислення n перших членів геометричної прогресії, перший член якої дорівнює a і знаменник q.