Recursion ni nini?

Question

Recursion ni nini?

Accepted Answer

**Recursion** ni wakati ambao kazi inaitisha yenyewe ili kutatua toleo dogo la tatizo moja. Kila recursion inahitaji **base case** inayoizuia na **recursive case** inayosogea kuelekea base.

## Wazo

Gawanya tatizo kuwa matatizo madogo yanayofanana. Kila simu inaeneza frame kwenye **call stack**; kurudi zinaondoa.

## Mfano

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

## Njia

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

## Utata

Hapa **O(n)** wakati na **O(n)** nafasi ya stack (frame moja kwa kila simu).

## Mitego

- **Base case inayokosa** -> recursion isiyo na mwisho -> stack overflow.
- Recursion nene inaweza kumkamata stack; baadhi ya lugha hazina tail-call optimization.
- Kuhesabu upya matatizo yanayoingiliana yanaweza kulipuka hadi wakati wa kielektroniki (sahihisha kwa memoization).

## Kwa nini ni muhimu

Recursion inaeleza kwa kabidhaa tatizo zinazozifanana zenyewe — miti, grafu, gawanya na kushinda — kubwa sana safi zaidi kuliko loops.

Ni muundo wa fikiria nyuma ya merge sort, backtracking, na dynamic programming.

Kuelewa call stack pia kukufanya wewe ni nzuri zaidi kwa debugging na kuzingatia juu ya kumbukumbu.