3.4 Grafalgoritmer og trær

Rekursjon

Rekursjon er ein teknikk der ein funksjon kallar seg sjølv for å løyse eit problem. Det høyrest kanskje rart ut, men det er ein av dei mest elegante og kraftige ideane i informatikk.

I dette kapittelet skal du lære:
- Kva rekursjon er og korleis det fungerer
- Basetilfelle og rekursive tilfelle
- Klassiske rekursive problem
- Samanlikning mellom rekursjon og iterasjon
- Stack overflow og korleis du unngår det

Mange algoritmar og datastrukturar byggjer på rekursjon, inkludert merge sort, trestrukturar og mange søkealgoritmar.

To nødvendige delar:

1. Basetilfelle (base case): Vilkåret som stoppar rekursjonen. Utan dette vil funksjonen kalle seg sjølv i det uendelege.

2. Rekursivt tilfelle (recursive case): Funksjonen kallar seg sjølv med eit forenkla problem som bevegar seg mot basetilfellet.

Analogi: Tenk på russiske matrjosjka-dukker. Du opnar ei dukke og finn ei mindre dukke inni. Du held fram med å opne til du finn den minste dukka (basetilfellet).

Grunnleggjande 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: Kvart rekursivt kall MÅ bringe oss nærare basetilfellet, elles stoppar funksjonen aldri.

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

Korleis 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 same svar, men den rekursive er meir lik den matematiske definisjonen.

Kva returnerer denne funksjonen når han blir kalla med summer(4)?

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

Rekursjon og kall-stakken:
Kvar gong ein rekursiv funksjon kallar seg sjølv, blir eit nytt kall lagt på stakken. Alle ventande kall blir haldne i minnet til dei kan fullførast.

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: Dersom rekursjonen aldri når basetilfellet, veks kall-stakken til han sprengjer minnegrensa. Python har ei standardgrense 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 funksjonar bruker O(n) minne for stakken, der n er djupna av rekursjonen.

Fibonacci-tala er definerte 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øysing:

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øysing 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øysing 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

Samanlikning:

Sjå på denne rekursive funksjonen:

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

Kva returnerer mystisk("hei")?

Mange listeoperasjonar kan skrivast 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: Desse rekursive versjonane er ikkje meir effektive enn iterative versjonar. Dei bruker meir minne (kall-stakken) og liste[1:] lagar ei ny liste for kvart kall (O(n) ekstra).

Når er rekursiv listebehandling nyttig?
- For å lære rekursiv tenking
- Når datastrukturen sjølv er rekursiv (t.d. trestrukturar)
- I funksjonelle programmeringsspråk
- For problem som naturleg deler seg i delproblem

Skriv ein rekursiv funksjon potens(base, eksponent) som reknar ut base^eksponent utan å bruke **-operatoren eller pow().

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

Samanlikning:

- Når yting er kritisk
- Når rekursjonsdjupna kan bli stor
- Lineære gjennomgangar av data
Hugseregel: Bruk rekursjon når problemet er naturleg rekursivt. Bruk iterasjon når problemet er naturleg lineært.

La oss samanlikne rekursiv og iterativ løysing for nokre vanlege problem:

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 enklare. 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 mykje meir lesbar fordi filsystem er ein 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 enklast. Rekursjon er unødvendig.

Konklusjon: Vel den tilnærminga som gir mest lesbar kode for det aktuelle problemet.

For kvart problem, avgjer om rekursjon eller iterasjon er mest naturleg:

A) Rekne ut gjennomsnittet av ei liste med tal
B) Søkje gjennom ein trestruktur (t.d. filsystem)
C) Skrive ut tala frå 1 til n
D) Merge sort

Når ein rekursiv funksjon kallar seg sjølv for mange gonger, blir kall-stakken fylt opp og programmet krasjar.

# 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

Hugseregel: Dersom rekursjonsdjupna kan bli over ~500, vurder iterativ løysing.

Denne rekursive funksjonen skal rekne ut summen av siffera i eit tal, men han har ein feil. Kva er feilen?

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

Oppsummering

Rekursjon er ein teknikk der ein funksjon kallar seg sjølv.

To nødvendige delar:
1. Basetilfelle - stoppar rekursjonen
2. Rekursivt tilfelle - forenklar problemet og kallar seg sjølv

Klassiske rekursive problem:
- 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. Definer alltid basetilfelle først
2. Sørg for at kvart kall bevegar seg mot basetilfellet
3. Vurder iterasjon dersom rekursjonsdjupna kan bli > 500
4. Bruk memoisering for overlappande delproblem (som Fibonacci)

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

Samleoppgåver

Oppgåver som kombinerer rekursiv tenking med andre konsept:

Eit palindrom er eit ord som blir lese likt begge vegar (t.d. "ana", "racecar").

Skriv ein rekursiv funksjon som sjekkar om ein streng er eit palindrom.

Hint: Eit ord er eit palindrom dersom:
- Første og siste bokstav er like
- Resten av ordet (utan første og siste) også er eit palindrom

Tårnet i Hanoi er eit klassisk rekursivt problem:
- Du har 3 pinnar (A, B, C) og n diskar i ulik storleik
- Alle diskar startar på pinne A, sortert med størst nedst
- Mål: Flytt alle diskar til pinne C
- Reglar: Flytt berre éin disk om gongen, aldri ein større disk på ein mindre

Kor mange trekk krevst for å flytte n diskar?