CSBootcampHSG

Lektion 04

Rekursion, Higher-Order und Datenstrukturen

Rekursion sauber denken (Basisfall + Rekursivfall), Higher-Order-Funktionen mit map/filter/sorted und Lambdas, dazu der Unterschied zwischen Liste, Dict und Set. Wenn du das im Schlaf hast, sind Quiz 04 und das Assignment routine.

Dauer:
60 Min. geschätzt
Voraussetzungen:
Funktionen (Lektion 03)
Stilisierter geometrischer Baum: ein rekursiver Funktionsaufruf, dessen Aufrufe sich wie Äste verzweigen, mit kleinen Knoten f(n), f(n-1), f(n-2)

Theorie & Konzepte

Phase 1 / 4

Bisher hast du Schleifen benutzt, um etwas mehrfach zu machen. In dieser Lektion lernst du drei Alternativen dazu, die in jeder professionellen Codebasis vorkommen:

  1. Rekursion — eine Funktion ruft sich selbst auf. Klingt verrückt, ist aber für manche Probleme die natürlichste Formulierung.
  2. Higher-Order-Funktionenmap, filter, sorted und Lambdas. Eine Schleife in einer Zeile.
  3. Dicts und Sets — die richtigen Datenstrukturen für Nachschlagen und Eindeutigkeit.

Quiz 04 testet alle drei genau dort, wo Anfänger ausrutschen — bei Endlosrekursion, bei list(map(...))-Traces und bei der Frage was passiert, wenn der Basisfall nie greift. Nach dieser Lektion fallen dir diese Stolpersteine direkt ins Auge.

Rekursion — Basisfall + Rekursivfall

Eine rekursive Funktion ruft sich selbst auf. Damit das nicht ewig läuft, braucht sie zwingend zwei Teile:

  • Basisfall (base case) — die Bedingung, unter der die Funktion direkt ein Ergebnis liefert, ohne sich selbst aufzurufen.
  • Rekursivfall (recursive case) — wir verkleinern das Problem und rufen uns selbst mit dem kleineren Input wieder auf.
def factorial(n):
    if n == 0:        # Basisfall: 0! = 1
        return 1
    return n * factorial(n - 1)   # Rekursivfall: n! = n · (n-1)!

Lies das laut: "Wenn n null ist, ist die Antwort eins. Sonst ist sie n mal die Antwort für n-1." — Genau dieselbe Definition wie in Mathe.

Die goldene Regel: Im Rekursivfall muss der Aufruf näher am Basisfall sein als der jetzige. Sonst wirst du ihn nie erreichen, der Aufrufstapel wächst, und Python bricht mit RecursionError: maximum recursion depth exceeded ab.

Der Aufrufstapel — wie Rekursion abgearbeitet wird

Aufrufstapel von factorial(3) — drei Stack-Frames bis zum Basisfall, dann zurück.factorial(3) wird aufgerufenfactorial(3)return 3 * 2 6factorial(2)return 2 * 1 2factorial(1)return 1 * 1 1factorial(0)return Basisfall → 1 1Jeder Aufruf legt einen Stack-Frame an. Der Basisfall liefert direkt einen Wert, der dann nach oben zurückgereicht wird.
Jeder rekursive Aufruf legt einen Stack-Frame an. Der Basisfall liefert einen konkreten Wert, der dann nach oben durchgereicht wird.

Cheat-Sheet: Rekursion auf einer Seite

Cheat-Sheet: Rekursion. Zwei Karten: Basisfall (return-Wert direkt) und Rekursivfall (sich selbst mit kleinerem Input aufrufen). Unten die Aufrufkette factorial(3) → factorial(2) → factorial(1) → factorial(0).
Druck dir das aus, bevor du die Aufgaben angehst.

Rekursion vs. Iteration

Beide rechnen `factorial(4)` aus. Welche Form du bevorzugst, hängt vom Problem ab.

Rekursiv

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Liest sich wie die mathematische Definition. Schön, wenn das Problem rekursiv gedacht ist (Bäume, Fraktale, Fibonacci, Quicksort).

