Apa iku recursion?

Question

Apa iku recursion?

Accepted Answer

**Recursion** yaiku nalika sawijining fungsi nyebutake dhewe dhéwé kanggo nglesaiki versi sing luwih cilik saka masalah sing padha. Saben recursion perlu **base case** sing menggawe mungkur lan **recursive case** sing mlaku menyang base.

## Ide kasebut

Pecahaké masalah dadi submasalah sing luwih cilik lan padha. Saben panggilan nyorong frame menyang **call stack**; mulih ngilusaké liyané.

## Conto

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

## Jejet

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

## Kompleksitas

Disin **O(n)** wektu lan **O(n)** ruang stack (siji frame saben panggilan).

## Jebakan

- **Base case ilang** -> recursion tanpa wates -> stack overflow.
- Recursion jero bisa ngobong-ngabangake stack; sawetara basa tanpa tail-call optimization.
- Ngilangi submasalah sing tumpang tindih bisa jadi wektu eksponensial (baureksa karo memoization).

## Apa sing penting

Recursion nampilake kanthi alami masalah sing padha karo dhewe — wit, grafik, pembagi lan kuwatake — luwih bersih tinimbang loop.

Iku minangka model mental ing balik merge sort, backtracking, lan pemrograman dinamis.

Ngerti call stack uga nggawéake sampeyan luwih apik ing debugging lan padumuk bab memori.