Iterasi versus rekursi — apa saja trade-off-nya?

Question

IT Interview Practice · Accepted Answer

**Iterasi** menggunakan loop; **rekursi** menggunakan panggilan diri. Keduanya sama kuatnya (apa pun yang bisa kamu lakukan dengan satu bisa kamu lakukan dengan yang lain), tetapi mereka berbeda dalam kejelasan dan biaya.

## 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 | Iterasi | Rekursi |
|--------|-----------|----------|
| Memori | O(1) ekstra | O(kedalaman) stack |
| Keterbacaan | sempurna untuk pekerjaan linier | sempurna untuk pohon / bagi-dan-taklukkan |
| Risiko | loop tak terbatas | stack overflow |
| Kecepatan | biasanya lebih cepat (tanpa overhead panggilan) | overhead panggilan per frame |

## Kapan menggunakan mana

- Gunakan **iterasi** untuk traversal linier sederhana dan ketika kedalaman stack bisa besar.
- Gunakan **rekursi** ketika masalahnya secara alami rekursif (pohon, graf, backtracking) dan kedalaman terbatas.

## Jebakan

Rekursi dalam berisiko stack overflow; ubah kode rekursif panas menjadi iterasi (sering dengan stack eksplisit) ketika kedalaman tidak terbatas.

## Mengapa ini penting

Memilih gaya yang tepat membuat kode tetap benar dan mudah dibaca.

Rekursi membuat kode pohon dan graf elegan, tetapi mengetahui biaya memorinya memungkinkan kamu menghindari kerusakan pada input dalam.

Pertimbangan trade-off ini adalah persis apa yang diuji pewawancara ketika mereka meminta kamu untuk "ubah ini menjadi iteratif."

Aspek	Iterasi	Rekursi
Memori	O(1) ekstra	O(kedalaman) stack
Keterbacaan	sempurna untuk pekerjaan linier	sempurna untuk pohon / bagi-dan-taklukkan
Risiko	loop tak terbatas	stack overflow
Kecepatan	biasanya lebih cepat (tanpa overhead panggilan)	overhead panggilan per frame

Berdampingan

Perbandingan

Kapan menggunakan mana

Jebakan

Mengapa ini penting

Pertanyaan terkait