Iterativ

def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

Kein Aufrufstapel, keine Rekursionstiefe. Pythons sweet spot — schneller und ohne RecursionError.

Doppel-Rekursion — Fibonacci

Manchmal hat eine Funktion zwei Basisfälle — und ruft sich pro Aufruf zweimal selbst auf. Das ist völlig zulässig, sieht so aus:

def fibonacci(n):
    if n == 0:
        return 0          # Basisfall 1
    if n == 1:
        return 1          # Basisfall 2
    return fibonacci(n - 2) + fibonacci(n - 1)   # zwei Rekursivaufrufe

fibonacci(4) löst sich auf zu fibonacci(2) + fibonacci(3), jeder davon wieder zu zweien, … Das wächst exponentiell — fibonacci(35) macht schon Millionen Aufrufe. Pythons RecursionError-Limit (~1000) wirst du dabei nicht direkt sehen, aber Geduld solltest du mitbringen.

Wichtig fürs Quiz:

  • Mehrere Basisfälle sind kein Bug — die Funktion ist trotzdem terminierend, solange jeder Pfad bei einem davon landet.
  • Mit fibonacci(-1) rutschst du in den Rekursivfall (-1 ist weder 0 noch 1) → fibonacci(-3) + fibonacci(-2) → … → RecursionError. Negative n führen zu unendlicher Rekursion.

Aufrufbaum von `fibonacci(4)`

Aufrufbaum von fibonacci(4): jede Verzweigung liefert zwei neue Aufrufe; viele wiederholen sich.f(4)=3f(2)=1f(3)=2f(0)=0f(1)=1f(1)=1f(2)=1f(0)=0f(1)=1RekursivfallBasisfallDoppelt berechnetf(4) braucht 9 Aufrufe — 5 davon Basisfälle, 4 wiederholen Berechnungen.
Pro Aufruf entstehen zwei neue Aufrufe. Viele Teilbäume berechnen denselben Wert mehrfach — daher die exponentielle Laufzeit.

Higher-Order-Funktionen — `map`, `filter`, `sorted`

Funktionen sind in Python ganz normale Werte. Du kannst sie an Variablen binden, in Listen stecken und — am wichtigsten — anderen Funktionen als Argument übergeben. So funktionieren map, filter und sorted:

zahlen = [1, 2, 3, 4, 5]

# map: wende eine Funktion auf JEDES Element an
list(map(lambda x: x * x, zahlen))      # → [1, 4, 9, 16, 25]

# filter: behalte nur Elemente, für die die Funktion True liefert
list(filter(lambda x: x % 2 == 0, zahlen))   # → [2, 4]

# sorted: sortiere mit einem optionalen Vergleichsschlüssel
sorted(zahlen, key=lambda x: -x)         # → [5, 4, 3, 2, 1]

Wichtig: map und filter geben einen Iterator zurück, keine Liste. Du musst sie mit list(...) materialisieren, sonst siehst du nur etwas wie <map object at 0x…>.

List Comprehension vs. `map`/`filter`

Beide bauen `[x*x for x in zahlen if x % 2 == 0]`. Welche Form du wählst, ist Geschmackssache.

List Comprehension (pythonic)

[x * x for x in zahlen if x % 2 == 0]
# → [4, 16]

Liest sich wie ein Satz: die Quadrate aller geraden Zahlen. Im Pandas-Alltag und in der Standardbibliothek meist die Form, die du siehst.

map + filter

list(map(lambda x: x * x,
         filter(lambda x: x % 2 == 0, zahlen)))
# → [4, 16]

Funktional aequivalent. Für HSG-Quiz und -Assignment musst du beide Formen lesen können — die Aufgaben drehen sich oft um list(map(filter(…)))-Konstrukte.

`map`/`filter` als Pipeline

