Aufgabe 05 - Rekursion III

Aufgabe 05 - Rekursion III

Worum geht es?

Gemischtes Training: viele kleine rekursive Funktionen, bei denen Sie Basisfall und Rekursionsschritt jedes Mal selbst finden müssen, dazu die Umwandlung zwischen Schleife und Rekursion in beide Richtungen und die Analyse einer fehlerhaften Rekursion (siehe Kapitel Rekursion). Rekursion wird durch Wiederholung zur Routine; diese dritte Übung schließt den Block ab.

Was Sie dafür brauchen

• Kapitel Rekursion vollständig; Aufgaben 03 und 04 abgeschlossen.
• Python, VS Code.

Welche Kompetenzen Sie erwerben und zeigen

• Sie formulieren Basisfall und Rekursionsschritt ohne Vorlage für neue Probleme.
• Sie behandeln Strings und Zahlen als rekursiv zerlegbare Strukturen.
• Sie erkennen fehlerhafte Rekursionen und begründen die Wahl zwischen Rekursion und Schleife.

Pädagogische Einordnung

• Reproduktion: eingeübte Rekursionsmuster auf sehr ähnliche Aufgaben anwenden (Teil A).
• Reorganisation und Transfer: Lösungen zwischen rekursiver und iterativer Form umformen, Fehlerbilder analysieren (Teile B und C).
• Reflexion, Problemlösung und Urteilsbildung: ein kombinatorisches Problem selbstständig rekursiv lösen und Entwurfsregeln ableiten (Teil D).

Arbeitsaufträge

Die Übung ist auf etwa zwei Stunden ausgelegt. Alle Funktionen der Teile A bis C kommen ohne Schleifen aus; Teil D ist der Expertenteil.

Teil A - Trainingslauf

Implementieren Sie rekursiv, jeweils mit zwei Testaufrufen und einem Kommentar, der Basisfall und Rekursionsschritt benennt:

1. digit_sum(n): Quersumme; 4712 ergibt 14. Hilfsmittel: % 10 für die letzte Ziffer, // 10 für den Rest.
2. count_char(char, text): wie oft kommt das Zeichen im Text vor?
3. repeat(text, n): hängt den Text n-mal aneinander, ohne den *-Operator für Strings zu verwenden.

Teil B - Strings rückwärts und vorwärts

1. reverse(text): aus "stack" wird "kcats". Ansatz: erstes Zeichen ans Ende des umgedrehten Rests.
2. is_palindrome(text): erst die äußeren Zeichen vergleichen, dann innen weiterprüfen.
3. power(base, exponent): Potenz ohne **, nur mit Multiplikation und Rekursion (Exponent ist eine nicht negative Ganzzahl).
4. Für eine der drei Funktionen: Expandieren Sie einen Aufruf schriftlich von Hand, wie in Aufgabe 03 geübt.

Teil C - Umformen und Fehler finden

1. Gegeben ist diese Schleifenlösung; formen Sie sie in eine rekursive Funktion um:

   def list_sum(values):
       total = 0
       for value in values:
           total += value
       return total

2. Formen Sie umgekehrt Ihre rekursive digit_sum aus Teil A in eine Schleifenversion um.

3. Die folgende Funktion stürzt bei manchen Eingaben ab:

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

   Für welche Eingaben genau? Begründen Sie, beheben Sie das Problem und formulieren Sie daraus eine allgemeine Regel: Was muss der Rekursionsschritt gegenüber dem Basisfall garantieren?

Teil D - Expertenteil: Alle Möglichkeiten aufzählen

Kombinatorische Aufzählungen sind ohne Rekursion kaum sauber zu lösen; mit ihr schon.

1. binary_strings(n): liefert eine Liste aller Bitfolgen der Länge n; binary_strings(2) ergibt ["00", "01", "10", "11"]. Ansatz: Jede Folge der Länge n ist "0" oder "1" plus eine Folge der Länge n-1.
2. permutations(text): liefert alle Anordnungen der Zeichen; permutations("abc") ergibt sechs Strings. Ansatz: Jedes Zeichen einmal nach vorne nehmen, Rest permutieren.
3. Wie viele Ergebnisse liefern binary_strings(n) und permutations(text) allgemein? Geben Sie beide Formeln an und prüfen Sie sie mit len() für zwei Werte.
4. Beurteilen Sie in zwei Sätzen, warum diese Aufgabenklasse als rekursionstypisch gilt, während die Aufgaben aus Teil A auch iterativ gut lösbar sind.

Wissenscheck

1. Nennen Sie die drei Fragen, mit denen Sie jede eigene rekursive Funktion vor dem ersten Start prüfen.
2. Was ist der Basisfall von reverse, und warum genügt “leerer String” allein nicht immer? (Denken Sie an Strings der Länge 1.)
3. Warum stürzt buggy(3) ab, buggy(4) aber nicht?
4. Eine Aufgabe lautet “summiere die Zahlen einer flachen Liste”. Rekursion oder Schleife? Begründen Sie in einem Satz.
5. Wie viele Permutationen hat ein Wort mit 10 verschiedenen Zeichen? Was sagt diese Zahl über die Laufzeit von permutations aus?

Abgabe

recursion3.py mit allen Funktionen, Kommentaren, der Handexpansion aus Teil B und der Regel aus Teil C.