Lektion 04
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.
Bisher hast du Schleifen benutzt, um etwas mehrfach zu machen. In dieser Lektion lernst du drei Alternativen dazu, die in jeder professionellen Codebasis vorkommen:
map, filter, sorted und Lambdas. Eine Schleife in einer Zeile.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.
Eine rekursive Funktion ruft sich selbst auf. Damit das nicht ewig läuft, braucht sie zwingend zwei Teile:
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.
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.
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:
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.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…>.
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.
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:
if/else-Statement (aber der Ausdruck a if cond else b ist erlaubt).return — der Ausdruck ist die Rückgabe.def. Lambdas sind kein Selbstzweck.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?
xs[0]).in-Testen, mathematische Mengenoperationen.
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
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:
recursive_sum(2) → 2. Bei recursive_factorial(0) → 1.f(n) = n + f(n - schritt) oder f(n) = n * f(n - 1).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
number - 2, nicht number - 1.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.Assignment-Aufgabe 2
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
fibonacci: n == 0 → 0, n == 1 → 1. Direkt ohne Rekursion.f(n) = f(n - 2) + f(n - 1).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
fibonacci(1) → fibonacci(-1) + fibonacci(0) → endlose Rekursion.n. Die Funktion endet nicht für negative Eingaben. Wenn die Aufgabenstellung das nicht ausschließt, prüfe if n < 0: raise ValueError(...) ab.fibonacci(35) sekunden, fibonacci(50) minutenlang. Im Quiz nicht relevant, im echten Code: nutze functools.lru_cache oder Iteration.Assignment-Aufgabe 3
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
def (besser lesbar) oder als Lambda. Test sie zuerst mit einem Einzelwert.map anwenden — map(deine_funktion, deine_liste) liefert einen Iterator.list(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.map und filter. map transformiert alle Elemente, filter behält nur einige. Lies die Aufgabe genau.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
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
gross = ceil(len(students) / groups). In Python ohne math: (len(students) + groups - 1) // groups oder die Fallunterscheidung wie im HSG-Solution.students.extend(['__EMPTY__'] * (gross * groups - len(students))).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
students.extend(...) benutzt — das verändert die Eingabeliste! Sicherer ist eine Kopie (students = students + [...] statt students.extend(...)).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
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:
pip install streamlit ausführen.app.py mit ein paar st.write(...) Zeilen anlegen.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
cmd.exe — sonst findet pip die richtige Python-Installation nicht.streamlit run einen Port-Konflikt meldet, mit --server.port 8502 einen anderen Port nehmen.pip zur gleichen Python-Version gehört, die dein Jupyter benutzt.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.range(). Die Lösung ist rekursiv.n = 1 ist das Ergebnis 1.Beispiele:
product_of_odds(1) → 1product_of_odds(3) → 1 * 3 = 3product_of_odds(5) → 1 * 3 * 5 = 15product_of_odds(7) → 1 * 3 * 5 * 7 = 105Du 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.n = 0 (du bist schon oben → genau 1 Weg) und n = 1 (genau 1 Weg, einen Einer-Schritt).stair_ways(n) = stair_ways(n-1) + stair_ways(n-2). (Erkennst du es wieder?)Beispiele:
stair_ways(0) → 1stair_ways(1) → 1stair_ways(2) → 2 (1+1 oder 2)stair_ways(3) → 3 (1+1+1, 1+2, 2+1)stair_ways(4) → 5Schreibe 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.
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:
"Hello" und "hello" zählen als dasselbe.sentence.split() reicht.Beispiele:
unique_word_counts([
"Hello world",
"hello there",
"Goodbye world",
])
# → {"hello": 2, "world": 2, "there": 1, "goodbye": 1}
Teste dein Verständnis in 15 Minuten mit 6 Frage(n), direkt an den HSG-Quizstolperfallen ausgerichtet.
Quiz starten