Begriff der Rekursion

1.1 Definition der Rekursion und ihre grundlegenden Konzepte.

Rekursion ist, wenn etwas sich selbst immer und immer wieder tut. Stell dir vor, du hast eine Anleitung, und ein Teil dieser Anleitung sagt, der Anleitung selbst zu folgen. Es ist, als ob du den Befehl gibst, den Befehl selbst zu wiederholen.

Beispiele aus dem echten Leben:

Spiegel gegenüber voneinander:

Stell dir vor, du stehst zwischen zwei Spiegeln. Du siehst dein Spiegelbild und im Spiegelbild siehst du ebenfalls dein Spiegelbild und so weiter. Das ist ein Beispiel für Rekursion, weil jeder Spiegel das Spiegelbild des anderen Spiegels zeigt.

Matrjoschkas:

Eine Matrjoschka ist eine Puppe, in der sich eine andere Puppe befindet, und in dieser wiederum eine weitere und so weiter. Wenn du an der kleinsten Puppe angekommen bist, gibt es nichts mehr zu enthüllen. Das ist wie ein Basisfall in der Rekursion - der Moment, wenn man aufhören muss.

Pizzaschneiden:

Stell dir vor, du teilst eine Pizza in zwei Hälften. Dann nimmst du eine Hälfte und teilst sie wieder in zwei Hälften und machst so weiter, bis die Stücke zu klein sind, um sie weiter zu teilen. Das Teilen in Stücke ist ein rekursiver Prozess und der Moment, wenn du das Stück nicht weiter teilen kannst, ist der Basisfall.

Wichtig! Rekursion ist kein endloses Wiederholen eines Befehls, es geht vielmehr darum, dass bei der Aufteilung einer komplexen Aufgabe in Teile der Ansatz zur Lösung der Teile der Aufgabe dem zur Lösung der Gesamtaufgabe ähnelt.

Wie funktioniert das?

Um Rekursion zu verstehen, muss man zwei grundlegende Konzepte kennen:

• Basisfall: dies ist die Bedingung, bei der die Rekursion aufhört. Zum Beispiel ist beim Beispiel mit den Matrjoschkas der Basisfall, wenn du die kleinste Matrjoschka öffnest und nichts mehr darin ist.
• Rekursiver Fall: dies ist, wenn die Aufgabe mit kleineren Teilen wiederholt wird. Im Beispiel mit der Pizza teilst du ein Stück, und dann teilst du die Hälfte und so weiter.

Warum ist das nützlich?

Rekursion hilft, komplexe Aufgaben zu lösen, indem sie in einfachere Teile zerlegt werden. Anstatt die gesamte Aufgabe auf einmal zu lösen, löst du sie Stück für Stück.

Weitere Beispiele aus dem Leben:

Märchen im Märchen:

Stell dir vor, der Held eines Märchens erzählt ein weiteres Märchen, und der Held dieses Märchens beginnt, ein weiteres zu erzählen. Wenn eines der Märchen endet, kehrst du zum vorherigen Märchen zurück. Der Basisfall ist, wenn das letzte Märchen endet.

Rekursives Zeichnen:

Du zeichnest ein großes Dreieck und dann in jeder Ecke dieses Dreiecks ein kleines Dreieck und machst so weiter, bis die Dreiecke zu klein werden. Der Basisfall ist, wenn das Dreieck so klein wird, dass es nicht mehr gezeichnet werden kann.

1.2 Basisfall: Definition und Beispiele.

Der Basisfall ist die Bedingung, die die rekursiven Aufrufe beendet und der Funktion erlaubt, einen konkreten Wert zurückzugeben. Normalerweise ist dies die einfachste und offensichtlichste Lösung der Aufgabe, die keine weitere Rekursion erfordert.

Beispiele für den Basisfall:

Fakultät einer Zahl:

Die Fakultät einer Zahl n wird als F(n) == 1*2*3*…*n bezeichnet. Es ist auch offensichtlich, dass F(n) == n* F(n-1).

Basisfall: die Fakultät der Zahl 0 oder 1 ist gleich 1. F(0) == F(1)==1

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Basisfall
    else:
        return n * factorial(n - 1)
        

Fibonacci-Zahlen:

Fibonacci-Zahlen sind eine Sequenz: 1, 1, 2, 3, 5, 8, 13, … Wo jede nächste Zahl die Summe der beiden vorherigen ist. Für F(n) == F(n-1) + F(n-2)

Basisfall: die ersten beiden Fibonacci-Zahlen sind 1, also ist die "nullte" Fibonacci-Zahl gleich 0. Oder F(0) = 0 und F(1) = 1.

def fibonacci(n):
    if n == 0:
        return 0  # Basisfall
    elif n == 1:
        return 1  # Basisfall
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        

1.3 Rekursiver Fall: Definition und Beispiele

Der rekursive Fall ist der Teil der Funktion, der die Aufgabe löst, indem er sich selbst mit neuen Parametern aufruft, die die Lösung dem Basisfall annähern. Jeder rekursive Aufruf verringert oder verändert die Aufgabe, um letztendlich den Basisfall zu erreichen.

Beispiele für den rekursiven Fall:

Fakultät einer Zahl:

Der rekursive Fall: die Fakultät der Zahl n ist gleich n mal Fakultät der Zahl n-1.

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Basisfall
    else:
        return n * factorial(n - 1)  # Rekursiver Fall
        

Fibonacci-Zahlen:

Der rekursive Fall: F(n) ist die Summe von F(n-1) und F(n-2).

def fibonacci(n):
    if n == 0:
        return 0  # Basisfall
    elif n == 1:
        return 1  # Basisfall
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Rekursiver Fall
        

1.4 Beispiele rekursiver Algorithmen

1. Traversierung eines binären Baums:

Beispiel einer "in-order"-Traversierung.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)
        
# Beispiel der Nutzung:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder_traversal(root)
        

2. Suche des maximalen Elements in einer Liste:

def find_max(lst):
    if len(lst) == 1:
        return lst[0]  # Basisfall
    else:
        max_of_rest = find_max(lst[1:])  # Rekursiver Fall
        return max(lst[0], max_of_rest)
        
# Beispiel der Nutzung:
print(find_max([1, 5, 3, 9, 2]))  # Ausgabe: 9
        
        

3. Rekursive binäre Suche:

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # Basisfall: Element nicht gefunden
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # Basisfall: Element gefunden
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # Rekursiver Fall
    else:
        return binary_search(arr, target, left, mid - 1)  # Rekursiver Fall
        
# Beispiel der Nutzung:
arr = [1, 2, 3, 4, 5, 6, 7]
print(binary_search(arr, 5, 0, len(arr) - 1))  # Ausgabe: 4