X'inhi r-rekursjoni?

Question

Accepted Answer

**Ir-rekursjoni** hija meta funzjoni tissejjaħ lest stessa biex tissolvi verżjoni isgħira tal-istess problema. Kull rekursjoni għandha bżonn **każ bażiku** li twaqqifha u **każ rikursiv** li jimxi lejn il-bażi.

## L-idea

Iqsam problema f'problemi identiki isgħar. Kull sejħa timbuttaċa frame fuq il-**call stack**; ir-ritorni tneħħihom.

## Eżempju

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

## Traċċa

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

## Kumplessità

Hawnhekk **O(n)** ħin u **O(n)** spazju stack (frame wieħed għal kull sejħa).

## Ħwienet

- **Każ bażiku nieqes** -> rekursjoni infinita -> stack overflow.
- Rekursjoni profonda tista' ħlewweġ il-stack; xi lingwi m'għandhomx tail-call optimization.
- Ir-rikomputazzjoni ta' subproblemi li jikkoinċidu tista' tisplodi għal ħin esponenzjali (issottlija b'memoization).

## Għaliex hija importanti

Ir-rekursjoni tesprimi b'mod naturali problemi li huma self-similar — siġar, grafs, divide and conquer — ħafna aktar sakta minn loops.

Hija l-mudell mentali wara merge sort, backtracking, u dynamic programming.
"%

L-għarfien tal-call stack jagħmel ukoll lil ħadd aħjar fl-debugging u fit-tħassib dwar il-memorja.