5.2 Rekursjon — spore og skrive

En rekursiv funksjon er en funksjon som kaller seg selv med et mindre argument, og som har en utgang der den svarer direkte uten å kalle seg selv igjen.

Den er ikke magi og ikke en ny språkkonstruksjon: hvert kall er et helt vanlig funksjonskall, med sine egne lokale variabler, som venter på at svaret fra det neste kallet skal komme tilbake.

Rekursjon løser problemer som kan sies slik: «svaret for n er noe enkelt gjort med svaret for n - 1».

Det tilfellet funksjonen kan svare på direkte, uten å kalle seg selv. På engelsk kalles det base case, og det ordet møter du i mye kodelitteratur.

Grunntilfellet står alltid først i funksjonen, som en if med en return. Uten det får du en funksjon som kaller seg selv i det uendelige, og Python stopper den til slutt med en RecursionError.

Et godt grunntilfelle dekker også de rare inndataene: fakultet(0) skal gi 1, ikke krasje, og derfor skrives testen if n <= 1, ikke if n == 1.

Linja der funksjonen kaller seg selv med et mindre argument, og gjør noe med svaret som kommer tilbake.

return n * fakultet(n - 1) er et rekursivt steg: kallet gjøres først, og multiplikasjonen skjer når svaret kommer tilbake.

To ting må være på plass, ellers virker ikke funksjonen: argumentet må faktisk bli mindre, og resultatet av kallet må brukes. Glemmer du return foran kallet, regner funksjonen riktig og returnerer None likevel.

Hvert rekursivt kall må flytte argumentet nærmere grunntilfellet, ellers stopper funksjonen aldri.

Rekka av kall som er startet, men ikke ferdige. Hvert kall har sine egne lokale variabler, og de ligger «oppå hverandre» — det siste startede kallet blir det første som blir ferdig.

På papiret tegner du den som en trapp nedover, med argumentet på hver linje. Dybden er antall linjer, og den er ofte det oppgaven egentlig spør om.

Andre halvdel av sporingen: når grunntilfellet har svart, regnes hvert ventende kall ferdig, nedenfra og opp.

Det er her rekkefølgen ofte går galt. fakultet(4) er ikke $4 \times 3$; det er 4 ganger svaret fra fakultet(3), som igjen er 3 ganger svaret fra fakultet(2). Skriv hvert ledd på egen linje med tallverdien innsatt, så ser du kjeden.

Resultatet av et rekursivt kall forsvinner hvis du ikke gjør noe med det. fakultet(n - 1) alene på en linje regner ut hele kjeden og kaster svaret.

Derfor har hvert rekursivt steg i denne boka return foran seg. Glemmer du det, returnerer funksjonen None, og feilen er stum: koden krasjer ikke, den svarer bare None — som er nøyaktig det en sporingsoppgave er ute etter å teste.

Produktet av alle heltallene opp til n: $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.

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

Grunntilfellet er n <= 1 og gir 1. Vokser fort: fakultet(10) er over tre millioner. Blandes ofte med potens på eksamen — fakultet ganger med et synkende tall, potens ganger med det samme tallet hver gang.

Det største tallet som deler begge tallene. Euklids observasjon er at største felles divisor av a og b er den samme som av b og resten a % b.

def sfd(a, b):
    if b == 0:
        return a
    return sfd(b, a % b)

Grunntilfellet er b == 0, og svaret er da a. På eksamen står funksjonen ofte under navnet gcd (engelsk for greatest common divisor) eller med et intetsigende navn som myst, og oppgaven spør hva den regner ut.

Rekka 0, 1, 1, 2, 3, 5, 8, 13 …, der hvert tall er summen av de to foregående.

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

To grunntilfeller i ett: fib(0) er 0 og fib(1) er 1, og begge dekkes av if n <= 1: return n. Dette er den eneste klassikeren med to rekursive kall i samme uttrykk, og derfor den mest krevende å spore.

Summen av sifrene i et positivt heltall: tverrsummen av 915 er 9 + 1 + 5 = 15.

def tverrsum(n):
    if n == 0:
        return 0
    return n % 10 + tverrsum(n // 10)

Bygger på at n % 10 er siste siffer og n // 10 er tallet uten det. Grunntilfellet er n == 0, som er det du sitter igjen med når alle sifrene er brukt opp.

def potens(g, e):
    if e == 0:
        return 1
    return g * potens(g, e - 1)

Grunntilfellet er e == 0 og gir 1, fordi ethvert tall opphøyd i null er 1. Merk at det er eksponenten som telles ned, mens grunntallet står stille — det er forskjellen fra fakultet, der tallet som ganges selv blir mindre.

Når et rekursivt steg inneholder to kall, som fib(n - 1) + fib(n - 2), blir sporingen et tre i stedet for en trapp.

Metoden er den samme, men du må regne den ene grenen helt ferdig før du starter på den andre, og skrive delsvarene ned underveis. På papiret lønner det seg å regne små verdier først og bygge oppover: fib(0), fib(1), fib(2) … til du er framme.

Det er også grunnen til at rekursiv Fibonacci er treg: fib(5) gjør 15 kall, og de fleste av dem regner ut det samme om igjen.

Python setter en øvre grense for hvor dypt kall kan stables — som regel rundt tusen nivåer. Nås grensen, avbrytes programmet med meldingen RecursionError: maximum recursion depth exceeded.

Det er et stumt symptom, ikke en diagnose: feilen ligger alltid enten i grunntilfellet eller i at argumentet ikke blir mindre. På en sporingsoppgave er «programmet stopper aldri / gir RecursionError» et fullgodt svar når koden faktisk har den feilen.

Antall nivåer i kall-stakken før grunntilfellet nås. For fakultet(5) er dybden 5; for tverrsum(4072) er den 5 (fire sifre pluss grunntilfellet).

Dybden er et vanlig oppfølgingsspørsmål på eksamen: «hvor mange ganger kalles funksjonen?». Svaret leser du rett av kall-stakken du allerede har tegnet — og husk å telle med kallet som treffer grunntilfellet.

Alt du kan gjøre rekursivt, kan du gjøre med en løkke, og omvendt. Valget er et spørsmål om hva oppgaven ber om, og hva som blir lesbart.

Det samme mønsteret virker på sekvenser: det første elementet behandles direkte, og resten sendes videre som x[1:].

def total(x):
    if len(x) == 0:
        return 0
    return x[0] + total(x[1:])

Grunntilfellet er den tomme sekvensen, og x[1:] er «alt unntatt det første» — et utsnitt du kjenner fra kap. 3.1. Merk at x[1:] lager en ny liste for hvert kall; det er greit på eksamensstørrelser, men er grunnen til at en løkke er raskere i praksis.