На пятой неделе курса мы рассмотрим один из фундаментальных концептов в программировании — рекурсию. Вы узнаете, как функции могут вызывать сами себя, как использовать стек вызовов, а также какие алгоритмы строятся на рекурсивном подходе. Также познакомимся с понятием хвостовой рекурсии и базовыми примерами.
Рекурсия — это ситуация, когда функция вызывает саму себя для решения подзадачи.
Каждая рекурсивная функция должна иметь:
- базовый случай (условие завершения);
- шаг рекурсии (вызов самой себя с другим аргументом).
```python```
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
```python```
def fib(n):
if n <= 1:
return n
else:
return fib(n - 1) + fib(n - 2)
Этот алгоритм неэффективен без оптимизации — он выполняет экспоненциальное число вызовов.
Для ускорения можно использовать кеширование результатов:
```python```
memo = {}
def fib(n):
if n in memo:
return memo[n]
if n <= 1:
memo[n] = n
else:
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
Это форма рекурсии, когда результат функции возвращается сразу без дополнительных вычислений после рекурсивного вызова. Python не поддерживает оптимизацию хвостовой рекурсии, но можно имитировать её с помощью циклов.
Рекурсивные решения проще и понятнее для задач с вложенной или повторяющейся структурой (деревья, графы), но могут быть менее эффективны.
Итеративные решения предпочтительны, если важна производительность и экономия памяти.
1. Быстрая сортировка (QuickSort)
2. Поиск в глубину (DFS)
3. Обход дерева (inorder, preorder, postorder)
4. Разбиение задач (разделяй и властвуй)
1. Напишите рекурсивную функцию вычисления степени числа.
2. Реализуйте DFS на графе.
3. Напишите функцию, которая проверяет, является ли строка палиндромом (рекурсивно).