Iteration kontra rekursion — vilka är kompromissen?

Question

Accepted Answer

**Iteration** använder loopar; **rekursion** använder självanrop. De är lika kraftfulla (allt du kan göra med en kan du göra med den andra), men de skiljer sig i klarhet och kostnad.

## Sida vid sida

```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)
```

## Jämförelse

| Aspekt | Iteration | Rekursion |
|--------|-----------|----------|
| Minne | O(1) extra | O(djup) stack |
| Läsbarhet | bra för linjärt arbete | bra för träd / dela-och-härska |
| Risk | oändlig loop | stack overflow |
| Hastighet | vanligtvis snabbare (ingen samtalskostnad) | samtalskostnad per ram |

## När du ska använda vilken

- Använd **iteration** för enkla linjära genomföranden och när stackdjupet kan vara stort.
- Använd **rekursion** när problemet är naturligt rekursivt (träd, grafer, backtracking) och djupet är begränsat.

## Fallgropar

Djup rekursion riskerar stack overflow; konvertera het rekursiv kod till iteration (ofta med en explicit stack) när djupet är obegränsat.

## Varför det spelar roll

Att välja rätt stil håller koden både korrekt och läsbar.

Rekursion gör träd- och grafkod elegant, men genom att känna till dess minneskostnad kan du undvika krascher på djupa inmatningar.

Detta bedömningskompromiss är exakt vad intervjuare söker när de ber dig "konvertera detta till iterativ."

Aspekt	Iteration	Rekursion
Minne	O(1) extra	O(djup) stack
Läsbarhet	bra för linjärt arbete	bra för träd / dela-och-härska
Risk	oändlig loop	stack overflow
Hastighet	vanligtvis snabbare (ingen samtalskostnad)	samtalskostnad per ram