Çfarë është rekurzioni?

Question

Accepted Answer

**Rekurzioni** është kur një funksion thërret veten për të zgjidhur një version më të vogël të problemit të njëjtë. Çdo rekurcion ka nevojë për një **rast bazë** që e ndalon atë dhe një **rast rekurziv** që lëviz drejt bazës.

## Ideja

Thye një problem në nënprobleme më të vogla identike. Çdo thirrje shtyn një frame në **call stack**; kthimet i heqin ato.

## Shembull

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

## Gjurmim

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

## Kompleksiteti

Këtu **O(n)** kohë dhe **O(n)** hapësirë stack (një frame për çdo thirrje).

## Grackë

- **Rast bazë që mungon** -> rekurzioni i pafund -> stack overflow.
- Rekurzioni i thellë mund të shterë stack; disa gjuhë nuk kanë optimizim tail-call.
- Rillogaritja e nënproblemeve që mbivendosen mund të shpërthet në kohë eksponenciale (rregulloje me memoization).

## Pse rëndëson

Rekurzioni shpreh natyrshëm problemet e ngjashme me veten — pemë, grafe, ndaj dhe sundimoje — shumë më pastër sesa sythe.

Është modeli mental prapa merge sort, backtracking dhe programimit dinamik.

Kuptimi i call stack të bën edhe më të mirë në debug dhe arsyetim rreth memories.