Rekursion og memoization

Kommunikation og IT A · HTX · A-niveau · Avanceret programmering

💻 Rekursion og memoization

Rekursion er en funktion der kalder sig selv. Kræver: (1) basistilfælde der stopper rekursionen og (2) rekursivt trin der reducerer problemet.

```python

def fib(n):

if n <= 1: return n # basistilfælde

return fib(n-1) + fib(n-2) # rekursivt trin

```

Problem: fib(40) beregner de samme delproblemer milliarder af gange → O(2ⁿ).

Memoization cacher beregnede resultater:

```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)

Nu O(n) i stedet for O(2ⁿ)

```

Klassiske rekursive problemer: fakultet, Fibonacci, tårne i Hanoi, binær søgning, træ-traversal (pre/in/post-order), quicksort.

Call stack: hver rekursivt kald bruger hukommelse → stack overflow hvis rekursionsdybden er for stor. Pythons standardgrænse: 1000.

Læringsmål

• Skrive korrekte rekursive funktioner med basistilfælde og rekursivt trin
• Identificere rekursive problemer og vurdere effektiviteten
• Implementere memoization med lru_cache eller manuel dict-cache
• Forklare risikoen for stack overflow og hvornår iteration er bedre

Sådan kan du arbejde med emnet

• Skriv en rekursiv funktion til at beregne fakultet af et tal og forklar basistilfældet
• Beregn de første 10 Fibonacci-tal med og uden memoization — sammenlign antal funktionskald
• Forklar hvorfor en rekursiv funktion uden basistilfælde fører til stack overflow

Træningsforslag

• Implementér tårne i Hanoi rekursivt og vis trin-for-trin
• Sammenlign Fibonacci rekursivt vs. memoization med tidsmåling
• Løs LeetCode-opgaver om rekursion (Climbing Stairs, Tree Traversal)