Buch kaufen
Buch kaufen
Buch kaufen
Recursive Functions
Definition
"Rekursion hat etwas mit Unendlichkeit zu tun. Ich weiß, dass Rekursion etwas mit Unendlichkeit zu tun hat. Ich glaube, ich weiß, dass Rekursion etwas mit Unendlichkeit zu tun hat. Er ist sich sicher, dass ich weiß, dass Rekursion etwas mit Unendlichkeit zu tun hat. Wir bezweifeln, dass er sicher ist, dass ich weiß ..." Wir glauben, dass wir Sie jetzt davon überzeugt haben, dass wir mit diesem Beispiel einer Rekursion aus der natürlichen Sprache für immer weitermachen können. Rekursion ist nicht nur ein grundlegendes Merkmal der natürlichen Sprache, sondern auch der kognitiven Fähigkeiten des Menschen. Unsere Denkweise basiert auf rekursiven Denkprozessen. Selbst mit einer sehr einfachen Grammatikregel wie "Ein englischer Satz enthält ein Subjekt und ein Prädikat und ein Prädikat enthält ein Verb, ein Objekt und eine Ergänzung" können wir die unendlichen Möglichkeiten der natürlichen Sprache demonstrieren. Der Kognitionswissenschaftler und Linguist Stephen Pinker formuliert es so: "Mit ein paar tausend Substantiven, die den Platzhalter für das Subjekt füllen können, und ein paar tausend Verben, die den Platzhalter für das Prädikat füllen können, hat man bereits mehrere Millionen Möglichkeiten, einen Satz zu öffnen. Die möglichen Kombinationen multiplizieren sich schnell zu unvorstellbar großen Zahlen. In der Tat ist das Repertoire an Sätzen theoretisch unendlich, weil die Sprachregeln einen Trick verwenden, der als Rekursion bezeichnet wird. Eine rekursive Regel erlaubt es einer Phrase, ein Beispiel für sich selbst zu enthalten, wie in "Sie glaubt, dass er das denkt sie denken, dass er es weiß" und so weiter, ad infinitum. Und wenn die Anzahl der Sätze unendlich ist, ist auch die Anzahl der möglichen Gedanken und Absichten unendlich, weil praktisch jeder Satz einen anderen Gedanken oder eine andere Absicht ausdrückt. "1
Wir müssen unsere kurze Exkursion zur Verwendung der Rekursion in natürlicher Sprache beenden, um zur Rekursion in Informatik und Programmen und schließlich zur Rekursion in der Programmiersprache Python zurückzukehren.
Das Adjektiv "rekursiv" stammt vom lateinischen Verb "recurrere" ab, was "zurücklaufen" bedeutet. Und dies ist, was eine rekursive Definition oder eine rekursive Funktion tut: Sie "läuft zurück" oder kehrt zu sich selbst zurück. Die meisten Leute, diesich mit Mathematik oder Informatik beschäftigt haben oder ein Buch über Programmierung gelesen haben, werden auf die Fakultät gestoßen sein, die in mathematischen Begriffen definiert ist als
n! = n * (n-1)!, wenn n> 1 und 0! = 1
Es wird wegen seiner Einfach- und Klarheit oft als erstes Beispiel für eine Rekursion verwendet.
Definition der Rekursion
Rekursion ist eine Methode zum Programmieren oder Codieren eines Problems, bei der eine Funktion ein- oder mehrmals in ihrem Funktionskörper aufgerufen wird. Normalerweise wird der Rückgabewert dieses Funktionsaufrufs zurückgegeben. Wenn eine Funktionsdefinition die Rekursionsbedingung erfüllt, nennen wir diese Funktion eine rekursive Funktion.
Abbruchbedingung: Eine rekursive Funktion muss eine wichtige Bedingung erfüllen, damit man sie in einem Programm verwenden kann: Sie muss terminieren. Eine rekursive Funktion wird beendet, wenn bei jedem rekursiven Aufruf die Lösung des Problems verkleinert wird und sich einem Basisfall "nähert". Ein Basisfall ist ein Fall, in dem das Problem ohne weitere Rekursion gelöst werden kann. Eine Rekursion kann in einer Endlosschleife enden, wenn der Basisfall in den Aufrufen nicht erreicht wird.
Beispiel:
4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1
Das Ersetzen der berechneten Werte ergibt den folgenden Ausdruck
4! = 4 * 3 * 2 * 1Mit anderen Worten, Rekursion in der Informatik ist eine Methode, bei der die Lösung eines Problems auf der Lösung kleinerer Instanzen desselben Problems basiert.
Rekursive Funktionen in Python
Nun kommen wir dazu, die Fakultät in Python zu implementieren. Es ist so einfach und elegant wie die mathematische Definition.
def Fakultät(n):
if n == 1:
return 1
else:
return n * Fakultät(n-1)
print(Fakultät(4))
Wir können die Funktionsweise der Funktion verfolgen, indem wir der vorherigen Funktionsdefinition zwei print()-Funktionen hinzufügen:
def Fakultät(n):
print(f"Fakultät wurde mit {n} aufgerufen")
if n == 1:
return 1
else:
res = n * Fakultät(n-1)
print("Zwischenergebnis für ", n, " *Fakultät (" , n-1, "): ", res)
return res
print(Fakultät(5))
Schauen wir uns eine iterative Version der Fakultätsfunktion an.
def iterative_Fakultät(n):
Ergebnis = 1
for i in range(2, n+1):
Ergebnis *= i
return Ergebnis
for i in range(5):
print(i, iterative_Fakultät(i))
Es ist üblich, die Fakultätsfunktion für 0 als Argument zu erweitern. Es ist sinnvoll, "0!" als "1" zu definieren, da es genau eine Permutation von Nullobjekten gibt, d.h. wenn nichts permutieren soll, bleibt "Alles" an Ort und Stelle.
Für die mathematisch Interessierten: Zur Berechnung der k-Kombinationen von n Elementen gilt die Formel: $$\binom{n}{k} = \frac{n!}{(n-k)! \cdot k!}$$ Ist k gleich n, erhält man den Ausdruck $(n - n)!$ also 0!. Hierbei muss $0!$ auch als 1 definiert sein.
Um dies zu implementieren, müssen wir lediglich die Bedingung der if-Anweisung ändern:
def Fakultät(n):
if n == 0:
return 1
else:
return n * Fakultät(n-1)
Fibonacci-Zahlen
Unsere Abhandlung über die Rekursion führt uns nun zu einem weiteren interessanten Fall der Rekursion.
Was haben Sonnenblumen, der Goldene Schnitt, Tannenzapfen, der Da Vinci-Code, das Lied "Lateralus" von Tool und die Grafik auf der rechten Seite gemeinsam? Richtig, die Fibonacci-Zahlen. Die Fibonacci-Zahlen führen wir nicht ein, um ein weiteres Beispiel für eine rekursive Funktion zu haben. Vielmehr wollen wir mit einer rekursiven Funktion für diese Zahlenfolge auf ein interessantes Problem der Rekursion zu sprechen kommen. Der Versuch, eine rekursive Funktion für diese Zahlenfolge zu schreiben, kann nämlich zu einem ineffizienten Programm führen. In der Tat so ineffizient, dass es in der Praxis nicht brauchbar sein wird. Wir führen die Fibonacci-Zahlen ein, um die Fallstricke der Rekursion zu zeigen.