Co to jest rekursja?

Question

Accepted Answer

**Rekursja** to sytuacja, w której funkcja wywołuje samą siebie, aby rozwiązać mniejszą wersję tego samego problemu. Każda rekursja wymaga **warunku bazowego** (base case), który ją zatrzymuje, oraz **przypadku rekurencyjnego** (recursive case), który zbliża się do warunku bazowego.

## Idea

Rozbij problem na mniejsze, identyczne podproblemy. Każde wywołanie umieszcza ramkę na **stosie wywołań** (call stack); powroty je usuwają.

## Przykład

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

## Śledzenie

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

## Złożoność

Tu **O(n)** czasu i **O(n)** pamięci stosu (jedna ramka na każde wywołanie).

## Pułapki

- **Brak warunku bazowego** -> nieskończona rekursja -> przepełnienie stosu.
- Głęboka rekursja może wyczerpać stos; niektóre języki nie mają optymalizacji tail-call.
- Ponowne obliczanie nakładających się podproblemów może prowadzić do czasu wykładniczego (napraw za pomocą memoizacji).

## Dlaczego to ważne

Rekursja naturalnie wyrażała samoilościowe problemy — drzewa, grafy, algorytmy typu "dziel i zwyciężaj" — znacznie czystszym sposobem niż pętle.

To jest model myślenia stojący za algorytmem merge sort, cofaniem (backtracking) i programowaniem dynamicznym.

Zrozumienie stosu wywołań również sprawia, że jesteś lepszy w debugowaniu i rozumowaniu o pamięci.