Apakah itu recursion?

Question

Accepted Answer

**Recursion** ialah apabila sesuatu fungsi memanggil dirinya sendiri untuk menyelesaikan versi yang lebih kecil bagi masalah yang sama. Setiap recursion memerlukan **base case** yang menghentikannya dan **recursive case** yang bergerak ke arah base case.

## Ideanya

Pecahkan sesuatu masalah kepada submasalah lebih kecil yang serupa. Setiap panggilan menolak satu frame ke atas **call stack**; pulangan (return) mengeluarkannya semula.

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

## Surih (trace)

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

## Kompleksiti

Di sini masa **O(n)** dan ruang stack **O(n)** (satu frame bagi setiap panggilan).

## Perangkap

- **Base case yang tertinggal** -> recursion tak terhingga -> stack overflow.
- Recursion yang terlalu dalam boleh menghabiskan stack; sesetengah bahasa tiada tail-call optimization.
- Mengira semula submasalah yang bertindih boleh membengkak kepada masa eksponen (atasi dengan memoization).

## Mengapa ia penting

Recursion menyatakan masalah yang secara semula jadi serupa dengan dirinya — pokok (tree), graf, divide and conquer — jauh lebih kemas berbanding gelung.

Ia merupakan model mental di sebalik merge sort, backtracking, dan dynamic programming.

Memahami call stack juga menjadikan anda lebih mahir menyahpepijat dan menaakul tentang memori.