Pipeline: range(5) → filter (gerade) → map (Quadrat) → list. Werte fliessen von links nach rechts.Quellerange(5)01234filterx % 2 == 001234mapx → x*x0416list(...)materialisiert[0, 4, 16]Filter wirft 1 und 3 weg; map quadriert die durchgelassenen; list materialisiert das Ergebnis.
filter wirft Elemente weg, map verändert die durchgelassenen. Erst list() zwingt die ganze Pipeline zur Auswertung.

Cheat-Sheet: map · filter · sorted

Cheat-Sheet zu map, filter und sorted: jede Funktion mit Signatur, Erklärung und einem konkreten Beispiel.
Die drei Higher-Order-Klassiker, jeweils mit einem Mini-Beispiel.

Lambda-Funktionen — die Einzeiler-Variante

Ein Lambda ist eine anonyme Funktion — kein def, kein Name, ein Ausdruck. Genau dann nützlich, wenn du eine kleine Funktion einmal brauchst:

quadrat = lambda x: x * x
quadrat(4)        # 16  — wie eine normale Funktion

# Häufiger sieht man sie inline:
sorted([(1, 'b'), (2, 'a')], key=lambda pair: pair[1])
# → [(2, 'a'), (1, 'b')]

Drei Regeln:

  1. Genau ein Ausdruck — kein Block, kein if/else-Statement (aber der Ausdruck a if cond else b ist erlaubt).
  2. Argumente wie eine normale Funktion, aber kein return — der Ausdruck ist die Rückgabe.
  3. Wenn die Funktion länger als eine Zeile wird, schreib sie als def. Lambdas sind kein Selbstzweck.

Dictionaries und Sets

Dict = key → value-Zuordnung. Set = ungeordnete Sammlung eindeutiger Werte.

# Dict — Nachschlagen
ages = {'Alice': 30, 'Bob': 25, 'Carol': 28}
ages['Bob']                       # 25
ages.get('Dave', 'unbekannt')     # 'unbekannt' — Default statt KeyError
ages.keys(); ages.values(); ages.items()

# Set — Eindeutigkeit
names = {'Alice', 'Bob', 'Alice'}     # → {'Alice', 'Bob'}
'Bob' in names                         # True — schneller Lookup
set([1, 2, 2, 3, 3, 3])               # → {1, 2, 3} — dedup einer Liste

Wann was?

  • Liste: Reihenfolge wichtig, Duplikate erlaubt, Index-Zugriff (xs[0]).
  • Tupel: Wie Liste, aber unveränderlich (siehe Lektion 03).
  • Dict: Nachschlagen per Schlüssel, Schlüssel sind eindeutig.
  • Set: Eindeutigkeit, schnelles in-Testen, mathematische Mengenoperationen.

Set-Operationen — Vereinigung, Schnitt, Differenz

Set-Operationen: Vereinigung, Schnitt, Differenz, symmetrische Differenz.Sets als Mengen — visuell aufeinander abgebildetA | B (union)ABalles aus A und BA & B (intersect)ABnur die ÜberlappungA - B (diff)ABA ohne BA ^ B (symm. diff)ABalles ausser SchnittOperatoren: | & - ^. Methoden: union, intersection, difference, symmetric_difference.
Sets bringen Mengenlehre nach Python: `|` Vereinigung, `&` Schnitt, `-` Differenz, `^` symmetrische Differenz.

Cheat-Sheet: list / tuple / set / dict

Cheat-Sheet: list, tuple, set, dict — Entscheidungskarte mit Syntax und Anwendungsfall pro Datentyp.
Wann nimmst du welche Datenstruktur? Eine Karte, vier Antworten.

Assignment-Walkthrough

Phase 2 / 4

Hier gehen wir typspezifisch durch die 5 Aufgabenformen von Assignment 04: was gefragt ist, wie man es angeht, und wo man sich typischerweise verrennt. Die konkreten Namen und Daten siehst du im HSG-Notebook — die Muster hier passen auf jede Variante.

Assignment-Aufgabe 1

Eine rekursive Funktion definieren

Was ist gefragt

