Iteracja a rekurencja — jakie są kompromisy?

Question

Accepted Answer

**Iteracja** używa pętli; **rekurencja** używa samo-wywołań. Są one równie potężne (cokolwiek możesz zrobić z jednym, możesz zrobić z drugim), ale różnią się przejrzystością i kosztami.

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

| Aspekt | Iteracja | Rekurencja |
|--------|----------|----------|
| Memory | O(1) extra | O(depth) stack |
| Readability | świetnie do pracy liniowej | świetnie do drzew / divide-and-conquer |
| Risk | nieskończona pętla | stack overflow |
| Speed | zwykle szybciej (bez narzutu wywołań) | narzut wywołań na ramkę |

## Kiedy użyć którego

- Użyj **iteracji** do prostych przechodzić liniowych i gdy głębokość stosu może być duża.
- Użyj **rekurencji** gdy problem jest naturalnie rekurencyjny (drzewa, grafy, backtracking) i głębokość jest ograniczona.

## Pułapki

Głęboka rekurencja grozi переполнением stosu; konwertuj gorący kod rekurencyjny na iterację (często z jawnym stosem) gdy głębokość jest nieograniczona.

## Dlaczego to ważne

Wybór właściwego stylu utrzymuje kod zarówno poprawnym, jak i czytelnym.

Rekurencja sprawia, że kod drzew i grafów jest elegancki, ale znając jej koszt pamięci, możesz uniknąć awarii na głębokich danych wejściowych.

Ta ocena kompromisów to dokładnie to, co badają rozmówcy, gdy proszą cię o "konwersję tego na iteracyjny."

Aspekt	Iteracja	Rekurencja
Memory	O(1) extra	O(depth) stack
Readability	świetnie do pracy liniowej	świetnie do drzew / divide-and-conquer
Risk	nieskończona pętla	stack overflow
Speed	zwykle szybciej (bez narzutu wywołań)	narzut wywołań na ramkę