Rekursion

Programmering B · HTX · B-niveau · Datastrukturer og algoritmer

💻 Rekursion

Rekursion: en funktion der kalder sig selv.

Grundstruktur:

1. Basis-case: stop-betingelse der ALTID skal eksistere

2. Rekursivt kald: kalder sig selv med et mindre problem

Eksempel — fakultet:

```python

def fakultet(n: int) -> int:

if n <= 1: # basis-case

return 1

return n * fakultet(n - 1) # rekursivt kald

fakultet(5) # = 5 4 3 2 1 = 120

```

Fibonacci (naivt — eksponentiel tid O(2^n)):

```python

def fib_naiv(n):

if n <= 1: return n

return fib_naiv(n-1) + fib_naiv(n-2)

```

Fibonacci med memoization (O(n)):

```python

from functools import lru_cache

@lru_cache(maxsize=None)

def fib(n):

if n <= 1: return n

return fib(n-1) + fib(n-2)

```

Stack overflow: for dyb rekursion → Python max ~1000 niveauer.

Når er rekursion godt?

• Træer og grafer (DFS)
• Del-og-hersk algoritmer (Quicksort, Merge sort)
• Problemer med naturlig rekursiv struktur

Rekursion vs. iteration: rekursion er ofte mere læsbar, iteration er typisk hurtigere.

Læringsmål

• Skrive rekursive funktioner med korrekt basis-case
• Omskrive rekursiv løsning til iterativ
• Anvende memoization til at optimere rekursion
• Identificere hvornår rekursion er det bedste valg

Sådan kan du arbejde med emnet

• Skriv en rekursiv funktion, der beregner faktorial af et tal
• Forklar hvad et basistilfælde (base case) er, og hvorfor det er nødvendigt i rekursion
• Diskutér en fordel og en ulempe ved at bruge rekursion i forhold til en løkke

Træningsforslag

• Implementer binær søgning rekursivt
• Løs Tower of Hanoi rekursivt og forklar den rekursive struktur
• Sammenlign køretid for fib_naiv vs. fib med memoization for n=35