3.4 Grafalgoritmer og trær

Rekursjon

Rekursjon er en teknikk der en funksjon kaller seg selv for å løse et problem. Det høres kanskje rart ut, men det er en av de mest elegante og kraftige ideene i informatikk.

I dette kapittelet skal du lære:
- Hva rekursjon er og hvordan det fungerer
- Basetilfeller og rekursive tilfeller
- Klassiske rekursive problemer
- Sammenligning mellom rekursjon og iterasjon
- Stack overflow og hvordan du unngår det

Mange algoritmer og datastrukturer bygger på rekursjon, inkludert merge sort, trestrukturer og mange søkealgoritmer.

To nødvendige deler:

1. Basetilfelle (base case): Betingelsen som stopper rekursjonen. Uten dette vil funksjonen kalle seg selv i det uendelige.

2. Rekursivt tilfelle (recursive case): Funksjonen kaller seg selv med et forenklet problem som beveger seg mot basetilfellet.

Analogi: Tenk på russiske matryoshka-dukker. Du åpner en dukke og finner en mindre dukke inni. Du fortsetter å åpne til du finner den minste dukken (basetilfellet).

Grunnleggende mønster:

def rekursiv_funksjon(problem):
    if problem er enkelt nok:   # Basetilfelle
        return løsning direkte
    else:                        # Rekursivt tilfelle
        del_opp_problemet
        return rekursiv_funksjon(enklere_problem)

Viktig: Hvert rekursivt kall MÅ bringe oss nærmere basetilfellet, ellers stopper aldri funksjonen.

Fakultet er det klassiske eksempelet på rekursjon:
- 5! = 5 × 4 × 3 × 2 × 1 = 120
- Rekursiv definisjon: n! = n × (n-1)!
- Basetilfelle: 0! = 1

Rekursiv implementasjon:

def fakultet(n):
    """Beregner n! rekursivt"""
    # Basetilfelle
    if n == 0 or n == 1:
        return 1

    # Rekursivt tilfelle
    return n * fakultet(n - 1)

print(fakultet(5))   # 120
print(fakultet(0))   # 1
print(fakultet(10))  # 3628800

Hvordan fungerer det? La oss spore fakultet(4):

fakultet(4)
= 4 * fakultet(3)
= 4 * (3 * fakultet(2))
= 4 * (3 * (2 * fakultet(1)))
= 4 * (3 * (2 * 1))          <- Basetilfelle!
= 4 * (3 * 2)                <- Ruller tilbake
= 4 * 6
= 24

Visualisering av kall-stakken:

fakultet(4)  -> venter...
  fakultet(3)  -> venter...
    fakultet(2)  -> venter...
      fakultet(1)  -> returnerer 1
    returnerer 2 * 1 = 2
  returnerer 3 * 2 = 6
returnerer 4 * 6 = 24

Iterativ versjon for sammenligning:

def fakultet_iterativ(n):
    """Beregner n! iterativt"""
    resultat = 1
    for i in range(2, n + 1):
        resultat *= i
    return resultat

Begge gir samme svar, men den rekursive er mer lik den matematiske definisjonen.

Hva returnerer denne funksjonen når den kalles med summer(4)?

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

Rekursjon og kall-stakken:
Hver gang en rekursiv funksjon kaller seg selv, legges et nytt kall på stakken. Alle ventende kall holdes i minnet til de kan fullføres.

Kall-stakken under fakultet(4):

Steg 1: [fakultet(4)]
Steg 2: [fakultet(4), fakultet(3)]
Steg 3: [fakultet(4), fakultet(3), fakultet(2)]
Steg 4: [fakultet(4), fakultet(3), fakultet(2), fakultet(1)]
Steg 5: [fakultet(4), fakultet(3), fakultet(2)]  <- 1 returnert
Steg 6: [fakultet(4), fakultet(3)]               <- 2 returnert
Steg 7: [fakultet(4)]                            <- 6 returnert
Steg 8: []                                       <- 24 returnert

Stack Overflow: Hvis rekursjonen aldri når basetilfellet, vokser kall-stakken til den sprenger minnegrensen. Python har en standard grense på ca. 1000 rekursive kall.

import sys
print(sys.getrecursionlimit())  # Vanligvis 1000

# ALDRI gjør dette:
def uendelig(n):
    return uendelig(n + 1)  # Ingen basetilfelle!
# RecursionError: maximum recursion depth exceeded

Plasskompleksitet: Rekursive funksjoner bruker O(n) minne for stakken, der n er dybden av rekursjonen.

