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

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 bearbeiten. 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, wie dies funktioniert:

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 sich die Funktion 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, das Arbeiten mit Argumenten, das Verarbeiten von Rückgabewerten sowie das Erstellen flexibler und effizienter Codes mithilfe von Rekursion und Lambda-Ausdrücken.

Erkunden, was Funktionen sind und warum sie in Python unverzichtbar sind. Lernen, 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 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.

Entdecken Sie, wie Rückgabewerte die Ausgabe einer Funktion repräsentieren. 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?

Ein einfaches Beispiel

Der Aufruf-Stack

Lösung