Jede rekursive Funktion besteht aus zwei Hauptteilen:
Basisfall: Der Basisfall ist der Teil der Funktion, der ein einfaches Problem direkt löst. Der Basisfall wird verwendet, um die Rekursion zu beenden. Ohne einen Basisfall würde die Rekursion endlos fortgesetzt.
Rekursiver Fall: Der rekursive Fall ist der Teil der Funktion, der das Problem in kleinere Teilprobleme unterteilt und sich selbst darauf aufruft.
Problemstellung: Wir möchten die Fakultät einer nicht-negativen Ganzzahl n berechnen, d.h. das Produkt aller Ganzzahlen von 1 bis n.
Was ist der einfachste Fall? Die Fakultät von 0
ist 1
(definiert als 0!=1
).
Rekursive Regel: Wenn n=0
, dann ist das Ergebnis 1
.
Spielen Sie mit Beispielen herum: Nehmen Sie ein paar Zahlen und berechnen Sie die Fakultät manuell, z.B. 3!=3×2×1×1=6
.
Visualisieren: Sie können erkennen, dass die Fakultät von n
das Produkt von n
und der Fakultät von n−1
ist.
Da Sie beim Herumspielen gemerkt haben, dass die Fakultät von n
das Produkt von n
und der Fakultät von n−1
ist. Haben Sie gemerkt, dass die Fakultät von n
als n×(n−1)!
ausgedrückt werden kann.
Allgemeine Formel finden: Die rekursive Formel ist also: n!=n×(n−1)!
.
Kombinieren der Formel mit dem Base Case: Die endgültige rekursive Funktion kombiniert die allgemeine Formel mit dem Base Case.
Hier ist der Python-Code, der diese Schritte umsetzt:
def factorial(n): if n == 0: # Base Case return 1 else: return n * factorial(n - 1) # Rekursiver Fall
Problemstellung: Wir möchten alle möglichen Permutationen eines gegebenen Strings finden.
Was ist der einfachste Fall? Ein String mit einer Länge von 1 hat nur eine Permutation, nämlich sich selbst.
Rekursive Regel: Wenn die Länge des Strings gleich 1 ist, geben Sie eine Liste mit dem String selbst zurück.
Spielen Sie mit Beispielen herum: Nehmen Sie einen String wie AB
und finden Sie alle möglichen Kombinationen (AB
, BA
).
Visualisieren: Sie können erkennen, dass die Permutation eines Strings die Verbindung eines jeden Zeichens mit der Permutation des Restes des Strings ist.
Relation zwischen schwierigen und einfachen Fällen: Die Permutationen eines Strings können gefunden werden, indem jedes Zeichen im String als Startzeichen genommen und mit den Permutationen des restlichen Strings verbunden wird.
Allgemeine Formel finden: Die rekursive Formel besteht darin, jedes Zeichen des Strings als Startpunkt zu nehmen und mit den Permutationen des Rests des Strings zu kombinieren.
Kombinieren der Formel mit dem Base Case: Die endgültige rekursive Funktion kombiniert die allgemeine Formel mit dem Base Case. Hier ist der Python-Code, der diese Schritte umsetzt:
def permutations(s): if len(s) == 1: # Base Case return [s] perm_list = [] # Liste, um die Permutationen zu speichern for char in s: remaining_chars = s.replace(char, '', 1) remaining_permutations = permutations(remaining_chars) # Rekursiver Aufruf for perm in remaining_permutations: perm_list.append(char + perm) return perm_list