Rekursjon, sortering og søk

En funksjon som kaller seg selv

Tenk deg at du skal regne ut produktet 4 · 3 · 2 · 1. Du kan løse det med en løkke, men det finnes en mer elegant innfallsvinkel: legg merke til at 4! (fire fakultet) er det samme som 4 · 3!, og at 3! er 3 · 2!, og slik fortsetter det. Hvert problem er en mindre versjon av seg selv. Det er nettopp dette rekursjon er — en funksjon som løser et problem ved å kalle seg selv på et mindre delproblem.

Her er fakultet skrevet rekursivt:

1def faktoriell(n):2    if n <= 1:        # basistilfelle3        return 14    return n * faktoriell(n - 1)   # rekursivt tilfelle5 6print(faktoriell(4))   # 24

Les funksjonen ovenfra. Hvis n er 0 eller 1, returnerer vi 1 med en gang — vi kaller ikke oss selv. Ellers returnerer vi n * faktoriell(n - 1). Hver gang vi kaller faktoriell med et mindre tall, helt til vi treffer det punktet der vi slutter å kalle videre.

Det punktet har et navn. Den grenen som returnerer et svar uten å kalle funksjonen på nytt, heter basistilfelle. Uten et basistilfelle ville funksjonen kalle seg selv i det uendelige — Python stopper deg riktignok med en RecursionError, men det er en bug, ikke en løsning. Den andre grenen, der funksjonen kaller seg selv på et mindre problem, kaller vi det rekursive tilfellet. Hver rekursjon må bevege seg mot basistilfellet, ellers stopper det aldri.

Hva skjer egentlig i maskinen

Når faktoriell(3) kjører, kaller den faktoriell(2), som kaller faktoriell(1). På det tidspunktet er det tre kall som er startet, men ingen av dem er ferdige — de venter alle på svaret fra kallet de selv gjorde. Maskinen holder styr på dette med en kall-stack: en stabel der hvert ufullførte funksjonskall får sin egen ramme med sine egne lokale variabler.

Figuren viser stacken på sitt dypeste, akkurat når faktoriell(1) er nådd. Det øverste kallet er det nyeste. Når faktoriell(1) returnerer 1, fjernes rammen, og faktoriell(2) kan fullføre sin 2 * 1 og returnere 2. Så fullfører faktoriell(3) sin 3 * 2 og returnerer 6. Stacken bygges opp på vei ned i rekursjonen og rives ned igjen på vei tilbake. Å forstå denne opp-og-ned-bevegelsen er nøkkelen til å lese rekursiv kode: et kall er ikke ferdig før alle kallene det selv startet er ferdige.

Rekursjon koster litt. Hver ramme tar plass i minnet, og en altfor dyp rekursjon kan fylle opp stacken. For fakultet og lignende problemer er en løkke ofte raskere og bruker mindre minne. Men noen problemer — særlig de som handler om trær, kataloger inne i kataloger, eller å bryte ned en struktur i mindre versjoner av samme struktur — blir mye kortere og klarere med rekursjon enn med løkker. Velg verktøyet etter problemet.

Den samme idéen med en løkke

For å se hva rekursjonen egentlig gjør, kan det hjelpe å skrive fakultet på den andre måten — med en løkke som bygger opp svaret skritt for skritt:

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

De to gir nøyaktig samme svar. Forskjellen er hvordan de tenker. Den rekursive versjonen sier «svaret er n ganger svaret på det litt mindre problemet», og lar maskinen holde rede på rekkefølgen via stacken. Løkkeversjonen sier «start på 1, og gang inn ett tall om gangen». Begge er gyldige; ofte er løkken enklere å resonnere om når problemet allerede er en rett fremover-opptelling. Rekursjon vinner når problemet i seg selv har en oppdelt struktur, slik binærsøk og flettesortering har — der deler du naturlig i to og løser hver del på samme måte.

Det er verdt å peke på en typisk feil. Hvis du glemmer å bevege deg mot basistilfellet — for eksempel skriver return n * faktoriell(n) i stedet for faktoriell(n - 1) — får du uendelig rekursjon. Stacken vokser og vokser til Python gir opp med en RecursionError. Når du leser eller skriver rekursjon, sjekk alltid to ting: finnes det et basistilfelle, og bringer hvert rekursivt kall deg nærmere det?

Å lete i en sortert liste

Tenk deg en ordbok med tusenvis av ord. Du leter aldri ved å lese fra første side og bla videre ett ord om gangen. Du slår opp omtrent midt i boka, ser om ordet du leter etter kommer før eller etter, og hopper til riktig halvdel. Så gjentar du. Hvert oppslag halverer mengden du må lete i.

