3.4 Grafalgoritmer og trær

Dukker inni dukker

Rekursjon er en teknikk der en funksjon kaller seg selv for å løse et problem. Det høres rart ut, men det er en av de mest elegante idéene i informatikk. Tenk på russiske matryoshka-dukker: du åpner en dukke og finner en mindre inni, og fortsetter til du når den minste. Den minste dukken er basetilfellet – punktet der du stopper.

Enhver rekursiv funksjon trenger nettopp to deler. Basetilfellet er betingelsen som stopper rekursjonen; uten det kaller funksjonen seg selv i det uendelige. Det rekursive tilfellet er der funksjonen kaller seg selv med et forenklet problem som beveger seg mot basetilfellet. Det avgjørende er at hvert kall må bringe oss nærmere bunnen.

Det klassiske eksempelet er fakultet. Matematisk er n! = n × (n−1)!, og basetilfellet er at 0! = 1. I kode:

def fakultet(n):
    if n == 0 or n == 1:
        return 1
    return n * fakultet(n - 1)

Sporer vi fakultet(4), blir det 4 * fakultet(3), som blir 4 * (3 * fakultet(2)), helt ned til fakultet(1) som returnerer 1 – og så ruller alt tilbake til 24. Den rekursive versjonen ligner den matematiske definisjonen som en hånd i hanske.

Kall-stakken og når den sprenger

For å forstå rekursjon må du forstå kall-stakken. Når en funksjon kalles, legges den på en stakk i minnet, og når den returnerer, fjernes den. I fakultet(4) stables fire kall opp – fakultet(4), fakultet(3), fakultet(2), fakultet(1) – og alle venter til det innerste returnerer 1. Deretter løses de opp ett for ett, nedenfra og opp. Rekursive funksjoner bruker altså O(n) minne for stakken, der n er rekursjonsdybden.

Her ligger en fare: stack overflow. Hvis rekursjonen aldri når basetilfellet, vokser stakken til den sprenger minnegrensen. Python har en standardgrense på rundt 1000 kall, og en funksjon som def uendelig(n): return uendelig(n+1) gir umiddelbart RecursionError. Selv et korrekt fakultet krasjer rundt fakultet(1500). Løsningene er tre: skriv om til en iterativ løkke, som tåler enorme tall uten dybdeproblem; bruk memoisering for å redusere dybden; eller juster grensen forsiktig med sys.setrecursionlimit. En nyttig huskeregel: kan dybden bli over rundt 500, bør du vurdere en iterativ løsning. En relatert idé er halerekursjon, der det rekursive kallet er den aller siste operasjonen. Noen språk som Scheme og Haskell optimaliserer dette til en løkke – men det gjør ikke Python.

Fibonaccis dobbeltarbeid og strenger som snus

Rekursjon kan også gå galt på en mer subtil måte. Fibonacci er definert rekursivt – F(n) = F(n−1) + F(n−2) – og den naive implementasjonen ser elegant ut:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Men den gjør enormt mye dobbeltarbeid: fib(5) regner ut fib(2) tre ganger og fib(1) fem ganger. Tidskompleksiteten er O(2ⁿ), og fib(40) kan ta nær et minutt. Løsningen er memoisering – å lagre allerede beregnede svar i en cache, gjerne med dekoratoren @lru_cache – som gir O(n). Den iterative versjonen er like rask og bruker bare O(1) minne. Lærdommen: rekursjon med overlappende delproblemer trenger memoisering for å være effektiv.

Rekursjon er likevel et flott verktøy for å tenke om problemer. En kort funksjon kan snu en streng: reverser(s) returnerer reverser(s[1:]) + s[0], slik at "hei" blir "ieh". Mange listeoperasjoner – sum, finn største, tell forekomster – kan også skrives rekursivt. Men vær oppmerksom: disse er ikke mer effektive enn løkker, og liste[1:] lager en ny liste for hvert kall, noe som koster ekstra. En liten advarsel om vanlige feil: i en funksjon som summerer sifrene i et tall må du bruke heltallsdivisjon //, ikke /. Med / blir resultatet et desimaltall som aldri treffer 0, og rekursjonen stopper aldri.

Rekursjon eller iterasjon – og Hanoi

Alle rekursive løsninger kan skrives iterativt, og omvendt. Valget handler om lesbarhet og problemets natur. Rekursjon vinner når problemet naturlig deler seg i delproblemer (del-og-hersk), ved trestrukturer og grafer, ved backtracking, og når den rekursive koden rett og slett er klarere. Iterasjon vinner ved enkle gjentakelser, når ytelse er kritisk, og når dybden kan bli stor.

Noen eksempler gjør valget tydelig. Å telle ned fra n eller skrive ut tallene 1 til n er naturlig iterativt – en for-løkke er klart enklest. Å beregne gjennomsnittet av en liste er også iterativt, en lineær gjennomgang. Men å gå gjennom en filsystemstruktur er naturlig rekursivt, fordi et filsystem er et tre der hver mappe kan inneholde mapper. Og merge sort er rekursivt, fordi del-og-hersk uttrykker algoritmen elegant.

Det kanskje vakreste rekursive problemet er Tårnet i Hanoi. Du har tre pinner og n disker i ulik størrelse, alle på pinne A, og skal flytte dem til pinne C uten å legge en større disk på en mindre. Løsningen er ren rekursjon: flytt n−1 disker til hjelpepinnen, flytt den største disken til målet, og flytt så n−1 disker fra hjelpepinnen til målet. Antall trekk er 2ⁿ − 1 – for 3 disker er det 7, for 10 disker hele 1023. Et lite problem med eksponentiell vekst, løst på noen få linjer.

Oppsummering

Rekursjon er som matryoshka-dukker: en funksjon kaller seg selv til den når basetilfellet. Hver rekursiv funksjon trenger et basetilfelle som stopper, og et rekursivt tilfelle som forenkler problemet og nærmer seg bunnen. Klassiske eksempler er fakultet, Fibonacci, tretraversering, merge sort og binærsøk.

Vi så hvordan kall-stakken holder alle ventende kall i minnet (O(n)), og hvordan for dyp rekursjon gir stack overflow – løst ved iterasjon, memoisering eller justert grense. Naiv Fibonacci er O(2ⁿ) på grunn av dobbeltarbeid, men memoisering redder den. Valget mellom rekursjon og iterasjon handler om problemets natur: rekursjon for trær og del-og-hersk, iterasjon for lineære gjennomganger. Og Tårnet i Hanoi viste at noen få rekursive linjer kan løse et problem som krever 2ⁿ − 1 trekk. I neste kapittel ser vi på databehandling og filhåndtering.