1.7 Rekursive sammenhenger og programmering

Når datamaskinen tar trappen

Husker du skillet mellom heisen og trappen fra kapittel 1.1 — eksplisitte formler som tar oss rett til svaret, og rekursive som går steg for steg? For en menneskehjerne er trappen slitsom: å regne ut Fibonacci-tall nummer femti for hånd er en hel ettermiddags arbeid. For en datamaskin er det mikrosekunder.

Programmering og rekursjon er som skapt for hverandre. En rekursiv definisjon sier «neste verdi lages av de forrige» — og det er nøyaktig det en løkke i Python gjør, runde etter runde. Enda mer slående: et program kan inneholde en funksjon som kaller seg selv, en slags matematisk speilkabinett som likevel gir presise svar. I dette kapittelet bruker vi Python til å generere følger, beregne Fibonacci-tall og fakulteter, og simulere sprettballen fra kapittel 1.5 — og du vil se at noen få linjer kode kan erstatte timevis med håndregning.

Følger som løkker

En rekursiv definisjon består av to deler: startverdier (basistilfellet) og en regel $a_n = f(a_{n-1}, a_{n-2}, \ldots)$ som lager nye ledd av gamle. I Python blir dette en variabel som oppdateres i en løkke.

Ta den aritmetiske følgen $a_n = 3 + 5(n-1)$, som rekursivt er $a_1 = 3$ og $a_{n+1} = a_n + 5$:

a = 3  # startverdi
for n in range(1, 11):
    print(f"a_{n} = {a}")
    a = a + 5  # regelen: neste ledd = forrige + 5

Programmet skriver ut $a_1 = 3$, $a_2 = 8$, $a_3 = 13$ og videre til $a_{10} = 48$. Linjen a = a + 5 er den rekursive regelen, oversatt til kode.

Fibonacci-følgen trenger to startverdier, og da er en liste praktisk:

fib = [1, 1]
for i in range(2, 20):
    fib.append(fib[i-1] + fib[i-2])

Her bygger fib[i-1] + fib[i-2] neste tall av de to forrige — nøyaktig $F_n = F_{n-1} + F_{n-2}$ — og etter løkken vet vi at $F_{20} = 6765$. Det som tok middelalderens regnemestere dager, tar maskinen et øyeblikk.

Funksjoner som kaller seg selv

Løkker er én måte å programmere rekursjon på. Den andre er mer forbløffende: en rekursiv funksjon kaller seg selv. Ta fakultet, definert ved $n! = n \cdot (n-1)!$ med $0! = 1! = 1$:

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

Kaller du fakultet(4), regner funksjonen $4 \cdot \texttt{fakultet}(3)$, som regner $3 \cdot \texttt{fakultet}(2)$, som regner $2 \cdot \texttt{fakultet}(1)$ — og der stopper det, for basistilfellet if n <= 1: return 1 slår inn. Svarene ruller så tilbake: $2 \cdot 1 = 2$, $3 \cdot 2 = 6$, $4 \cdot 6 = 24$. Uten basistilfellet ville funksjonen kalt seg selv i evighet — rekursjonens svar på en dominorekke uten ende.

Rekursjon i kode er også et utforskningsverktøy. Husker du sprettballen som spratt til $80\,\%$ av forrige høyde? Vi kan simulere den:

h = 10
total = h
while h > 0.001:
    h = h * 0.8
    total += 2 * h
print(f"Total strekning: {total:.2f} m")

Programmet svarer $90{,}00$ meter — og formelen for uendelige geometriske rekker gir $\displaystyle 10 + 2 \cdot \frac{8}{1 - 0{,}8} = 90$ meter eksakt. Simulering og teori bekrefter hverandre. Slik bruker matematikere programmering i praksis: koden gir hypoteser og kontrollregning, teorien gir visshet.

Oppsummering: matematikk som kjører

I dette kapittelet møttes to verdener: følgenes rekursive definisjoner og programmeringens løkker og funksjoner. En rekursiv sammenheng — startverdier pluss en regel som lager neste ledd av de forrige — oversettes direkte til kode, enten som en løkke der en variabel oppdateres (a = a + 5 for aritmetiske følger, fib[i-1] + fib[i-2] for Fibonacci) eller som en rekursiv funksjon som kaller seg selv, slik fakultet(n) beregner $n! = n \cdot (n-1)!$. Den ufravikelige regelen er basistilfellet: hver rekursjon trenger en stoppbetingelse, akkurat som hvert induksjonsbevis trenger et basissteg.

Mønstrene du nå kan programmere, er kapittelets fire gjengangere: aritmetisk $a_n = a_{n-1} + d$, geometrisk $a_n = k \cdot a_{n-1}$, Fibonacci $F_n = F_{n-1} + F_{n-2}$ og fakultet $n! = n \cdot (n-1)!$. Og sprettball-simuleringen viste arbeidsdelingen mellom kode og teori: programmet ga $90{,}00$ meter, rekkeformelen ga $90$ eksakt. Med følger, rekker, konvergens, induksjon og programmering i verktøykassa er du klar for neste store tema i R2 — integralregningen.