Dette er binærsøk, og det forutsetter én ting: at lista allerede er sortert. Her er algoritmen i pseudokode:

1binaersok(liste, mål):2    lav  = 03    hoy  = lengde(liste) - 14    så lenge lav <= hoy:5        midt = (lav + hoy) // 26        hvis liste[midt] == mål:7            returner midt          # funnet8        ellers hvis liste[midt] < mål:9            lav = midt + 1         # let i høyre halvdel10        ellers:11            hoy = midt - 1         # let i venstre halvdel12    returner -1                    # ikke funnet

Figuren viser en sortert liste der vi leter etter tallet 23. Vi starter med to grenser, lav og hoy, som omslutter hele lista. Vi ser på elementet i midten. Er det for lite, vet vi at svaret må ligge til høyre, så vi flytter lav forbi midten. Er det for stort, flytter vi hoy. Slik klemmer vi søkeområdet sammen fra begge sider til vi enten finner tallet eller står igjen med et tomt område.

Kraften ligger i halveringen. Et lineært søk gjennom en million elementer kan i verste fall kreve en million sammenligninger. Binærsøk klarer seg med rundt 20, fordi hver runde halverer. Men igjen: lista må være sortert først, ellers gir midt-sammenligningen ingen mening.

Hvor mye arbeid kreves

For å snakke presist om hvor raskt en algoritme er, bruker vi o-notasjon (store-O). Den beskriver hvordan arbeidsmengden vokser når datamengden vokser, og ignorerer konstanter og detaljer. Et lineært søk er O(n): dobler du lista, dobler du i verste fall arbeidet. Binærsøk er O(log n): dobler du lista, øker arbeidet bare med ett ekstra trinn. Den forskjellen er enorm for store datamengder.

sortering er den andre store byggeklossen her. For at binærsøk skal virke må noen ha sortert lista først. Enkle sorteringsmetoder som boblesortering sammenligner naboer om og om igjen og er O(n²) — arbeidet firedobles når lista dobles, så de blir ubrukelige for store mengder. Smartere metoder som flettesortering deler lista i to, sorterer hver halvdel rekursivt og fletter dem sammen, og oppnår O(n log n). I praksis sorterer du sjelden selv: Python har sorted() og list.sort(), som bruker en svært effektiv innebygd algoritme. Det viktige for deg er å vite at sortering ikke er gratis, og at valg av algoritme avgjør om et program er ferdig på et blunk eller henger i timevis.

For å gjøre tallene konkrete: tenk deg en liste med en million elementer. Et lineært søk gjør i verste fall en million sammenligninger. Binærsøk gjør rundt 20, fordi 2 opphøyd i 20 allerede er over en million — hver halvering klipper bort halvparten av det som er igjen. Det er denne logaritmiske veksten som gjør binærsøk så kraftig. Men prisen er at lista må holdes sortert. Hvis du bare skal lete én gang i en usortert liste, lønner det seg ikke å sortere først — da er et lineært søk raskere totalt sett. Skal du derimot lete mange ganger i den samme lista, betaler sorteringen seg raskt tilbake, fordi hvert påfølgende søk blir så billig. Å vurdere slike avveininger — hva koster det å forberede dataene, og hvor mange ganger skal jeg bruke dem etterpå — er en stor del av det å tenke som en programmerer.

Et siste poeng om sortering og søk sammen: når Python sorterer en liste av tall, sammenligner det dem numerisk. Sorterer det en liste av strenger, sammenligner det dem alfabetisk (egentlig etter tegnenes tallkoder). Binærsøk fungerer på begge — så lenge elementene har en veldefinert rekkefølge og lista er sortert etter nettopp den rekkefølgen, kan du halvere deg fram til svaret.

Hvorfor dette teller ekstra i TDT4109

Rekursjon, sortering og søk er pensum for alle, men de vektlegges ekstra i TDT4109. Der forventes det at du både kan lese og skrive rekursive funksjoner, forklare hva kall-stacken gjør under en rekursjon, og resonnere om kjøretid med O-notasjon. Tar du TDT4109, bør du øve på å spore en rekursjon for hånd — tegn stacken ramme for ramme slik figuren over gjør — og på å sammenligne algoritmer ut fra hvordan arbeidet vokser, ikke ut fra hvor raskt de føles på et lite eksempel.

Tre ting å ta med videre. Rekursjon løser et problem ved å redusere det til en mindre versjon av seg selv, og trenger alltid et basistilfelle. Binærsøk halverer søkeområdet hver runde, men krever en sortert liste. Og O-notasjon lar deg sammenligne algoritmer ved å se på hvordan de skalerer, ikke hvor kjappe de er på små eksempler.