![[Formales]] ![[05_rekursionen__735948278.png]] > [!TLDR] > Rekursion – eine Funktion, die sich selbst aufruft – ist in vielen typischen “Schulbüchern” oft anhand von Fibonacci oder Fakultät erklärt. > > In der Praxis begegnen uns Rekursionen aber auch bei der Verarbeitung hierarchischer Daten, etwa: > - Baumstrukturen (z. B. Ordner mit Unterordnern) > - Verschachtelte JSON-/XML-Daten (z. B. Daten mit Unterobjekten) > - Aggregationen in einer verschachtelten Python-Struktur (z. B. dict in dict in dict) > > Da unser Datensatz apotheken_daten.csv nicht hierarchisch aufgebaut ist, können wir uns den praktischen Nutzen erschließen, indem wir künstlich eine verschachtelte Struktur aufbauen. > > Anschließend werden wir diese rekursiv traversieren und/oder statistische Auswertungen vornehmen. So kann man das Prinzip der Rekursion praxisnah üben, auch wenn es nicht die häufigste Alltagsaufgabe in CSV-Daten ist. ![[00 Python 101 Syntax#05 Rekursionen]] # Beispielaufbau: Verschachteltes Dictionary > [!TLDR] > Wir erstellen ein verschachteltes Dictionary, das ungefähr so aussieht: > > { > "Schmerzmittel": { > "Bayer": \[Liste von Einträgen], > "Ratiopharm": \[Liste von Einträgen] > }, > "Antibiotikum": { > "Pfizer": \[Liste von Einträgen], > ... > }, > ... > } > > Jeder Value kann wiederum ein Dictionary sein (nach Kategorie -> Hersteller) oder eine Liste, in der wir die eigentlichen Medikament-Infos speichern. > > Eine rekursive Funktion kann diese Struktur durchsuchen und z. B. Summen berechnen. > [!QUOTE] Verschachtelte Struktur aufbauen und rekursiv traversieren > > [!NOTE] Ziel > > Wir möchten alle Verkaufszahlen summieren, sortiert nach Kategorie und Hersteller. > > > [!NOTE] Schritte > > 1. Komplette CSV lesen (oder meinetwegen 20 Zeilen, wenn es reicht). > > 2. Für jede Zeile: > > - Kategorie (parts\[1]), Hersteller (parts\[2] oder wo immer der Hersteller steht; Achtung: in unserem Datensatz kann das an Index 2 oder 3 sein – je nach Struktur. Schau in die Headerzeile!), Verkaufszahlen (parts\[8]). > > - In einem verschachtelten Dictionary ablegen, z. B. nested_dict\[category]\[manufacturer] als Liste, in die wir die Verkaufszahlen anhängen. > > 1. Rekursive Funktion recursive_sum(d), die: > > - Prüft, ob d eine Liste ist => dann summiert sie deren Verkaufszahlen. > > - Oder ob d ein Dictionary ist => dann für jeden Key rekursiv recursive_sum(d\[key]). > > - Teil-Ergebnisse aufsummiert und zurückgibt. ```python # rec_nested_task1.py filename = "apotheken_daten.csv" def recursive_sum(structure): """ Summiert alle Verkaufszahlen in einer verschachtelten Struktur: - Falls structure eine Liste mit Zahlen ist, summiere sie. - Falls structure ein dict ist, rufe recursive_sum() auf alle Values auf. """ if isinstance(structure, list): # Dann gehen wir davon aus, es ist eine Liste von Verkaufszahlen return sum(structure) elif isinstance(structure, dict): total = 0 for key, value in structure.items(): total += recursive_sum(value) # rekursiver Aufruf return total else: # Falls wir hier irgendetwas Unerwartetes haben return 0 # 1) Verschachtelte Struktur aufbauen nested_data = {} # "Kategorie" -> { "Hersteller" -> [Liste von Verkaufszahlen] } with open(filename, "r", encoding="utf-8") as f: header = f.readline().strip().split(";") # Im Original-Datensatz muss man ggf. die Indizes aus dem Header ermitteln. # Zur Vereinfachung gehen wir davon aus: # Kategorie = parts[1], Hersteller = parts[2], Verkaufszahlen = parts[8] # (Bitte anpassen, falls abweichend!) for _ in range(20): # Wir lesen hier beispielhaft 20 Zeilen line = f.readline() if not line: break # Datei zu Ende parts = line.strip().split(";") if len(parts) < 9: continue # Zeile unbrauchbar cat = parts[1] manuf = parts[2] sales_str = parts[8] sales = int(sales_str) if sales_str.isdigit() else 0 # Dictionary-Einträge prüfen und erzeugen if cat not in nested_data: nested_data[cat] = {} if manuf not in nested_data[cat]: nested_data[cat][manuf] = [] nested_data[cat][manuf].append(sales) # 2) Rekursive Summierung total_sales = recursive_sum(nested_data) print("Gesamte Verkaufszahlen (rekursiv ermittelt):", total_sales) ``` > [!NOTE] Ablauf > 1. Im Dictionary nested_data sammeln wir alle Verkaufszahlen pro Kategorie und Hersteller in Listen. > 2. Die Funktion recursive_sum() prüft: > - Ist structure eine Liste? Dann summiert sie die Elemente. > - Ist structure ein dict? Dann ruft sie sich für jedes Value rekursiv auf. > 1. So haben wir am Ende eine Summierung aller Verkaufszahlen, ohne Schleifen über Hersteller-Ebenen explizit codieren zu müssen – denn das geschieht automatisch durch die Rekursion. # Rekursives Ausdrucken aller Einträge > [!TLDR] > Wenn wir nicht nur summieren, sondern z. B. alle Einträge in einer hierarchischen Struktur (z. B. Kategorie -> Hersteller -> Liste von Verkaufszahlen) ausgeben wollen, kann eine ähnliche Rekursionsidee helfen: ```python def recursive_print(structure, indent=0): # Falls dict: Keys durchgehen if isinstance(structure, dict): for key, value in structure.items(): print(" " * indent + f"[{key}]") recursive_print(value, indent + 1) elif isinstance(structure, list): for item in structure: print(" " * indent + str(item)) else: # Unerwarteter Datentyp print(" " * indent + str(structure)) ``` Aufruf z. B. recursive_print(nested_data) => Dann bekommst Du eine baumartige Ausgabe aller Kategorien, Hersteller und deren Verkaufszahlen. # Rekursionsübungen, 2 Varianten > [!TLDR] > Nun ein paar praxisnähere Rekursionsübungen, die an das obige Beispiel anknüpfen und doch etwas eigenständig sind. > [!SUMMARY] Rekursiver Durchschnittswert (z. B. für Preis) pro Kategorie > 1. Baue ein verschachteltes Dictionary nested_prices, in dem Du Kategorie -> Hersteller -> Liste von Preisen ablegst (statt Verkaufszahlen). > - Lies dazu 30 Zeilen (oder je nach Zeit). > - Konvertiere Spalte „Preis (€)“ (Index ~13) in float, falls leer = 0.0. > 2. Definiere eine Funktion recursive_sum_and_count(structure), die bei Listen die Summe aller Elemente und die Anzahl zurückgibt, bei Dictionary rekursiv summiert & zählt. > - Rückgabeformat z. B. (gesamtsumme, anzahl). > 3. Errechne am Ende den globalen Durchschnitt (sum / anzahl), also über alle Kategorien und Hersteller. > 4. (Optional) Wer Lust hat, kann zusätzlich für jede Kategorie einzeln den Durchschnitt ermitteln, indem man pro Kategorie den rekursiven Aufruf ausführt. > [!SUMMARY]- Beispielhafte Lösung > ```python > # rec_prices_task.py > > def recursive_sum_and_count(data): > """ > Gibt (summe, anzahl) zurück. > """ > if isinstance(data, list): > return (sum(data), len(data)) > elif isinstance(data, dict): > total_sum = 0 > total_count = 0 > for key, value in data.items(): > s, c = recursive_sum_and_count(value) > total_sum += s > total_count += c > return (total_sum, total_count) > else: > return (0, 0) > > filename = "apotheken_daten.csv" > nested_prices = {} > > with open(filename, "r", encoding="utf-8") as f: > header = f.readline().split(";") > > for _ in range(30): > line = f.readline() > if not line: > break > > parts = line.strip().split(";") > cat = parts[1] > manuf = parts[2] > price_str = parts[13] > price = float(price_str) if price_str else 0.0 > > if cat not in nested_prices: > nested_prices[cat] = {} > if manuf not in nested_prices[cat]: > nested_prices[cat][manuf] = [] > > nested_prices[cat][manuf].append(price) > > # Rekursiver Summen- und Count-Aufruf > total_s, total_c = recursive_sum_and_count(nested_prices) > if total_c > 0: > overall_avg = total_s / total_c > print("Globaler Durchschnittspreis:", round(overall_avg, 2)) > ``` Je nach Übungstiefe kann man dann noch pro Kategorie einzeln die Funktion aufrufen – also recursive_sum_and_count(nested_prices\["Schmerzmittel"]) usw. – und pro Kategorie den Durchschnitt drucken.) --- > [!SUMMARY] Rekursives Suchen nach einem bestimmten Hersteller > 1. Erstelle ein Dictionary nested_meds, in dem Du Kategorie -> Hersteller -> Liste von Medikamentennamen ablegst (Spalte 0). > 2. Schreibe eine Funktion recursive_search(data, target_manufacturer), die: > - Bei einem dict die Keys durchgeht: > - Wenn der Key == target_manufacturer ist, gibt sie die Liste (oder den Teilbaum) zurück. > - Sonst ruft sie sich bei den Values rekursiv auf. > - Bei einer Liste: tut nichts (oder gibt None zurück). > - Falls der Hersteller nicht gefunden wird, am Ende None. > 3. Teste die Funktion, indem Du z. B. recursive_search(nested_meds, "Bayer") aufrufst und schaust, welche Medikamentenliste Du zurückbekommst. > > Das ist ein etwas realitätsnäheres Beispiel, bei dem man in einer verschachtelten Struktur per Rekursion gezielt nach einem bestimmten Key suchen kann. > [!SUMMARY]- Beispielhafte Lösung > ```python > # rec_search_task.py > > def recursive_search(data, target_manufacturer): > """ > Durchsucht data nach target_manufacturer. > Falls gefunden, gebe die Liste von Medikamentennamen zurück. > Sonst None. > """ > if isinstance(data, dict): > for k, v in data.items(): > if k == target_manufacturer: > # v könnte unsere Medikamentenliste sein > return v > else: > # Rekursiv tiefer suchen > result = recursive_search(v, target_manufacturer) > if result is not None: > return result > # Falls in keinem Zweig gefunden: > return None > else: > # Falls es eine Liste oder was anderes ist, haben wir hier keinen Treffer > return None > > filename = "apotheken_daten.csv" > nested_meds = {} > > with open(filename, "r", encoding="utf-8") as f: > header = f.readline() > > for _ in range(30): > line = f.readline() > if not line: > break > parts = line.strip().split(";") > cat = parts[1] > manuf = parts[2] > med_name = parts[0] > > if cat not in nested_meds: > nested_meds[cat] = {} > if manuf not in nested_meds[cat]: > nested_meds[cat][manuf] = [] > > nested_meds[cat][manuf].append(med_name) > > res = recursive_search(nested_meds, "Bayer") > if res is None: > print("Hersteller 'Bayer' nicht gefunden.") > else: > print("Gefundene Medikamentennamen für 'Bayer':", res) > ``` > [!QUESTION] Wann ist Rekursion in solchen CSV-Beispielen hilfreich? > - Hierarchische Kategorisierungen (Kategorie -> Unterkategorie -> Unter-Unterkategorie) sind in manchen Datensätzen wichtig (z. B. wenn wir an Produkt-Hierarchien denken: „Arznei -> Schmerzmittel -> Ibuprofen“). > - Aufbau einer Verschachtelung (z. B. Du gruppierst nach 2 oder 3 Merkmalen). Wenn Du diese Struktur verarbeiten willst (z. B. summieren, durchsuchen, ausgeben), kann eine rekursive Funktion bequemer sein als verschachtelte Schleifen. > - Generische Operationen (Summe, Suche), die unabhängig davon sind, ob Du eine Ebene oder zehn Ebenen hast. > > In der Realität lösen wir solche Aufgaben oft iterativ oder nutzen Bibliotheken (z. B. pandas mit groupby). Aber das Prinzip der Rekursion bleibt wertvoll, wenn man flexibel tief verschachtelte Daten durchlaufen muss. # Fazit > [!SUMMARY] > Damit habt Ihr zwei rekursive Anwendungsszenarien für Euren Apotheken-Datensatz gesehen, die etwas praxisnäher sind als „Fibonacci“: > 1. Rekursives Summieren oder Durchschnitt berechnen in einer mehrstufigen (Kategorie -> Hersteller -> Daten) Struktur. > 2. Rekursives Suchen nach einem bestimmten Hersteller in dieser Struktur. # Quiz ## 1) Multiple Choice > [!QUESTION] Was versteht man unter Rekursion in der Programmierung? > 1. [ ] Eine Funktion, die nur einmal ausgeführt werden kann > 2. [ ] Eine Funktion, die sich innerhalb einer Schleife selbst aufruft > 3. [ ] Eine Funktion, die sich selbst aufruft > 4. [ ] Eine Methode, die ausschließlich mit Listen arbeitet > [!SUCCESS]- > 3 > Eine rekursive Funktion ruft sich selbst innerhalb ihres eigenen Rumpfs auf. ## 2) True or False > [!QUESTION] Rekursive Funktionen benötigen meist eine Abbruchbedingung, damit sie nicht endlos weiterlaufen. > - [ ] Richtig > - [ ] Falsch > [!SUCCESS]- > “Richtig” ## 3) Multiple Choice > [!QUESTION] Welches klassische Beispiel wird oft als Einführung in die Rekursion verwendet? > 1. [ ] Fibonacci-Zahlen > 2. [ ] Bubble Sort > 3. [ ] Quicksort > 4. [ ] Matrixmultiplikation > [!SUCCESS]- > 1 > Das Fibonacci-Beispiel wird sehr häufig herangezogen, um Rekursion aufzuzeigen. ## 4) Multiple Choice > [!QUESTION] In welchem Fall kann Rekursion bei CSV-Daten sinnvoll sein? > 1. [ ] Wenn die CSV-Daten hierarchisch verschachtelt sind > 2. [ ] Bei linearen Tabellen ohne jegliche Gliederung > 3. [ ] Grundsätzlich nie, da CSV immer flach strukturiert ist > 4. [ ] Nur, wenn keine Schleifen verwendet werden dürfen > [!SUCCESS]- > 1 > Bei hierarchischen oder verschachtelten Strukturen, die man künstlich aus einer CSV ableitet, kann Rekursion sinnvoll sein. ## 5) True or False > [!QUESTION] ‘isinstance(d, dict)’ kann in einer rekursiven Funktion genutzt werden, um zu prüfen, ob ‘d’ ein Dictionary ist und man tiefer auf dessen Keys/Values zugreifen muss. > - [ ] Richtig > - [ ] Falsch > [!SUCCESS]- > “Richtig” ## 6) True or False > [!QUESTION] In Python ist Rekursion die einzige Möglichkeit, eine Summe über eine verschachtelte Datenstruktur zu bilden. > - [ ] Richtig > - [ ] Falsch > [!SUCCESS]- > “Falsch” > ## 7) Multiple Choice > [!QUESTION] Warum sollte man in einer rekursiven Funktion eine Abbruchbedingung definieren? > 1. [ ] Damit die Funktion nach dem ersten Aufruf stoppt > 2. [ ] Damit man sie nur einmal pro Programmstart nutzen kann > 3. [ ] Um endlose Aufrufe zu verhindern > 4. [ ] Abbruchbedingungen sind nicht nötig > [!SUCCESS]- > 3 > Ohne Abbruchbedingung würde die Funktion sich potenziell endlos selbst aufrufen. ## 8) Multiple Choice > [!QUESTION] Wie kann man rekursiv eine Summe aller Werte in einem verschachtelten Dictionary berechnen? > 1. [ ] Mit ‘sum()’ direkt auf dem Dictionary > 2. [ ] Indem man bei jedem dict-Value wieder die Funktion aufruft, bis man Listen erreicht > 3. [ ] Durch for-Schleifen ohne Funktion > 4. [ ] Nur durch Nutzung von globalen Variablen > [!SUCCESS]- > 2 > Man ruft rekursiv dieselbe Funktion auf, bis man auf Listen (die Werteebene) stößt und summieren kann. ## 9) True or False > [!QUESTION] Die Python-Standardbibliothek stellt keinen eingebauten Mechanismus bereit, der rekursiv alle Werte in einem verschachtelten Dictionary summiert. > - [ ] Richtig > - [ ] Falsch > [!SUCCESS]- > “Richtig” ## 10) Multiple Choice > [!QUESTION] Welche Datenstruktur wurde im Beispiel genutzt, um verschachtelte Daten für Hersteller und Kategorien aufzubauen? > 1. [ ] Eine Liste aus Listen > 2. [ ] Ein verschachteltes Dictionary > 3. [ ] Eine CSV-Datei direkt > 4. [ ] Ein Tupel aus Integers > [!SUCCESS]- > 2 > Im Beispiel wurde ein Dictionary innerhalb eines Dictionaries erzeugt (z.B. nach Kategorie und Hersteller). ## 11) True or False > [!QUESTION] Beim Traversieren eines verschachtelten Dictionaries prüft man im rekursiven Ansatz oft zuerst, ob ein Eintrag ein Dictionary oder eine Liste ist. > - [ ] Richtig > - [ ] Falsch > [!SUCCESS]- > “Richtig” ## 12) Multiple Choice > [!QUESTION] Wozu kann eine rekursive Funktion ‘recursive_search’ dienen? > 1. [ ] Um in einer flachen Liste alle Elemente zu finden > 2. [ ] Um eine Datei zu öffnen > 3. [ ] Um einen bestimmten Key in einer mehrstufigen Datenstruktur zu suchen > 4. [ ] Nur um JSON zu verarbeiten, nicht für Dictionaries > [!SUCCESS]- > 3 > Sie kann verschachtelte Ebenen durchlaufen, um den gesuchten Key oder Wert zu finden. ## 13) True or False > [!QUESTION] Bei Rekursion in Python kann ein zu tiefer Aufruf zu einem ‘RecursionError’ führen, wenn das ‘recursion limit’ überschritten wird. > - [ ] Richtig > - [ ] Falsch > [!SUCCESS]- > “Richtig” ## 14) Multiple Choice > [!QUESTION] Warum könnte man anstelle von Rekursion in Python auch andere Lösungen (z.B. Iteration) bevorzugen? > 1. [ ] Rekursion ist in Python verboten > 2. [ ] Iteration kann häufig effizienter sein und vermeidet mögliche Stack-Limit-Probleme > 3. [ ] Rekursion funktioniert nur mit Lambda-Funktionen > 4. [ ] Iteration ist in Python nicht implementiert > [!SUCCESS]- > 2 > Iterative Lösungen vermeiden zu tiefe Funktionsaufrufe und sind oft effizienter in Python.