Рекурсивна функція викликає себе для вирішення меншої версії тієї самої задачі. Кожна рекурсивна функція потребує двох речей: **базового випадку**, що зупиняє рекурсію, та **рекурсивного випадку**, що наближається до базового.
```python
def factorial(n):
if n == 0: # базовий випадок: зупинитися тут
return 1
return n * factorial(n - 1) # рекурсивний випадок: менша задача
factorial(4) # 24
```
**Що відбувається при кожному виклику — стек викликів**
Коли Python викликає функцію, він поміщає фрейм на стек викликів. Кожен фрейм зберігає локальні змінні та адресу повернення. З `factorial(4)` стек зростає так:
```
factorial(4) -> викликає factorial(3) чекає...
factorial(3) -> викликає factorial(2) чекає...
factorial(2) -> викликає factorial(1) чекає...
factorial(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
```
Стек *розкручується* після досягнення базового випадку — кожен виклик, що чекав, отримує відповідь і обчислює власне значення.
**Найпоширеніша помилка: забути базовий випадок**
Без базового випадку рекурсія ніколи не зупиняється — Python генерує `RecursionError`:
```python
def bad_factorial(n):
return n * bad_factorial(n - 1) # немає базового випадку!
bad_factorial(3) # RecursionError: maximum recursion depth exceeded
```
**Інша поширена помилка: не наближатися до базового випадку**
```python
def also_bad(n):
if n == 0:
return 0
return also_bad(n + 1) # іде від 0, а не до нього!
```
Завжди перевіряй: чи робить кожен рекурсивний виклик задачу *строго меншою*?
**Простий приклад: сума списку**
```python
def total(lst):
if not lst: # базовий випадок: порожній список
return 0
return lst[0] + total(lst[1:]) # перший елемент + сума решти
total([1, 2, 3, 4]) # 10
```
Це менш ефективно, ніж `sum(lst)`, але чітко показує рекурсивний патерн: відокреми один елемент, виклич рекурсивно для решти, об'єднай.
Коли рекурсія — правильний інструмент: дерева, «розділяй і володарюй»
Рекурсія блискуче підходить, коли задача має природно рекурсивну структуру: дерева, вкладені дані, алгоритми «розділяй і володарюй».
**Бінарний пошук** (розділяй і володарюй)
```python
def binary_search(lst, target, lo=0, hi=None):
if hi is None:
hi = len(lst) - 1
if lo > hi: # базовий випадок: не знайдено
return -1
mid = (lo + hi) // 2
if lst[mid] == target:
return mid
if lst[mid] < target:
return binary_search(lst, target, mid + 1, hi) # шукаємо у правій половині
return binary_search(lst, target, lo, mid - 1) # шукаємо у лівій половині
binary_search([1, 3, 5, 7, 9], 7) # 3
```
**Обхід дерева** (природно рекурсивна структура)
```python
def tree_sum(node):
if node is None: # базовий випадок: порожній вузол
return 0
return node['value'] + tree_sum(node.get('left')) + tree_sum(node.get('right'))
tree = {'value': 1, 'left': {'value': 2, 'left': None, 'right': None},
'right': {'value': 3, 'left': None, 'right': None}}
tree_sum(tree) # 6
```
**Вирівнювання вкладених списків**
```python
def flatten(lst):
result = []
for item in lst:
if isinstance(item, list):
result.extend(flatten(item)) # рекурсія у вкладений список
else:
result.append(item)
return result
flatten([1, [2, [3, 4]], 5]) # [1, 2, 3, 4, 5]
```
**Хвостова рекурсія — Python її не оптимізує**
У деяких мовах (Scheme, Erlang) рекурсивний виклик, що є *останньою* операцією у функції (хвостовий виклик), оптимізується компілятором для повторного використання фрейму стеку. Python навмисно цього НЕ робить (Гвідо ван Россум: це зробило б трасування нечитабельними). Хвостово-рекурсивна функція в Python все одно створює O(n) фреймів стеку:
```python
def factorial_tail(n, acc=1):
if n == 0:
return acc
return factorial_tail(n - 1, acc * n) # хвостовий виклик - але НЕ оптимізується
```
Якщо потрібна дуже глибока рекурсія (тисячі викликів), замість неї використовуй ітерацію.
Рекурсія vs ітерація, lru_cache, та перетворення у стек
**Рекурсія vs ітерація — коли перемикатися**
Рекурсія елегантна для природно ієрархічних задач. Ітерація часто краща, коли глибина рекурсії може бути великою, або структура лінійна (зв'язний список, плоска послідовність).
```python
# Рекурсивно - зрозуміло, але O(n) фреймів стеку
def sum_recursive(n):
if n == 0: return 0
return n + sum_recursive(n - 1)
# Ітеративно - той самий результат, O(1) місця у стеку
def sum_iterative(n):
total = 0
while n > 0:
total += n
n -= 1
return total
```
Ліміт рекурсії Python за замовчуванням — 1000. Можна підняти через `sys.setrecursionlimit(n)`, але це тимчасовий захід — велика глибина рекурсії зазвичай означає, що варто перейти на ітерацію.
**`functools.lru_cache` — мемоїзація дорогих рекурсивних викликів**
Без кешування наївний Фібоначчі повторно обчислює одні й ті самі підзадачі по-експоненційному:
```python
def fib(n):
if n <= 1: return n
return fib(n - 1) + fib(n - 2) # O(2^n) викликів
fib(35) # займає ~2 секунди
```
Додай `@lru_cache` і кожна підзадача вирішується один раз:
```python
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1: return n
return fib(n - 1) + fib(n - 2) # тепер O(n) викликів
fib(35) # миттєво
fib.cache_info() # CacheInfo(hits=..., misses=36, ...)
```
**Перетворення рекурсії на ітерацію з явним стеком**
Будь-яку рекурсію можна перетворити на ітерацію, підтримуючи власний стек (список). Це повністю уникає ліміту рекурсії Python:
```python
def flatten_iterative(lst):
result = []
stack = [lst]
while stack:
current = stack.pop()
for item in reversed(current):
if isinstance(item, list):
stack.append(item) # помістити вкладений список для обробки пізніше
else:
result.append(item)
return result
flatten_iterative([1, [2, [3, 4]], 5]) # [1, 2, 3, 4, 5]
```
**Практичне правило**: використовуй рекурсію, коли глибина обмежена і мала (наприклад, висота дерева < 100), і `lru_cache`, коли підзадачі перетинаються. Переходь на ітерацію (з явним стеком), коли глибина необмежена або критична продуктивність.
def flatten(data):
result = []
for item in data:
if isinstance(item, list):
result.extend(flatten(item))
else:
result.append(item)
return result
print(flatten([1, [2, [3, [4]], 5], 6]))
Напишіть рекурсивну функцію, яка виконує двійковий пошук у відсортованому списку. Повертайте індекс цільового елемента, якщо знайдено, або -1, якщо ні.
Напишіть рекурсивну функцію, яка виводить кроки розв'язання головоломки Ханойських веж для n дисків. Перемістіть усі диски зі стержня A на стержень C, використовуючи стержень B як допоміжний. Виводьте кожен хід як 'Move disk from X to Y'.
def hanoi(n, source, target, auxiliary):
if n == 1:
print(f"Move disk from {source} to {target}")
return
hanoi(n - 1, source, auxiliary, target)
print(f"Move disk from {source} to {target}")
hanoi(n - 1, auxiliary, target, source)
hanoi(3, 'A', 'C', 'B')
No split tab
Налаштування cookies
Ми використовуємо необхідні cookies для роботи сайту. З вашого дозволу ми також можемо зберігати налаштування сайту та використовувати аналітичні й рекламні cookies, щоб розуміти використання сайту й підтримувати розвиток проєкту.
* Ви завжди можете змінити свій вибір у налаштуваннях сайту.
Оберіть категорії cookies
Налаштування аналітики
Можна вимкнути аналітику використання платформи. Також можна надіслати в Google Analytics запит на видалення даних про використання цього сайту, пов'язаних із цим браузером.
Навчальний workspace
Навчайтеся, читаючи, запускаючи код і розв'язуючи задачі.
Практикуйте програмування з поясненнями тем, вправами, інструментами browser IDE, перевіркою regex і тренуванням друку коду в одному workspace.
Відкривайте інструменти у вкладках.Вправи, IDE-інструменти й тренажери залишаються доступними як вкладки сайту.
Перемикайтеся без втрати контексту.Переходьте між поясненнями, кодом та утилітами, зберігаючи своє місце.
Використовуйте sidebar як карту.Ліві панелі містять навігацію, налаштування, файли, libraries та керування інструментами.
PythonJavaScriptSQLite
Одна IDE, три практичні режими
Python у браузері.Запускайте невеликі скрипти, пробуйте бібліотеки й тренуйте API-запити без встановлення.
JavaScript для швидких експериментів.Перевіряйте код для браузера й порівнюйте ідеї поруч із навчальними матеріалами.
SQLite для практики з даними.Відкривайте оглядач бази даних, переглядайте таблиці, пишіть запити й вивчайте SQL локально.
ТемаIDE
Працюйте поруч у split tabs
Тримайте інструкції перед очима.Відкрийте вправу або довідкову сторінку поруч з IDE, замість постійних перемикань.
Порівнюйте інструменти під час навчання.Розміщуйте перевірки regex, пояснення та експерименти з кодом поруч, коли це потрібно для задачі.
Закрийте split, коли завершите.Workspace повернеться до однієї сфокусованої вкладки, а відкриті вкладки сайту залишаться доступними.
Тренажер друку коду
Або звичайного тексту
Тренажер розрахований на фізичну клавіатуру.Відкрийте цей розділ на ноутбуці або комп'ютері з широким екраном. На телефоні тренування друку не працюватиме коректно.
Швидкість: 0 зн/хв
0 слів/хв
Найкраща швидкість (60с): 0 зн/хв
0 слів/хв
Помилки: 0
Загальний час: 0.0 с
Щоб тренувати сліпий друк, не підглядайте на фізичну клавіатуру.