Mikä on rekursio?

Question

Mikä on rekursio?

Accepted Answer

**Rekursio** on kun funktio kutsuu itseään ratkaistakseen pienemmän version samasta ongelmasta. Jokainen rekursio tarvitsee **perusehdon (base case)**, joka pysäyttää sen, ja **rekursiivisen ehdon (recursive case)**, joka etenee kohti perusehtoa.

## Ajatus

Jaa ongelma pienempiin identtisiin osaongelmiin. Jokainen kutsu työntää kehyksen **kutsupinolle (call stack)**; palautukset poistavat ne.

## Esimerkki

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

## Jäljitys

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

## Monimutkaisuus

Täällä **O(n)** aika ja **O(n)** pinotila (yksi kehys kutsua kohti).

## Sudenkuopat

- **Puuttuva perusehto** -> ääretön rekursio -> pinoylityskään.
- Syvä rekursio voi kuluttaa pinon; joillakin kielillä ei ole tail-call-optimointia.
- Päällekkäisten osaongelmien uudelleenlaskenta voi nousta eksponentiaaliseen aikaan (korjaa memoizaatiolla).

## Miksi se on tärkeää

Rekursio ilmaisee luonnollisesti itseään muistuttavat ongelmat — puut, verkot, jaa ja valloita — paljon siistimmin kuin silmukat.

Se on ajattelumalli merge sortin, backtrakingin ja dynaamisen ohjelmoinnin takana.

Kutsupinojen ymmärtäminen tekee sinusta myös paremman debuggauksessa ja muistin päättelyssä.