Die erste Aufgabe ist immer das Lehrbuch-Rezept: eine Funktion definieren, die sich selbst aufruft, um eine Aggregation (Summe, Produkt, Anzahl) über einen ganzzahligen Bereich zu bilden — ohne range(), ohne Schleife.

Das HSG-Notebook gibt dir eine Vorbedingung wie number ist eine gerade Zahl ≥ 2". Daran erkennst du den Basisfall.

Strategie

Drei Schritte:

  1. Basisfall identifizieren. Was ist die Antwort für den kleinstmöglichen gültigen Input? Bei recursive_sum(2)2. Bei recursive_factorial(0)1.
  2. Rekursivfall aufschreiben. Reduziere das Problem um eine Stufe und kombiniere es: f(n) = n + f(n - schritt) oder f(n) = n * f(n - 1).
  3. Endet die Folge im Basisfall? Spiel den Aufruf im Kopf durch: f(6) → f(4) → f(2) → 2. Wenn du beim Basisfall ankommst, passt es.

Lösungsskelett

def recursive_aggregat(number):
    if number == BASISFALL_WERT:        # ← was liefert direkt ein Ergebnis?
        return BASISFALL_RUECKGABE
    return KOMBINIERE(number, recursive_aggregat(number - SCHRITT))

Typische Stolperstellen

  • Falsche Schrittweite. Soll deine Folge nur durch gerade Zahlen gehen? Dann number - 2, nicht number - 1.
  • Basisfall verfehlbar. if number == 2 ist nur erreichbar für gerade Zahlen ≥ 2. Für ungerade oder negative Inputs läuft die Rekursion endlos. Lies die Vorbedingung, dann ist der Basisfall für jeden gültigen Input erreichbar.
  • Stop-Condition zuerst! Schreib den Basisfall vor dem Rekursivfall. Vergisst du ihn, hast du Endlosrekursion.

Assignment-Aufgabe 2

Doppel-Rekursion mit zwei Basisfällen

Was ist gefragt

Aufgabe 2 ist klassisch Fibonacci — eine Funktion, die sich pro Aufruf zweimal selbst aufruft. Der Rekursivfall referenziert n-1 und n-2, deshalb brauchst du zwingend zwei Basisfälle (für die kleinsten beiden Werte).

Das Muster ist universell — Treppen-Aufstiege, Pfade in Gittern, einige Spielbaum-Probleme haben dieselbe Struktur.

Strategie

  1. Beide Basisfälle hinschreiben. Bei fibonacci: n == 0 → 0, n == 1 → 1. Direkt ohne Rekursion.
  2. Rekursivfall. f(n) = f(n - 2) + f(n - 1).
  3. Reihenfolge der ifs irrelevant — beide sind gleichberechtigt, sie schliessen einander aus.

Lösungsskelett

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

Typische Stolperstellen

  • Nur ein Basisfall. Ohne den zweiten landet fibonacci(1) → fibonacci(-1) + fibonacci(0) → endlose Rekursion.
  • Negative n. Die Funktion endet nicht für negative Eingaben. Wenn die Aufgabenstellung das nicht ausschließt, prüfe if n < 0: raise ValueError(...) ab.
  • Geschwindigkeit. Naive Doppel-Rekursion ist exponentiell langsam. Für fibonacci(35) sekunden, fibonacci(50) minutenlang. Im Quiz nicht relevant, im echten Code: nutze functools.lru_cache oder Iteration.

Assignment-Aufgabe 3

`map` mit eigener Funktion auf eine Liste anwenden

Was ist gefragt

Aufgabe 3 ist die Transformation einer Liste: definiere zuerst eine kleine Hilfsfunktion (z. B. aus einer Zahl die Ziffern absteigend sortiert als String), dann wende sie via map auf eine vorgegebene Liste an. Speichere das Ergebnis als konkrete Liste (nicht als map-Object).