Fibonacci-tallene er definert rekursivt:
- F(0) = 0, F(1) = 1
- F(n) = F(n-1) + F(n-2) for n > 1
- Serien: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Naiv rekursiv løsning:

def fib(n):
    """Fibonacci - naiv rekursiv versjon"""
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))  # 55
# print(fib(40))  # Ekstremt tregt! Ikke kjør dette.

Problemet: Dobbeltarbeid!

fib(5)
= fib(4) + fib(3)
= (fib(3) + fib(2)) + (fib(2) + fib(1))
= ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + 1)
...

Løsning 1: Memoisering (top-down)

def fib_memo(n, cache={}):
    """Fibonacci med memoisering"""
    if n <= 1:
        return n
    if n not in cache:
        cache[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return cache[n]

print(fib_memo(50))  # 12586269025 - lynraskt!

Løsning 2: Iterativ (bottom-up)

def fib_iterativ(n):
    """Fibonacci iterativt"""
    if n <= 1:
        return n
    forrige = 0
    nåværende = 1
    for _ in range(2, n + 1):
        forrige, nåværende = nåværende, forrige + nåværende
    return nåværende

print(fib_iterativ(50))  # 12586269025

Sammenligning:

Se på denne rekursive funksjonen:

def mystisk(tekst):
    if len(tekst) <= 1:
        return tekst
    return mystisk(tekst[1:]) + tekst[0]

Hva returnerer mystisk("hei")?

Mange listeoperasjoner kan skrives rekursivt:

Sum av liste:

def rekursiv_sum(liste):
    """Beregner summen av en liste rekursivt"""
    # Basetilfelle: tom liste
    if len(liste) == 0:
        return 0

    # Rekursivt: første element + sum av resten
    return liste[0] + rekursiv_sum(liste[1:])

print(rekursiv_sum([1, 2, 3, 4, 5]))  # 15

Finn største element:

def rekursiv_maks(liste):
    """Finner største element rekursivt"""
    # Basetilfelle: bare ett element
    if len(liste) == 1:
        return liste[0]

    # Rekursivt: sammenlign første med maks av resten
    maks_resten = rekursiv_maks(liste[1:])
    if liste[0] > maks_resten:
        return liste[0]
    else:
        return maks_resten

print(rekursiv_maks([3, 7, 2, 9, 4]))  # 9

Tell forekomster:

def tell(liste, mål):
    """Teller forekomster av mål i liste, rekursivt"""
    if len(liste) == 0:
        return 0

    treff = 1 if liste[0] == mål else 0
    return treff + tell(liste[1:], mål)

print(tell([1, 2, 3, 2, 1, 2], 2))  # 3

Merk: Disse rekursive versjonene er ikke mer effektive enn iterative versjoner. De bruker mer minne (kall-stakken) og liste[1:] lager en ny liste for hvert kall (O(n) ekstra).

Når er rekursiv listebehandling nyttig?
- For å lære rekursiv tenkning
- Når datastrukturen selv er rekursiv (f.eks. trestrukturer)
- I funksjonelle programmeringsspråk
- For problemer som naturlig deler seg i delproblemer

Skriv en rekursiv funksjon potens(base, eksponent) som beregner base^eksponent uten å bruke **-operatoren eller pow().

Hint:
- base^0 = 1 (basetilfelle)
- base^n = base * base^(n-1) (rekursivt tilfelle)

Sammenligning:

- Når ytelse er kritisk
- Når rekursjonsdybden kan bli stor
- Lineære gjennomganger av data
Huskeregel: Bruk rekursjon når problemet er naturlig rekursivt. Bruk iterasjon når problemet er naturlig lineært.

La oss sammenligne rekursiv og iterativ løsning for noen vanlige problemer:

Problem 1: Nedtelling

# Rekursiv
def nedtelling_rek(n):
    if n <= 0:
        print("Start!")
        return
    print(n)
    nedtelling_rek(n - 1)

# Iterativ
def nedtelling_iter(n):
    for i in range(n, 0, -1):
        print(i)
    print("Start!")

# Begge gir: 5, 4, 3, 2, 1, Start!

Her er den iterative versjonen klart enklere. Rekursjon gir ingen fordel.

Problem 2: Katalogstruktur (trestruktur)

import os

# Rekursiv - naturlig og elegant
def vis_filer_rek(mappe, innrykk=0):
    """Vis alle filer rekursivt"""
    for element in os.listdir(mappe):
        sti = os.path.join(mappe, element)
        print("  " * innrykk + element)
        if os.path.isdir(sti):
            vis_filer_rek(sti, innrykk + 1)

# Iterativ - mer komplisert med egen stakk
def vis_filer_iter(mappe):
    """Vis alle filer iterativt med eksplisitt stakk"""
    stakk = [(mappe, 0)]
    while stakk:
        nåværende, innrykk = stakk.pop()
        print("  " * innrykk + os.path.basename(nåværende))
        if os.path.isdir(nåværende):
            for element in reversed(os.listdir(nåværende)):
                stakk.append((os.path.join(nåværende, element), innrykk + 1))

Her er den rekursive versjonen mye mer lesbar fordi filsystemer er en trestruktur.

Problem 3: Omvendt streng

# Rekursiv
def reverser_rek(s):
    if len(s) <= 1:
        return s
    return reverser_rek(s[1:]) + s[0]

# Iterativ
def reverser_iter(s):
    return s[::-1]

# Pythonic
"hei"[::-1]  # "ieh"

Her er Python-slicing klart enklest. Rekursjon er unødvendig.

Konklusjon: Velg den tilnærmingen som gir mest lesbar kode for det aktuelle problemet.

For hvert problem, avgjør om rekursjon eller iterasjon er mest naturlig:

A) Beregne gjennomsnittet av en liste med tall
B) Søke gjennom en trestruktur (f.eks. filsystem)
C) Skrive ut tallene fra 1 til n
D) Merge sort

