Rekursjon

I artikkelen om å lagre funksjoner i moduler finner  vi funksjonen fakultet(), som beregner fakultetet til et tall, n!

def fakultet(n):
    """Beregner n!"""
    fakt = 1
    for m in range(2, n + 1):
        fakt *= m
    return fakt

Funksjonen er basert på ei løkke der tallene fra 1 til n blir multiplisert. Nå skal vi skrive den på en annen måte.

Hvis skal finne fakultetet til et tall, n!, og allerede kjenner fakultetet til det forrige tallet, (n − 1)!, trenger vi jo ikke starte på 1 og multiplisere oss oppover, alt vi behøver gjøre er å multiplisere det nye tallet med fakultetet vi kjenner: n! = n · (n − 1)! Hvis vi for eksempel vet at 4! = 24, blir 5! = 5 · 4! = 5 · 24 = 120.

Dette mønsteret gjelder for alle n > 0, for n = 0 er det definert at 0! = 1. Vi kan angi det slik:

$n!\, =\, \left\{ {\begin{array}{l}
1\, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \,
n\, =\, 0 \\
\, \\
n\cdot \left( n-1 \right)!\, \, \, \, \, n>0\, \\
\end{array}} \right.$

Så spør vi oss om det er mulig å programmerere dette mønsteret direkte i en funksjon, slik:

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

Svaret er ja. I artikkelen om funksjoner som kaller funksjoner ser vi at funksjoner kan kalle andre funksjoner, her ser vi at funksjoner også kan kalle seg selv. Dette kalles rekursjon.

Vi har nå skrevet funksjonen fakultet() på to måter. Én der beregningen foregår ved hjelp av ei løkke, noe som kalles en iterativ metode, og én der beregningen foregår ved at funksjonen kaller seg selv, noe vi kaller en rekursiv metode.

Rekursjon fungerer fordi variable definert inni en funksjon er lokale i funksjonen, slik vi beskriver i artikkelen om lokale og globale variabler. Hadde variabelen n i fakultet() vært global, ville rekursjon ikke fungert.

La oss som en illustrasjon tenke oss at vi i hovedprogrammet skriver kode som kaller opp fakultet() med argument 2. Siden vi kommer til å ha flere utgaver av n og fakultet(), bruker vi fargekoder for å holde dem fra hverandre.

Vi skriver altså først:

print(fakultet(2))

Da blir verdien 2 overført til parameteren n i fakultet().

Siden n ikke er 0, blir kodeblokka tilhørende else utført:

return n * fakultet(n-1)

Her kaller fakultet() opp seg selv med n − 1 = 2 − 1 = 1 som argument. Da blir verdien 1 overført til parameteren n i fakultet().

Siden n ikke er 0, blir kodeblokka tilhørende else utført:

return n * fakultet(n-1)

Her kaller fakultet() opp seg selv med n − 1 = 1 − 1 = 0 som argument. Da blir verdien 0 overført til parameteren n i fakultet().

(Vi har nå tre utgaver av fakultet() aktive, med henholdsvis n = 2, n = 1 og n = 0.)

Siden n er 0, blir kodeblokka tilhørende if utført:

return 1

Denne returverdien går tilbake til der fakultet() ble kalt opp:

return n * fakultet(n-1)

Her er n = 1 og returverdien fra kallet fakultet(n-1) er 1, så dette blir 1 · 1 = 1.

Denne returverdien går tilbake til der fakultet() ble kalt opp:

return n * fakultet(n-1)

Her er n = 2 og returverdien fra kallet fakultet(n-1) er 1, så dette blir 2 · 1 = 2.

Denne returverdien går tilbake til der fakultet() ble kalt opp:

print(fakultet(2))

Og vi får skrevet ut 2.

I et rekursivt system genereres en kjede av funksjonskall. Men det må være en grunnverdi der det ikke lenger genereres nye kall. I fakultetsfunksjonen er det n = 0, der vi vet at funksjonen skal returnere 1 og ikke trenger flere kall. Mangler vi en grunnverdi, får vi teoretisk en rekursjonskjede uten ende. I praksis vil Python etter om lag 1000 rekursive kall gi feilmeldingen "RecursionError: maximum recursion depth exceeded".

Python Tutor, er et supert verktøy til å utforske rekursjon. I bildet under har vi lagt inn den rekursive funksjonen fakultet(), og kalt den opp med argument 2 fra print(). Så har vi klikket oss fram til dit fakultet() er blitt kalt opp med argument 0, og har fått returverdi 1.

Vi ser at vi har funksjonen fakultet() representert som tre bokser, der hver av boksene utgjør et ledd i kjeden av rekursjonskall, med n lik henholdsvis 2, 1 og 0. Ved neste klikk returnerer siste ledd i kjeden.

Nå er det siste leddet i rekursjonskjeden borte, og returverdien i leddet før er beregnet som 1 · 1 = 1.

Neste klikk gir enda en retur.

Nå er det enda et ledd i rekursjonskjeden borte, og returverdien i leddet før er beregnet som 2 · 1 = 2.

Neste klikk gir siste retur.

Nå er tallet 2 returnert til print() og skrevet ut.

Siden fakultet() returnerer hvis n = 0, kommer vi bare videre i funksjonen hvis n ≠ 0, så else er egentlig overflødig, og vi kan skrive koden slik:

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

Logikken blir imidlertid tydeligere hvis vi har med else.

Oppgave 1:

Summen av de n første leddene av den harmoniske rekka ${\large\frac{1}{1}} + {\large\frac{1}{2}} + {\large\frac{1}{3}} + \dots + {\large\frac{1}{n}}$ kan vi beregne ved å summere ledd for ledd med denne iterative funksjonen:

def harmonisk(n):
    """Beregner 1/1 + 1/2 + ... + 1/n"""
    rekkesum = 0
    # Adder 1/m til rekkesummen for m fra 1 til n
    for m in range(1, n + 1):
        rekkesum += 1/m
    return rekkesum

Men vi kan også basere oss på en rekursiv definisjon av rekka. For n = 1, er summen definert til 

$S_1 = {\large \frac{1}{1}} = 1$

For n > 1, er summen definert til 1/n + summen av leddene foran:

$S_n = {\large \frac{1}{n}} + S_{n-1}$

For eksempel blir

$S_3 = {\large \frac{1}{3}} + S_{2}$

og

$S_2 = {\large \frac{1}{2}} + S_{1}$

Siden S₁ = 1, får vi derved

$S_2 = {\large \frac{1}{2}} + 1 = {\large \frac{3}{2}}$

og

$S_3 = {\large \frac{1}{3}} + {\large \frac{3}{2}} = {\large \frac{11}{6}} \approx 1{,}83333$

Skriv en rekursiv funksjon som bruker dette designet til å beregne S_n.

Husk at det ikke er noen løkker i den rekursive varianten, den kan skrives så og si rett ut fra definisjonen.

Avrundet til 5 desimaler er riktig svar for n = 10 lik 2,92897.

Se løsningsforslag

Oppgave 2:

Vi har en rekursiv funksjon, summer():

def summer(n):
    if n == 1:
        return n
    else:
        return n + summer(n - 1)

Gjør en analyse av koden med penn og papir, og forklar hva som blir skrevet ut når vi i hovedprogrammet skriver

print(summer(3))

Forklar også hva skjer hvis vi i stedet skriver

print(summer(-3))

Sjekk så om du har tenkt riktig ved å kjøre koden, gjerne i Python Tutor.

Se løsningsforslag

Se film om rekursjon

Kilder

• • Matthes A. (2019). Python Crash Course. no starch press