Strategie

  1. Hilfsfunktion definieren — entweder mit def (besser lesbar) oder als Lambda. Test sie zuerst mit einem Einzelwert.
  2. map anwendenmap(deine_funktion, deine_liste) liefert einen Iterator.
  3. Materialisierenlist(map(...)). Ohne dieses list hast du nur ein <map object at 0x...>-Reservoir.

Lösungsskelett

def transformiere(zahl):
    return "".join(sorted(str(zahl), reverse=True))   # Beispielhilfsfunktion

to_sort = [1, 10, 23, 33, 42, 100, 48279]
sorted_list = list(map(transformiere, to_sort))

Typische Stolperstellen

  • list(...) vergessen. Ohne wirft die Testzelle einen AssertionError, weil map-Object ≠ erwartete Liste.
  • Verwechslung von map und filter. map transformiert alle Elemente, filter behält nur einige. Lies die Aufgabe genau.
  • Ergebnis-Typ. sort_numbers_by_digit aus dem HSG-Beispiel gibt Strings zurück ("42"), keine Ints. Wenn die Tests Strings erwarten, gib Strings zurück. Wenn sie int erwarten (Quiz 04 Q5!), wickle das Ergebnis in int(...).

Assignment-Aufgabe 4

Gruppen-Aufteilung (advanced) — Slicing + Padding

Was ist gefragt

Die vierte Aufgabe ist als ADVANCED markiert und wird nicht im nächsten Quiz geprüft. Sie kombiniert mehrere Konzepte: ganzzahlige Division, Slicing einer Liste, optionales Auffüllen mit Platzhaltern. Lohnt sich nur, wenn du Zeit hast.

Idee: gegeben eine Liste von Studenten und eine Anzahl Gruppen, baue eine Liste von Listen — jede Gruppe gleich groß, fehlende Plätze mit "__EMPTY__" aufgefüllt.

Strategie

  1. Pro Gruppe Plätze berechnen. gross = ceil(len(students) / groups). In Python ohne math: (len(students) + groups - 1) // groups oder die Fallunterscheidung wie im HSG-Solution.
  2. Liste auffüllen. students.extend(['__EMPTY__'] * (gross * groups - len(students))).
  3. In Gruppen slicen. students[i:i+gross] für i in range(0, len(students), gross).

Lösungsskelett

def group_students(students, groups=2):
    n = len(students)
    if n % groups == 0:
        per = n // groups
    else:
        per = n // groups + 1
        students = students + ['__EMPTY__'] * (per * groups - n)

    return [students[i:i + per] for i in range(0, len(students), per)]

Typische Stolperstellen

  • In-place vs. Kopie. Im HSG-Solution wird students.extend(...) benutzt — das verändert die Eingabeliste! Sicherer ist eine Kopie (students = students + [...] statt students.extend(...)).
  • Default-Wert. groups=2 ist die geforderte Default-Signatur. Vergiss ihn nicht — Tests prüfen die Signatur explizit.
  • math.ceil ist nicht in math importiert. Im HSG-Notebook ist nichts importiert. Nutze die Fallunterscheidung oder Floor-Division-Trick.

Assignment-Aufgabe 5

Streamlit (Installation und erste Schritte)

Was ist gefragt

Aufgabe 5 ist kein Coding-Problem, sondern eine Installations- und Einrichtungs-Aufgabe für Streamlit auf deinem lokalen Rechner. Es gibt keine Test-Zelle, keine erwartete Funktion.

Deshalb ist hier nichts zu graden — und unser Pyodide-Browser-Sandbox kann Streamlit ohnehin nicht ausführen (das braucht einen lokalen Webserver).

Strategie

Folge den HSG-Anweisungen direkt im Notebook. Kurzfassung:

  1. Terminal/Anaconda Prompt öffnen.
  2. pip install streamlit ausführen.
  3. Eine Datei app.py mit ein paar st.write(...) Zeilen anlegen.
  4. streamlit run app.py starten — Browser sollte sich öffnen.

Wenn du das einmal aufgesetzt hast, vergiss es bis Modul 4. Im Quiz 04 wird Streamlit nicht abgefragt.

