Lelaran vs rekursi — apakah pertukaran-pertukaran itu?

Question

Accepted Answer

**Lelaran** menggunakan gelung; **rekursi** menggunakan panggilan-diri. Mereka sama kuatnya (apa pun yang anda lakukan dengan satu anda boleh lakukan dengan yang lain), namun mereka berbeza dalam kejelasan dan kos.

## Berdampingan

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

## Perbandingan

| Aspek | Lelaran | Rekursi |
|--------|-----------|-----------|  
| Memori | O(1) tambahan | O(kedalaman) timbunan |
| Kebolehbacaan | bagus untuk kerja linear | bagus untuk pepohon / bahagi-dan-takluk |
| Risiko | gelung tak terbatas | limpahan timbunan |
| Kecepatan | biasanya lebih cepat (tiada overhed panggilan) | overhed panggilan setiap bingkai |

## Bila menggunakan yang mana

- Gunakan **lelaran** untuk traversal linear mudah dan apabila kedalaman timbunan boleh menjadi besar.
- Gunakan **rekursi** apabila masalah secara semula jadi rekursif (pepohon, grafik, penjejakan kembali) dan kedalaman terikat.

## Jebakan

Rekursi dalam risiko limpahan timbunan; tukarkan kod rekursi panas kepada lelaran (sering dengan timbunan eksplisit) apabila kedalaman tak terbatas.

## Mengapa ini penting

Memilih gaya yang tepat mengekalkan kod yang betul dan boleh dibaca.

Rekursi membuat kod pohon dan grafik elegan, tetapi mengetahui kos memorinya membolehkan anda mengelakkan ranap pada masukan mendalam.

Pertimbangan pertukaran ini adalah betul apa yang pemeriksa terokai apabila mereka meminta anda "tukarkan ini kepada lelaran."

Aspek	Lelaran	Rekursi
Memori	O(1) tambahan	O(kedalaman) timbunan
Kebolehbacaan	bagus untuk kerja linear	bagus untuk pepohon / bahagi-dan-takluk
Risiko	gelung tak terbatas	limpahan timbunan
Kecepatan	biasanya lebih cepat (tiada overhed panggilan)	overhed panggilan setiap bingkai