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

Question

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

Accepted Answer

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

## Идея

Разбейте задачу на меньшие идентичные подзадачи. Каждый вызов добавляет кадр в **стек вызовов** (call stack); возвраты их извлекают.

## Пример

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## Трассировка

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## Сложность

Здесь **O(n)** времени и **O(n)** пространства стека (один кадр на вызов).

## Подводные камни

- **Отсутствие базового случая** -> бесконечная рекурсия -> переполнение стека.
- Глубокая рекурсия может исчерпать стек; в некоторых языках отсутствует оптимизация tail-call.
- Пересчёт перекрывающихся подзадач может привести к экспоненциальному времени (исправьте мемоизацией).

## Почему это важно

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

Это ментальная модель, лежащая в основе merge sort, backtracking и динамического программирования.

Понимание стека вызовов также делает вас лучше в отладке и рассуждении о памяти.