Iterație versus recursie — care sunt compromisurile?

Question

Accepted Answer

**Iterația** folosește bucle; **recursia** folosește self-calls. Sunt la fel de puternice (orice poți face cu una poți face și cu cealaltă), dar diferă în claritate și cost.

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

| Aspect | Iterație | Recursie |
|--------|----------|----------|
| Memory | O(1) extra | O(depth) stack |
| Readability | excelent pentru munca liniară | excelent pentru arbori / divide-and-conquer |
| Risk | buclă infinită | stack overflow |
| Speed | de obicei mai rapid (fără overhead de apel) | overhead de apel pe frame |

## Când să folosești care

- Folosește **iterația** pentru traversări liniare simple și când adâncimea stack-ului ar putea fi mare.
- Folosește **recursia** când problema este în mod natural recursivă (arbori, grafuri, backtracking) și adâncimea este limitată.

## Capcane

Recursia profundă riscă stack overflow; convertește codul recursiv critică în iterație (adesea cu o stack explicită) când adâncimea este nelimitată.

## De ce conteaza

Alegerea stilului corect ține codul atât corect cât și citibil.

Recursia face codul arborilor și grafurilor elegant, dar cunoscând costul memoriei, poți evita prăbușirile pe intrări profunde.

Această judecată de compromis este exact ce investigheaza intervievatorii când te cer să "convertești asta în iterativ."

Aspect	Iterație	Recursie
Memory	O(1) extra	O(depth) stack
Readability	excelent pentru munca liniară	excelent pentru arbori / divide-and-conquer
Risk	buclă infinită	stack overflow
Speed	de obicei mai rapid (fără overhead de apel)	overhead de apel pe frame