Summary
Recursion is a technique where a function defines a base case to stop and a recursive case that calls itself with simpler input to solve problems.

General domain of usage
processing trees

Eine **rekursive Funktion** ist eine Funktion, die sich selbst aufruft, um ein Problem zu lösen, indem sie es in kleinere, einfachere Teile zerlegt.



Definition

Die Schlüsselelemente der Rekursion sind:
- **Basisfall**: 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 aufruft, um die einfacheren Fälle zu behandeln. Sie wird häufig bei Aufgaben wie der Verarbeitung von Bäumen, der Erkundung von Pfaden oder dem Zerlegen von Strukturen (z. B. Listen, Zeichenketten) verwendet.



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

print_message('Hello, Recursion!', 3)

Schrittweise Erklärung des Ablaufs:

1. `times = 3` → Bedingung ist erfüllt, Nachricht wird ausgegeben, Aufruf von `print_message(message, 2)`;
2. `times = 2` → Bedingung ist erfüllt, Nachricht wird ausgegeben, Aufruf von `print_message(message, 1)`;
3. `times = 1` → Bedingung ist erfüllt, Nachricht wird ausgegeben, Aufruf von `print_message(message, 0)`;
4. `times = 0` → Bedingung ist nicht erfüllt, Rekursion endet.

**Ergebnis**: Die Nachricht wird dreimal ausgegeben.



## Der Aufruf-Stack

Jedes Mal, wenn die Funktion sich selbst aufruft, wird ein neuer Frame zum **Aufruf-Stack** hinzugefügt – eine Speicherstruktur, die aktive Funktionsaufrufe verfolgt. Sobald der Basisfall erreicht ist, wird jeder vorherige Aufruf nacheinander in umgekehrter Reihenfolge abgeschlossen.

Jede rekursive Funktion muss einen Basisfall haben. Ohne diesen ruft die Funktion sich unendlich oft selbst auf und verursacht einen `RecursionError`.

Hinweis

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 TestListSum(unittest.TestCase):

    def test_list_sum_basic(self):
        import user_code
        try:
            result = user_code.list_sum([1, 2, 3, 4, 5])
            expected = 15
            condition = result == expected
            failure_message = f"Expected `{expected}` for `[1, 2, 3, 4, 5]`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, f"The `list_sum` returns `15` for `[1, 2, 3, 4, 5]`.", failure_message)

    def test_list_sum_another_list(self):
        import user_code
        try:
            result = user_code.list_sum([10, 20, 30])
            expected = 60
            condition = result == expected
            failure_message = f"Expected `{expected}` for `[10, 20, 30]`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, f"The `list_sum` returns `60` for `[10, 20, 30]`.", failure_message)

    def test_list_sum_empty(self):
        import user_code
        try:
            result = user_code.list_sum([])
            expected = 0
            condition = result == expected
            failure_message = f"Expected `{expected}` for an empty list, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, "The `list_sum` correctly returns `0` for an empty list.", failure_message)

    def test_recursion_used(self):
        import user_code
        import inspect
        try:
            source = inspect.getsource(user_code.list_sum)
            condition = "list_sum(" in source.split("def list_sum")[1]
            failure_message = "Expected `list_sum` to call itself recursively."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, "The `list_sum` function uses recursion.", 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, den Umgang mit Argumenten, das Verarbeiten von Rückgabewerten sowie das Erstellen flexibler und effizienter Codestrukturen mithilfe von Rekursion und Lambda-Ausdrücken.

Erkunden Sie, was Funktionen sind und warum sie in Python unverzichtbar sind. Erfahren Sie, wie Funktionen erstellt werden, wie Argumente definiert werden, wie Rückgabewerte behandelt werden und wie eingebaute Funktionen effektiv genutzt werden.

Erfahren Sie, wie Positions- und optionale Argumente in Python funktionieren. Entwickeln Sie anpassungsfähige Funktionen, die verschiedene Eingaben verarbeiten und die Flexibilität Ihres Codes erhöhen.

Verstehen, wie mit beliebigen und Schlüsselwortargumenten gearbeitet wird, um variable Eingabegrößen zu verarbeiten.
Erlernen, wie diese Techniken Funktionen dynamischer und strukturierter gestalten.

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. Erfahren Sie, wie Rekursion wiederkehrende Probleme löst und wie Lambda-Ausdrücke prägnante, einzeilige Funktionen erstellen.

Rekursion

Warum Rekursion verwenden?

Ein einfaches Beispiel

Der Aufruf-Stack

Lösung