Итерация против рекурсии — каковы компромиссы?

Question

Accepted Answer

**Итерация** использует циклы; **рекурсия** использует self-calls. Они одинаково мощны (всё, что можно сделать с одной, можно сделать с другой), но отличаются ясностью и стоимостью.

## Side by side

```python
# Iterative sum: constant extra space
def sum_iter(n):
    total = 0
    for i in range(1, n + 1):
        total += i        # accumulate in a loop
    return total

# Recursive sum: uses the call stack
def sum_rec(n):
    if n == 0:
        return 0
    return n + sum_rec(n - 1)
```

## Comparison

| Аспект | Итерация | Рекурсия |
|--------|----------|----------|
| Memory | O(1) extra | O(depth) stack |
| Readability | отлично для линейной работы | отлично для деревьев / divide-and-conquer |
| Risk | бесконечный цикл | stack overflow |
| Speed | обычно быстрее (без overhead вызовов) | overhead вызовов за frame |

## Когда использовать что

- Используйте **итерацию** для простых линейных обходов и когда глубина стека может быть большой.
- Используйте **рекурсию** когда задача естественно рекурсивна (деревья, графы, backtracking) и глубина ограничена.

## Ловушки

Глубокая рекурсия рискует stack overflow; преобразуйте горячий рекурсивный код в итерацию (часто с явным стеком) когда глубина неограничена.

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

Выбор правильного стиля сохраняет код одновременно корректным и читаемым.

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

Этот компромисс — то, что интервьюеры проверяют, когда просят вас "преобразовать это в итеративный вариант."

Аспект	Итерация	Рекурсия
Memory	O(1) extra	O(depth) stack
Readability	отлично для линейной работы	отлично для деревьев / divide-and-conquer
Risk	бесконечный цикл	stack overflow
Speed	обычно быстрее (без overhead вызовов)	overhead вызовов за frame