Рекурсии в python

Tags:

Published 8 июля 2025 г. 12:28 by max_summer

Рекурсия в Python — это техника программирования, при которой функция вызывает саму себя для решения задачи. Рекурсивные функции полезны для решения задач, которые можно разбить на более мелкие подзадачи того же типа.

Основные принципы рекурсии:

  1. Базовый случай (условие выхода) — условие, при котором рекурсия прекращается.
  2. Рекурсивный случай — вызов функции самой себя с изменёнными параметрами, приближающими к базовому случаю.

Пример: Факториал числа

Факториал числа ( 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 ```

Важные моменты:

  1. Глубина рекурсии — Python имеет ограничение на глубину рекурсии (обычно около 1000 вызовов). Если превысить этот лимит, возникнет ошибка RecursionError.
  2. Оптимизация — рекурсивные решения могут быть менее эффективными из-за накладных расходов на вызов функции. Для оптимизации можно использовать мемоизацию (кэширование результатов) или переписать алгоритм в итеративном стиле.

Пример с мемоизацией (кэшированием):

```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 ```

Когда использовать рекурсию?

Когда избегать рекурсии?

Если у вас есть конкретная задача, которую нужно решить с помощью рекурсии, спрашивайте! 😊

Share this post

Similar posts

There are no similar posts yet.

0 comments

There are no comments

Add a new comment