Rekursion og memoization

It A · STX · A-niveau · Avanceret programmering

💻 Rekursion og memoization

Rekursion er en teknik hvor en funktion kalder sig selv for at løse et delproblem. Grundlæggende struktur:

1.

Basistilfælde: stopper rekursionen.

2.

Rekursivt tilfælde: opdeler problemet.

Fibonacci-eksempel: fib(n) = fib(n-1) + fib(n-2) med fib(0)=0, fib(1)=1. Naiv rekursion: eksponentiel tidskompleksitet O(2ⁿ) fordi genberegner.

Memoization: cache resultaterne af dyrere funktionskald for at undgå genberegning. Implementeres med dict (Python) eller @functools.lru_cache. fib(50) med memoization: O(n) mod O(2ⁿ) uden.

Tørn-basede eksempler: merge sort (opdel list → sortér halvdele → merge), QuickSort (vælg pivot → partition → sortér sub-lister), Tower of Hanoi (flytte n skiver via 3 pinde).

Kald-stakken: hvert rekursivt kald tilføjer en frame. Python's standard stack limit: 1000 kald.

Tail recursion: i sprog som Scheme er tail-rekursion optimeret (TCO). Python har ikke TCO.

Dynamisk programmering (bottom-up alternativ til memoization top-down): byg løsning systematisk fra basistillfælde.

Læringsmål

• Implementere OOP (klasser, arv, polymorfi, enkapsulering)
• Anvende rekursion og memoization
• Implementere og forklare Big-O for centrale datastrukturer
• Implementere merge sort og quicksort
• Anvende BFS og DFS på grafer

Sådan kan du arbejde med emnet

• Implementér en rekursiv fibonacci-funktion og lav en version med memoization — sammenlign køretid på fib(35)
• Skriv en rekursiv funktion, der beregner summen af alle tal i en nesting liste
• Forklar, hvad base case og recursive case er, og hvad der sker, hvis base case mangler

Arbejd iterativt med prototyper og dokumentation. Test, evaluér og dokumentér.