3.5 Rekursjon og algoritmekompleksitet

Rekursjon og algoritmekompleksitet

Tenk deg at du står foran et speil som reflekterer et annet speil. Du ser deg selv, som ser deg selv, som ser deg selv, i en tilsynelatende uendelig rekke av refleksjoner. Dette er en visuell metafor for rekursjon: noe som refererer til seg selv.

I programmering er rekursjon en kraftig teknikk der en funksjon løser et problem ved å kalle seg selv med et enklere delproblem. Det kan virke magisk, kanskje til og med litt forvirrende, den første gangen du ser det, men det er egentlig et elegant verktøy for å løse problemer som naturlig kan deles inn i like, men enklere delproblemer.

I tillegg til rekursjon skal vi i dette kapittelet se på algoritmekompleksitet, en måte å måle og sammenligne effektiviteten til algoritmer. Vi har allerede sett at binærsøk er raskere enn lineært søk, og at sorteringsalgoritmer har forskjellig ytelse. Big O-notasjonen gir oss et presist språk for å snakke om disse forskjellene.

Rekursjon med fakultet

Det klassiske eksempelet på rekursjon er beregning av fakultet. Fakultet av n (skrevet n!) er produktet av alle positive heltall fra 1 til n:

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

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

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

Iterativ løsning (med løkke):

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

Rekursiv løsning:

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

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

Hva skjer når vi kaller 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 kaller seg selv med stadig mindre verdier av n til den når basistilfellet (n == 0). Deretter «rulles» resultatet tilbake opp gjennom alle kallene.

Fibonacci-tallene

Fibonacci-tallrekken er et berømt eksempel som passer naturlig til rekursjon. Hvert tall er summen av de to foregående:

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 et viktig problem: den er svært ineffektiv! For å beregne fibonacci(5) kalles fibonacci(3) to ganger, fibonacci(2) tre ganger, og så videre. Antall kall vokser eksponentielt. fibonacci(40) kan ta flere sekunder, og fibonacci(100) ville ta lengre enn universets levetid!

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 beregner fibonacci(50) umiddelbart, mens den rekursive versjonen ville bruke ufattelig lang tid. Dette illustrerer at rekursjon ikke alltid er den beste løsningen, selv om den er elegant.

Forstå Big O-notasjon

Big O-notasjon gir oss et språk for å snakke om hvor raskt en algoritme vokser i tid eller plass når inndataen blir større. Vi bryr oss ikke om nøyaktig antall operasjoner, men om veksthastigheten.

De vanligste kompleksitetsklassene (fra raskest til tregest):

Big O i praksis: hvordan bestemme kompleksiteten

O(1) – Konstant tid:
Operasjonen tar like lang tid uansett størrelsen 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:
Tiden vokser proporsjonalt med inndataen. Én løkke gjennom n elementer.

# 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østede løkker der begge går gjennom n elementer.

# 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 dataene i hvert 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

Tommelfingerregler:
- Én enkel løkke gjennom n elementer → O(n)
- To nøstede løkker gjennom n elementer → O(n²)
- Tre nøstede løkker → O(n³)
- Halvering i hvert steg → O(log n)
- Én løkke med halvering i hvert steg → O(n log n)

Oppsummering

I dette kapittelet har du lært:

- Rekursjon: en funksjon som kaller seg selv.
- Basistilfelle og rekursivt tilfelle: stopp og gjentakelse.
- Eksempler: fakultet, Fibonacci og rekursivt binærsøk.
- Big O-notasjon: beskriver algoritmens ressursbruk.
- Vanlige kompleksiteter: O(1), O(log n), O(n) og O(n^2).

Noekkelbegreper