Рекурсии в python
Published 8 июля 2025 г. 12:28 by max_summer
Рекурсия в Python — это техника программирования, при которой функция вызывает саму себя для решения задачи. Рекурсивные функции полезны для решения задач, которые можно разбить на более мелкие подзадачи того же типа.
Основные принципы рекурсии:
- Базовый случай (условие выхода) — условие, при котором рекурсия прекращается.
- Рекурсивный случай — вызов функции самой себя с изменёнными параметрами, приближающими к базовому случаю.
Пример: Факториал числа
Факториал числа ( n! ) определяется как произведение всех чисел от 1 до ( n ). Рекурсивное определение: [ n! = n \times (n-1)! ] Базовый случай: ( 0! = 1 ).
```python def factorial(n): if n == 0: # Базовый случай return 1 else: return n * factorial(n - 1) # Рекурсивный случай
print(factorial(5)) # Вывод: 120 ```
Пример: Числа Фибоначчи
Последовательность Фибоначчи определяется как: [ F(n) = F(n-1) + F(n-2) ] Базовые случаи: ( F(0) = 0 ), ( F(1) = 1 ).
```python def fibonacci(n): if n <= 1: # Базовый случай return n else: return fibonacci(n - 1) + fibonacci(n - 2) # Рекурсивный случай
print(fibonacci(6)) # Вывод: 8 ```
Пример: Вычисление суммы элементов списка
```python def sum_list(lst): if not lst: # Базовый случай: пустой список return 0 else: return lst[0] + sum_list(lst[1:]) # Рекурсивный случай
print(sum_list([1, 2, 3, 4])) # Вывод: 10 ```
Важные моменты:
- Глубина рекурсии — Python имеет ограничение на глубину рекурсии (обычно около 1000 вызовов). Если превысить этот лимит, возникнет ошибка
RecursionError
. - Оптимизация — рекурсивные решения могут быть менее эффективными из-за накладных расходов на вызов функции. Для оптимизации можно использовать мемоизацию (кэширование результатов) или переписать алгоритм в итеративном стиле.
Пример с мемоизацией (кэшированием):
```python from functools import lru_cache
@lru_cache(maxsize=None) # Декоратор для кэширования результатов def fibonacci(n): if n <= 1: return n else: return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(50)) # Быстро вычислит даже для больших n ```
Когда использовать рекурсию?
- Для задач, которые естественно разбиваются на подзадачи (например, обход деревьев, графа).
- Для задач с рекурсивным определением (например, факториал, числа Фибоначчи).
- Когда код с рекурсией проще и понятнее итеративного аналога.
Когда избегать рекурсии?
- Если задача требует большого количества рекурсивных вызовов (риск переполнения стека).
- Если важна производительность (рекурсивные вызовы могут быть медленнее из-за накладных расходов).
Если у вас есть конкретная задача, которую нужно решить с помощью рекурсии, спрашивайте! 😊
Similar posts
There are no similar posts yet.
0 comments
There are no comments