# Рекурсия в информатике: примеры, принципы и магия самоповтора

31 мая 2025

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

## Что такое рекурсия?

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

“`python
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n – 1)
“`

Здесь функция `factorial` вызывает саму себя, уменьшая аргумент на каждом шаге, пока не достигнет базового случая (`n == 1`).

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

1. **Базовый случай** — условие выхода из рекурсии. Без него программа уйдет в бесконечный цикл.
2. **Рекурсивный случай** — шаг, на котором функция вызывает саму себя с измененными параметрами.
3. **Сходимость** — каждый рекурсивный вызов должен приближать к базовому случаю.

## Примеры рекурсии в программировании

### 1. Числа Фибоначчи

Классический пример, где каждое число равно сумме двух предыдущих:

“`python
def fibonacci(n):
if n <= 1: return n else: return fibonacci(n - 1) + fibonacci(n - 2) ``` ### 2. Обход дерева Рекурсия идеально подходит для работы с древовидными структурами, например, при парсинге JSON или обходе файловой системы: ```python def traverse_directory(path): for item in os.listdir(path): full_path = os.path.join(path, item) if os.path.isdir(full_path): traverse_directory(full_path) # Рекурсивный вызов для подкаталога else: print(full_path) ``` ### 3. Ханойская башня Эта математическая головоломка решается через рекурсию: ```python def hanoi(n, source, target, auxiliary): if n > 0:
hanoi(n – 1, source, auxiliary, target) # Перемещаем n-1 дисков на вспомогательный стержень
print(f”Переместить диск {n} с {source} на {target}”)
hanoi(n – 1, auxiliary, target, source) # Перемещаем n-1 дисков на целевой стержень
“`

## Преимущества и недостатки рекурсии

### **Плюсы:**
– Упрощает код для задач с вложенной структурой.
– Позволяет элегантно решать задачи, которые сложно реализовать итеративно.

### **Минусы:**
– Может потреблять много памяти из-за стека вызовов.
– Риск переполнения стека при глубокой рекурсии.

## Оптимизация: хвостовая рекурсия и мемоизация

В некоторых языках (например, Haskell) рекурсия оптимизируется через **хвостовую рекурсию**, где последняя операция — вызов функции. В Python можно использовать **мемоизацию** (кеширование результатов):

“`python
from functools import lru_cache

@lru_cache
def fibonacci(n):
if n <= 1: return n else: return fibonacci(n - 1) + fibonacci(n - 2) ``` ## Заключение Рекурсия — мощный инструмент, который делает код чище и выразительнее. Но важно помнить о базовом случае и следить за глубиной вызовов. Освоив рекурсию, вы сможете решать задачи, которые кажутся невероятно сложными на первый взгляд. А какие рекурсивные алгоритмы используете вы? Делитесь в комментариях! **Количество слов:** 598