Mi a rekurzió?

Question

Mi a rekurzió?

IT Interview Practice · Accepted Answer

**A rekurzió** az amikor egy függvény önmagát hívja meg az ugyanez probléma kisebb verziójának megoldásához. Minden rekurziónak szüksége van egy **alapesetre** amely leállítja és egy **rekurzív esetre** amely az alap felé halad.

## Az ötlet

Osszuk fel a problémát kisebb azonos alproblémákra. Minden hívás egy keretet tolókat fel a **hívási veremre**; a visszatérések eltávolítják őket.

## Például

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

## Nyomkövetés

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

## Bonyolultság

Itt **O(n)** idő és **O(n)** verem terület (egy keret hívásonként).

## Csapdák

- **Hiányzik az alapeset** -> végtelen rekurzió -> verem túlcsordulás.
- Mély rekurzió kimerülhet a veremen; egyes nyelvek nem támogatják a véghajtási optimalizálást.
- Az átfedő alproblémák újraszámítása exponenciális időre növekedhet (memoizálással rögzítse).

## Miért fontos

A rekurzió természetesen fejezi ki az öngeminális problémákat — fákat, gráfokat, oszd meg és hódítsd meg — sokkal tisztábban mint hurkokat.

Ez az elméleti modell a merge sort, backtracking és dinamikus programozás mögött.

A hívási verem megértése jobbá tesz a hibakeresésben és a memória érvelésében is.

Az ötlet

Például

Nyomkövetés

Bonyolultság

Csapdák

Miért fontos

Kapcsolódó kérdések