3.5 Rekursjon og algoritmekompleksitet

Rekursjon og algoritmekompleksitet

Tenk deg at du står framfor eit spegel som reflekterer eit anna spegel. Du ser deg sjølv, som ser deg sjølv, som ser deg sjølv, i ei tilsynelatande uendeleg rekkje av refleksjonar. Dette er ein visuell metafor for rekursjon: noko som refererer til seg sjølv.

I programmering er rekursjon ein kraftig teknikk der ein funksjon løyser eit problem ved å kalle seg sjølv med eit enklare delproblem. Det kan verke magisk, kanskje til og med litt forvirrande, den fyrste gongen du ser det, men det er eigentleg eit elegant verktøy for å løyse problem som naturleg kan delast inn i like, men enklare delproblem.

I tillegg til rekursjon skal vi i dette kapittelet sjå på algoritmekompleksitet, ein måte å måle og samanlikne effektiviteten til algoritmar på. Vi har allereie sett at binærsøk er raskare enn lineært søk, og at sorteringsalgoritmar har ulik yting. Big O-notasjonen gir oss eit presist språk for å snakke om desse skilnadene.

Rekursjon med fakultet

Det klassiske dømet på rekursjon er utrekning av fakultet. Fakultet av n (skrive n!) er produktet av alle positive heiltal frå 1 til n:

- 5! = 5 × 4 × 3 × 2 × 1 = 120
- 3! = 3 × 2 × 1 = 6
- 1! = 1
- 0! = 1 (per definisjon)

Det finst ein elegant rekursiv definisjon:
- n! = n × (n-1)! for n > 0
- 0! = 1 (basistilfelle)

Altså: 5! = 5 × 4!, og 4! = 4 × 3!, og så vidare til vi når 0! = 1.

Iterativ løysing (med løkke):

def fakultet_iterativ(n):
    resultat = 1
    for i in range(1, n + 1):
        resultat *= i
    return resultat

Rekursiv løysing:

def fakultet(n):
    # Basistilfelle
    if n == 0:
        return 1
    # Rekursivt tilfelle
    return n * fakultet(n - 1)

print(fakultet(5))  # 120
print(fakultet(0))  # 1

Kva skjer når vi kallar fakultet(4)?

fakultet(4) = 4 * fakultet(3)
                   = 3 * fakultet(2)
                            = 2 * fakultet(1)
                                     = 1 * fakultet(0)
                                              = 1  ← basistilfelle!
                                     = 1 * 1 = 1
                            = 2 * 1 = 2
                   = 3 * 2 = 6
             = 4 * 6 = 24

Funksjonen kallar seg sjølv med stadig mindre verdiar av n til han når basistilfellet (n == 0). Deretter vert resultatet «rulla» tilbake opp gjennom alle kalla.

Fibonacci-tala

Fibonacci-tallrekkja er eit berømt døme som passar naturleg til rekursjon. Kvart tal er summen av dei to føregåande:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Rekursiv definisjon:
- fib(0) = 0
- fib(1) = 1
- fib(n) = fib(n-1) + fib(n-2) for n > 1

def fibonacci(n):
    # Basistilfeller
    if n == 0:
        return 0
    if n == 1:
        return 1
    # Rekursivt tilfelle
    return fibonacci(n - 1) + fibonacci(n - 2)

# Skriv ut de 10 første Fibonacci-tallene
for i in range(10):
    print(f"fib({i}) = {fibonacci(i)}")

Kjøring:

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34

Fibonacci-rekursjonen har eit viktig problem: han er svært ineffektiv! For å rekne ut fibonacci(5) vert fibonacci(3) kalla to gonger, fibonacci(2) tre gonger, og så vidare. Talet på kall veks eksponentielt. fibonacci(40) kan ta fleire sekund, og fibonacci(100) ville ta lengre tid enn levetida til universet!

Effektiv iterativ versjon:

def fibonacci_effektiv(n):
    if n <= 1:
        return n
    forrige = 0
    naavaerende = 1
    for _ in range(2, n + 1):
        forrige, naavaerende = naavaerende, forrige + naavaerende
    return naavaerende

print(fibonacci_effektiv(50))  # 12586269025 (umiddelbart!)

Denne iterative versjonen reknar ut fibonacci(50) umiddelbart, medan den rekursive versjonen ville bruke ufatteleg lang tid. Dette illustrerer at rekursjon ikkje alltid er den beste løysinga, sjølv om han er elegant.

Forstå Big O-notasjon

Big O-notasjon gir oss eit språk for å snakke om kor raskt ein algoritme veks i tid eller plass når inndataen vert større. Vi bryr oss ikkje om nøyaktig tal på operasjonar, men om veksthastigheita.

Dei vanlegaste kompleksitetsklassane (frå raskast til tregast):

Big O i praksis: korleis bestemme kompleksiteten

O(1) – Konstant tid:
Operasjonen tek like lang tid uansett storleiken på inndataen.

# O(1) – å hente et element fra en liste via indeks
def hent_forste(liste):
    return liste[0]  # Alltid 1 operasjon

O(n) – Lineær tid:
Tida veks proporsjonalt med inndataen. Éi løkke gjennom n element.

# O(n) – lineært søk
def finn_maks(liste):
    storst = liste[0]
    for tall in liste:       # n gjennomløp
        if tall > storst:
            storst = tall
    return storst

O(n²) – Kvadratisk tid:
Nøsta løkker der begge går gjennom n element.

# O(n²) – boblesortering
def boblesortering(liste):
    n = len(liste)
    for i in range(n):           # n gjennomløp
        for j in range(n - 1):   # n gjennomløp for hvert i
            if liste[j] > liste[j + 1]:
                liste[j], liste[j + 1] = liste[j + 1], liste[j]

O(log n) – Logaritmisk tid:
Halverer dataa i kvart steg.

# O(log n) – binærsøk halverer søkeområdet
def binaersok(liste, maal):
    lav, hoy = 0, len(liste) - 1
    while lav <= hoy:            # Halverer for hvert steg
        midt = (lav + hoy) // 2
        if liste[midt] == maal:
            return midt
        elif liste[midt] < maal:
            lav = midt + 1
        else:
            hoy = midt - 1
    return -1

Tommelfingerreglar:
- Éi enkel løkke gjennom n element → O(n)
- To nøsta løkker gjennom n element → O(n²)
- Tre nøsta løkker → O(n³)
- Halvering i kvart steg → O(log n)
- Éi løkke med halvering i kvart steg → O(n log n)

Oppsummering

I dette kapittelet har du lært:

- Rekursjon: ein funksjon som kallar seg sjølv.
- Basistilfelle og rekursivt tilfelle: stopp og gjentaking.
- Døme: fakultet, Fibonacci og rekursivt binærsøk.
- Big O-notasjon: skildrar ressursbruken til algoritmen.
- Vanlege kompleksitetar: O(1), O(log n), O(n) og O(n^2).

Nøkkelbegrep