Summary  
This chapter covers recursion, detailing how to define a base case and a recursive case so a function calls itself with simpler inputs, and explains how the call stack manages these nested calls.  

General domain of usage  
Processing tree data structures

**Rekursion** ist eine Programmiertechnik, **bei der eine Funktion sich selbst aufruft**, um ein Problem in kleinere Teile zu zerlegen. Besonders nützlich bei Problemen mit wiederholender Struktur oder natürlichen Teilproblemen.

Definition

Die Schlüsselelemente der **Rekursion** sind:
- **Abbruchbedingung**: die Bedingung, die die Rekursion stoppt;
- **Rekursiver Fall**: der Teil, in dem die Funktion sich selbst mit einer einfacheren Eingabe aufruft.

### Warum Rekursion verwenden?

Einige Probleme lassen sich auf natürliche Weise in kleinere Teilprobleme zerlegen. Rekursion bietet eine übersichtliche und elegante Möglichkeit, diese zu lösen, indem eine Funktion sich selbst für die einfacheren Fälle aufruft. Häufig verwendet bei Aufgaben wie der Verarbeitung von Bäumen, der Pfadsuche oder dem Zerlegen von Strukturen (z. B. Listen, Zeichenketten).

def print_message(message, times):
    if times > 0:    # Base case: stop when times is 0
        print(message)
        print_message(message, times - 1)    # Recursive case

# Function call
print_message("Hello, Recursion!", 3)

Gehe **Schritt für Schritt** vor, um zu verstehen, wie dieses rekursive Programm funktioniert:

1. **Bedingungsprüfung:** Wenn `times > 0`, wird die Funktion ausgeführt. In diesem Fall ist `times = 3`, daher ist die Bedingung erfüllt;
2. **Nachricht ausgeben:** Die Funktion gibt `"Hello, Recursion!"` aus;
3. **Rekursiver Aufruf:** Die Funktion ruft sich selbst mit `times - 1` auf;
4. **Wiederholung:** Dieser Vorgang wiederholt sich, bis `times` den Wert 0 erreicht;
5. **Beendigung:** Wenn die Bedingung `times > 0` nicht mehr erfüllt ist, endet die Rekursion und das Programm wird abgeschlossen.

**Ergebnis**: Die Nachricht `"Hello, Recursion!"` wird __dreimal__ ausgegeben.

### Ablauf verstehen:
Jedes Mal, wenn die Funktion sich selbst aufruft, wird ein neuer Frame zum **Call Stack** (eine Speicherstruktur, die aktive Funktionsaufrufe verwaltet) hinzugefügt. Die Funktion ruft sich mit einem kleineren Wert für `times` erneut auf. Sobald der Basisfall (`times == 0`) erreicht ist, stoppt sie. Danach wird jeder vorherige Aufruf nacheinander in umgekehrter Reihenfolge abgeschlossen. Dieses Backtracking-Verhalten ist grundlegend für die Funktionsweise von Rekursion.

import unittest

def _dynamic_test(test_case, condition, success_message, failure_message):
    if condition:
        test_case._testMethodName = success_message
        test_case.assertTrue(True, success_message)
    else:
        test_case._testMethodName = failure_message
        test_case.fail(failure_message)

class TestFormatPhoneNumber(unittest.TestCase):
    def test_standard_format(self):
        """Checks that the function correctly formats a standard phone number."""
        try:
            import user_code
            result = user_code.format_phone_number("(123) 456-7890")
            expected_output = "1234567890"
            condition = result == expected_output
            failure_message = f"For input `(123) 456-7890`, expected `{expected_output}`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `format_phone_number` is not defined."

        _dynamic_test(self, condition, "The function correctly formats a standard phone number.", failure_message)

    def test_number_with_country_code(self):
        """Checks that the function correctly handles a phone number with a country code."""
        try:
            import user_code
            result = user_code.format_phone_number("  +1-800-555-0199  ")
            expected_output = "18005550199"
            condition = result == expected_output
            failure_message = f"For input `  +1-800-555-0199  `, expected `{expected_output}`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `format_phone_number` is not defined."

        _dynamic_test(self, condition, "The function correctly handles a phone number with a country code.", failure_message)

    def test_number_with_dots(self):
        """Checks that the function correctly handles a phone number with dots."""
        try:
            import user_code
            result = user_code.format_phone_number("987.654.3210")
            expected_output = "9876543210"
            condition = result == expected_output
            failure_message = f"For input `987.654.3210`, expected `{expected_output}`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `format_phone_number` is not defined."

        _dynamic_test(self, condition, "The function correctly handles a phone number with dots.", failure_message)

    def test_empty_string(self):
        """Checks that the function returns an empty string for an empty input."""
        try:
            import user_code
            result = user_code.format_phone_number("")
            expected_output = ""
            condition = result == expected_output
            failure_message = f"For input `''`, expected `{expected_output}`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `format_phone_number` is not defined."

        _dynamic_test(self, condition, "The function correctly handles an empty string.", failure_message)

    def test_only_special_characters(self):
        """Checks that the function returns an empty string when input contains only special characters."""
        try:
            import user_code
            result = user_code.format_phone_number("!@#$%^&*()")
            expected_output = ""
            condition = result == expected_output
            failure_message = f"For input `'!@#$%^&*()'`, expected `{expected_output}`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `format_phone_number` is not defined."

        _dynamic_test(self, condition, "The function correctly handles input with only special characters.", failure_message)

if __name__ == '__main__':
    unittest.main()

test_main.py

Erwerben Sie ein fundiertes Verständnis dafür, wie Funktionen die Python-Programmierung prägen. Beherrschen Sie das Definieren und Aufrufen von Funktionen, das Arbeiten mit Argumenten, das Verwalten von Rückgabewerten sowie das Erstellen flexibler und effizienter Codes mithilfe von Rekursion und Lambda-Ausdrücken.

Erkunden Sie, was Funktionen sind und warum sie in Python unverzichtbar sind. Lernen Sie, wie man Funktionen erstellt, Argumente definiert, Rückgabewerte verarbeitet und eingebaute Funktionen effektiv nutzt.

Erfahren Sie, wie Positions- und optionale Argumente in Python funktionieren. Entwicklung anpassungsfähiger Funktionen, die verschiedene Eingaben verarbeiten und die Flexibilität Ihres Codes verbessern.

Verstehen, wie mit beliebigen und Schlüsselwortargumenten gearbeitet wird, um variable Eingabegrößen zu verarbeiten. Erfahren, wie diese Techniken Ihre Funktionen dynamischer und organisierter machen.

Erfahren Sie, wie Rückgabewerte die Ausgabe einer Funktion darstellen. Lernen Sie, einzelne oder mehrere Werte zurückzugeben, None zu verwenden und Generatoren für eine fortgeschrittene Steuerung des Datenflusses zu nutzen.

Erschließen Sie fortgeschrittene Funktionskonzepte mit Rekursion und Lambda-Funktionen. Lernen Sie, wie Rekursion wiederkehrende Probleme löst und wie Lambda-Ausdrücke prägnante, einzeilige Funktionen erstellen.

Rekursion

Warum Rekursion verwenden?

Ablauf verstehen:

Lösung