3.5 Rekursjon og algoritmekompleksitet

Speilet som speiler et speil

Står du foran et speil som reflekterer et annet speil, ser du deg selv, som ser deg selv, som ser deg selv – i en tilsynelatende uendelig rekke. Det er en god metafor for rekursjon: noe som refererer til seg selv.

I programmering er rekursjon en teknikk der en funksjon løser et problem ved å kalle seg selv med et enklere delproblem. Hver rekursiv funksjon har to deler: et basistilfelle som stopper rekursjonen og gir et direkte svar, og et rekursivt tilfelle der funksjonen kaller seg selv med et mindre problem. Glemmer du basistilfellet, kaller funksjonen seg selv i det uendelige og krasjer med en «stack overflow»-feil.

Det klassiske eksempelet er fakultet. 5! = 5 × 4 × 3 × 2 × 1 = 120, og det kan defineres rekursivt: n! = n × (n-1)!, med 0! = 1 som basistilfelle.

def fakultet(n):
    if n == 0:        # basistilfelle
        return 1
    return n * fakultet(n - 1)  # rekursivt tilfelle

Kaller du fakultet(4), kaller funksjonen seg selv med stadig mindre n til den treffer fakultet(0), som gir 1. Deretter «rulles» resultatet tilbake oppover: 1 × 1, så × 2, så × 3, så × 4 = 24. Samme mønster gjelder en rekursiv sum: sum(n) = n + sum(n-1) med sum(0) = 0, som for n = 100 gir 5050.

Når elegant ikke betyr effektivt

Fibonacci-tallrekken passer naturlig til rekursjon. Hvert tall er summen av de to foregående: 0, 1, 1, 2, 3, 5, 8, 13, ... Definisjonen er fib(n) = fib(n-1) + fib(n-2), med fib(0) = 0 og fib(1) = 1 som basistilfeller. Den rekursive koden er kort og vakker – men den har et alvorlig problem: den er hopløst ineffektiv. For å regne ut fibonacci(5) kalles fibonacci(2) flere ganger, og antall kall vokser eksponentielt. fibonacci(40) kan ta flere sekunder, og fibonacci(100) ville ta lenger enn universets levetid.

En iterativ versjon med en enkel løkke beregner derimot fibonacci(50) umiddelbart. Lærdommen er viktig: rekursjon er elegant, men ikke alltid den beste løsningen. Du må vurdere effektivitet.

Noen ganger passer rekursjon perfekt likevel, fordi den speiler algoritmen direkte. Binærsøk er et godt eksempel: halvér, velg riktig side, gjenta. En rekursiv variant kaller seg selv på den halvdelen som er igjen:

def binaersok_rekursiv(liste, sokeord, lav, hoy):
    if lav > hoy:
        return -1
    midt = (lav + hoy) // 2
    if liste[midt] == sokeord:
        return midt
    if liste[midt] < sokeord:
        return binaersok_rekursiv(liste, sokeord, midt + 1, hoy)
    else:
        return binaersok_rekursiv(liste, sokeord, lav, midt - 1)

Hvert kall halverer søkeområdet, og koden gjenspeiler nettopp den intuitive «halvér og gjenta»-tankegangen fra telefonkatalogen.

Big O – et språk for fart

Vi har sett at algoritmer har ulik ytelse. Big O-notasjon gir oss et presist språk for dette. Den beskriver hvordan ressursbruken (tid eller minne) vokser når inndatastørrelsen n øker, og ignorerer konstante faktorer og lavere ledd. En algoritme som gjør 3n² + 5n + 10 operasjoner har kompleksitet O(n²), fordi n²-leddet dominerer for store n.

De vanligste klassene, fra raskest til tregest: O(1) (konstant – like rask uansett størrelse, som å hente et listeelement via indeks), O(log n) (logaritmisk – binærsøk), O(n) (lineær – lineært søk eller én løkke gjennom n), O(n log n) (Pythons innebygde sortering), O(n²) (kvadratisk – nøstede løkker, som boblesortering) og O(2ⁿ) (eksponentiell – naiv Fibonacci). Noen tommelfingerregler: én løkke gjennom n gir O(n), to nøstede løkker gir O(n²), og halvering hvert steg gir O(log n).

Hvorfor betyr dette noe? Tenk deg en million elementer. En O(n)-algoritme bruker millisekunder, en O(n log n) bruker sekunder, men en O(n²) bruker en million millioner operasjoner – timer eller dager. Måler du tiden på boblesortering (O(n²)) mot Pythons sorted() (O(n log n)), ser du det tydelig: når n dobles, bruker boblesortering rundt fire ganger så lang tid, mens sorted() knapt merker det. For 10 000 elementer kan den innebygde sorteringen være tusenvis av ganger raskere. Forskjellen mellom O(n) og O(n²) kan være forskjellen på et program som kjører på et sekund og ett som tar en uke.

Oppsummering

Rekursjon er når en funksjon kaller seg selv, og den trenger alltid et basistilfelle som stopper og et rekursivt tilfelle som forenkler problemet. Fakultet, sum og binærsøk passer naturlig, men Fibonacci minnet oss om at rekursjon kan være elegant og likevel hopløst ineffektiv (O(2ⁿ)) – noen ganger er en løkke mye bedre.

Big O-notasjon gir oss et felles språk for effektivitet, fra O(1) og O(log n) via O(n) og O(n log n) til O(n²) og O(2ⁿ). Reglene er enkle: én løkke gir O(n), nøstede løkker O(n²), og halvering O(log n). Å forstå kompleksitet er ikke akademisk pirk – det kan avgjøre om programmet ditt kjører på et sekund eller en uke.