Kas yra rekursija?

Question

Kas yra rekursija?

Accepted Answer

**Rekursija** yra tada, kai funkcija iškviečia save pačią, siekdama išspręsti mažesnę tą pačią problemą. Kiekviena rekursija turi **bazinį atvejį**, kuris ją sustabdo, ir **rekursinį atvejį**, kuris judėja link bazinio.

## Idėja

Problemą suskaidykite į mažesnes identiškas potarinius uždavinius. Kiekvienas iškvietime į **call stack** nukreipia kadrą; grįžimimai juos nuimti.

## Pavyzdys

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

## Atsekimas

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

## Sudėtingumas

Čia **O(n)** laikas ir **O(n)** stack vieta (po vieną kadro kiekviename iškvietime).

## Spąstai

- **Trūkstamas bazinis atvejis** -> begalinė rekursija -> stack perpildymas.
- Gili rekursija gali išeikvoją stack; kai kuriose kalbose trūksta tail-call optimizacijos.
- Persidubliavus sutampančius potarinius uždavinius gali išaugti iki eksponentinio laiko (paprasta fix su memoization).

## Kodėl tai svarbu

Rekursija natūraliai išreiškia savę panašias problemas — medžius, grafus, divide and conquer — daug aiškiau nei kilpos.

Tai yra mentalinis modelis, esantis merge sort, backtracking ir dinaminės programavimo pagrinde.

Suprasdami call stack, taip pat geriau mokysite debug ir samprotauti apie atmintį.