Apa itu rekursi?

Question

Apa itu rekursi?

Accepted Answer

**Rekursi** adalah ketika sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan versi lebih kecil dari masalah yang sama. Setiap rekursi membutuhkan **kasus dasar** yang menghentikannya dan **kasus rekursif** yang bergerak menuju dasar.

## Idenya

Pecah masalah menjadi submasalah yang lebih kecil dan identik. Setiap pemanggilan mendorong bingkai ke **call stack**; pengembalian mengeluarkannya.

## Contoh

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## Jejak

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## Kompleksitas

Di sini **O(n)** waktu dan **O(n)** ruang stack (satu bingkai per pemanggilan).

## Jebakan

- **Kasus dasar hilang** -> rekursi tak terbatas -> stack overflow.
- Rekursi dalam dapat menghabiskan stack; beberapa bahasa kekurangan optimasi tail-call.
- Menghitung ulang submasalah yang tumpang tindih dapat melonjak ke waktu eksponensial (perbaiki dengan memoization).

## Mengapa ini penting

Rekursi mengekspresikan secara alami masalah yang serupa dengan diri sendiri — pohon, grafik, bagi dan taklukkan — jauh lebih bersih daripada loop.

Ini adalah model mental di balik merge sort, backtracking, dan pemrograman dinamis.

Memahami call stack juga membuat Anda lebih baik dalam debugging dan penalaran tentang memori.