Når en rekursiv funksjon kaller seg selv for mange ganger, fylles kall-stakken opp og programmet krasjer.

# Dette vil krasje!
def evig_rekursjon(n):
    return evig_rekursjon(n + 1)

# RecursionError: maximum recursion depth exceeded

Pythons rekursjonsgrense:

import sys

# Se gjeldende grense
print(sys.getrecursionlimit())  # 1000

# Endre grensen (forsiktig!)
sys.setrecursionlimit(5000)

Eksempel: Fakultet med dyp rekursjon

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

# Fungerer
print(fakultet(500))   # Stort tall, men OK

# Krasjer!
# print(fakultet(1500))  # RecursionError

Løsninger for å unngå stack overflow:

1. Skriv om til iterasjon:

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

print(fakultet_iterativ(10000))  # Ingen problem!

2. Bruk halerekursjon-optimalisering (ikke i Python):

# Python optimaliserer IKKE halerekursjon, men konseptet:
def fakultet_hale(n, akkumulator=1):
    if n <= 1:
        return akkumulator
    return fakultet_hale(n - 1, n * akkumulator)
# Siste kall er det rekursive kallet - ingen ventende operasjoner
# Noen språk (Scheme, Haskell) optimaliserer dette til en løkke

3. Bruk memoisering for å redusere dybden:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

# Bygger opp cache gradvis
for i in range(0, 2000, 100):
    fib(i)
print(fib(1999))  # Fungerer fordi cache reduserer dybden

Huskeregel: Hvis rekursjonsdybden kan bli over ~500, vurder iterativ løsning.

Denne rekursive funksjonen skal beregne summen av sifrene i et tall, men den har en feil. Hva er feilen?

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

Oppsummering

Rekursjon er en teknikk der en funksjon kaller seg selv.

To nødvendige deler:
1. Basetilfelle - stopper rekursjonen
2. Rekursivt tilfelle - forenkler problemet og kaller seg selv

Klassiske rekursive problemer:
- Fakultet: n! = n * (n-1)!
- Fibonacci: F(n) = F(n-1) + F(n-2)
- Tretraversering
- Merge sort (del-og-hersk)
- Binærsøk

Rekursjon vs iterasjon:

1. Alltid definer basetilfelle(r) først
2. Sørg for at hvert kall beveger seg mot basetilfellet
3. Vurder iterasjon hvis rekursjonsdybden kan bli > 500
4. Bruk memoisering for overlappende delproblemer (som Fibonacci)

5. Test med små input og spor gjennom kall-stakken

Samleoppgaver

Oppgaver som kombinerer rekursiv tenkning med andre konsepter:

Et palindrom er et ord som leses likt begge veier (f.eks. "ana", "racecar").

Skriv en rekursiv funksjon som sjekker om en streng er et palindrom.

Hint: Et ord er et palindrom hvis:
- Første og siste bokstav er like
- Resten av ordet (uten første og siste) også er et palindrom

Tårnet i Hanoi er et klassisk rekursivt problem:
- Du har 3 pinner (A, B, C) og n disker i ulik størrelse
- Alle disker starter på pinne A, sortert med størst nederst
- Mål: Flytt alle disker til pinne C
- Regler: Flytt bare én disk om gangen, aldri en større disk på en mindre

Hvor mange trekk kreves for å flytte n disker?