Iteracija vs rekursija — kokie yra kompromisai?

Question

Accepted Answer

**Iteracija** naudoja ciklus; **rekursija** naudoja savireferencijas. Jie yra vienodai galingi (ką galite padaryti su vienu, galite padaryti su kitu), tačiau jie skiriasi aiškumu ir kaina.

## Šalia šalia

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

## Palyginimas

| Aspektas | Iteracija | Rekursija |
|--------|-----------|-----------|  
| Atmintis | O(1) papildomos | O(gylis) stack |
| Skaitomumas | puikiai tinka linijiniam darbui | puikiai tinka medžiams / dalijimui ir užkariaujimui |
| Rizika | begalinis ciklas | stack perpildymas |
| Greitis | paprastai greitesnis (nėra skambinimo išlaidos) | skambinimo išlaida per kadrą |

## Kada naudoti kurį

- Naudokite **iteraciją** paprastiems linijiniams perėjimams ir kai stack gylis gali būti didelis.
- Naudokite **rekursiją** kai problema yra natūraliai rekursinė (medžiai, grafikai, atgalinis sekimas) ir gylis yra ribojamas.

## Pavojinga vieta

Gili rekursija rizikuoja stack perpildymu; konvertuokite karštą rekursinį kodą į iteraciją (dažnai su aiškiu stack) kai gylis yra neribojamas.

## Kodėl tai svarbu

Tinkamo stiliaus pasirinkimas išlaiko kodą tiek teisingą, tiek skaitomą.

Rekursija daro medžių ir grafikų kodą elegantiškų, tačiau žinodami jos atminties kainą, galite išvengti strigimo esant giliems įėjimams.

Šis kompromiso sprendimas yra tiksliai tai, ką tiria pokalbio vedėjai, kai jie jus prašo "konvertuoti tai į iteracinę formą."

Aspektas	Iteracija	Rekursija
Atmintis	O(1) papildomos	O(gylis) stack
Skaitomumas	puikiai tinka linijiniam darbui	puikiai tinka medžiams / dalijimui ir užkariaujimui
Rizika	begalinis ciklas	stack perpildymas
Greitis	paprastai greitesnis (nėra skambinimo išlaidos)	skambinimo išlaida per kadrą