Typische Stolperstellen

  • Falsches Terminal auf Windows. Anaconda Prompt verwenden, nicht das normale cmd.exe — sonst findet pip die richtige Python-Installation nicht.
  • Port belegt. Wenn streamlit run einen Port-Konflikt meldet, mit --server.port 8502 einen anderen Port nehmen.
  • Mehrfache Python-Installationen. Stelle sicher, dass pip zur gleichen Python-Version gehört, die dein Jupyter benutzt.

Aufgaben

Phase 3 / 4
Aufgabe

Rekursive Produkt-Funktion

2 Punkte

Schreibe eine rekursive Funktion product_of_odds(n), die das Produkt aller ungeraden Zahlen von 1 bis n (inklusive) zurückgibt.

Anforderungen:

  • n ist eine ungerade ganze Zahl ≥ 1.
  • Verwende keine Schleife und kein range(). Die Lösung ist rekursiv.
  • Basisfall: für n = 1 ist das Ergebnis 1.

Beispiele:

  • product_of_odds(1)1
  • product_of_odds(3)1 * 3 = 3
  • product_of_odds(5)1 * 3 * 5 = 15
  • product_of_odds(7)1 * 3 * 5 * 7 = 105

Hinweise

    Aufgabe

    Doppel-Rekursion: Treppenaufstieg

    3 Punkte

    Du steigst eine Treppe mit n Stufen hoch. In jedem Schritt kannst du eine oder zwei Stufen auf einmal nehmen. Schreibe eine rekursive Funktion stair_ways(n), die zurückgibt, wie viele verschiedene Wege es gibt, ganz oben anzukommen.

    Anforderungen:

    • n ist eine nicht-negative ganze Zahl.
    • Zwei Basisfälle: n = 0 (du bist schon oben → genau 1 Weg) und n = 1 (genau 1 Weg, einen Einer-Schritt).
    • Rekursivfall: stair_ways(n) = stair_ways(n-1) + stair_ways(n-2). (Erkennst du es wieder?)

    Beispiele:

    • stair_ways(0)1
    • stair_ways(1)1
    • stair_ways(2)2 (1+1 oder 2)
    • stair_ways(3)3 (1+1+1, 1+2, 2+1)
    • stair_ways(4)5

    Hinweise

      Aufgabe

      Higher-Order: Filter + Map auf Zahlen

      2 Punkte

      Schreibe eine einzige Codezeile als Funktion even_squares(numbers), die aus der Liste numbers alle geraden Zahlen quadriert zurückgibt — als list.

      Du musst beides verwenden: map und filter. Verzichte auf eine for-Schleife oder eine List Comprehension.

      Beispiele:

      • even_squares([1, 2, 3, 4, 5, 6])[4, 16, 36]
      • even_squares([])[]
      • even_squares([7, 9, 11])[]

      Tipp: Lambdas und ein list(...) außen drum.

      Hinweise

        Aufgabe

        Set + Dict: einzigartige Wörter zählen

        3 Punkte

        Schreibe eine Funktion unique_word_counts(sentences), die aus einer Liste von Sätzen ein dict baut: für jedes eindeutige Wort zählt sie, in wie vielen Sätzen es vorkommt (nicht wie oft insgesamt).

        Anforderungen:

        • Vergleiche Wörter case-insensitiv"Hello" und "hello" zählen als dasselbe.
        • Splitte Sätze an Whitespace — sentence.split() reicht.
        • Kommt ein Wort im selben Satz mehrfach vor, zählt es trotzdem nur einmal für diesen Satz (deshalb das Set).

        Beispiele:

        unique_word_counts([
            "Hello world",
            "hello there",
            "Goodbye world",
        ])
        # → {"hello": 2, "world": 2, "there": 1, "goodbye": 1}
        

        Hinweise

          Übungsquiz

          Phase 4 / 4

          Teste dein Verständnis in 15 Minuten mit 6 Frage(n), direkt an den HSG-Quizstolperfallen ausgerichtet.

          Quiz starten