Ein Python-Leitfaden zur Fibonacci-Folge

Ein Python-Leitfaden zur Fibonacci-Folge

Die Fibonacci-Folge ist eine ziemlich berühmte Folge ganzer Zahlen. Die Sequenz kommt in vielen Problemen auf natürliche Weise vor und hat eine schöne rekursive Definition. Zu lernen, wie man es generiert, ist ein wesentlicher Schritt auf dem Weg des pragmatischen Programmierers zur Beherrschung der Rekursion. In diesem Tutorial konzentrieren Sie sich darauf, zu lernen, was die Fibonacci-Folge ist und wie Sie sie mit Python generieren.

In diesem Tutorial erfahren Sie, wie Sie:

Generieren Sie die Fibonacci-Folge mit einem rekursiven Algorithmus

Optimieren Sie den rekursiven Fibonacci-Algorithmus mithilfe der Memoisierung

Generieren Sie die Fibonacci-Folge mithilfe eines iterativen Algorithmus

Um dieses Tutorial optimal nutzen zu können, sollten Sie die Grundlagen der Big-O-Notation, der objektorientierten Programmierung, der speziellen Methoden von Python, bedingter Anweisungen, Funktionen und grundlegender Datenstrukturen wie Listen, Warteschlangen und Stapel kennen. Wenn Sie mit diesen Konzepten vertraut sind, können Sie die neuen Konzepte, die Sie in diesem Tutorial kennenlernen, wesentlich besser verstehen.

Lasst uns gleich eintauchen!

Erste Schritte mit der Fibonacci-Folge

Leonardo Fibonacci war ein italienischer Mathematiker, der schnell eine Antwort auf die Frage von Kaiser Friedrich II. von Schwaben finden konnte: „Wie viele Kaninchenpaare werden in einem Jahr gewonnen, ohne Todesfälle, wenn man davon ausgeht, dass jedes Paar ein anderes zur Welt bringt?“ jeden Monat ein Paar und die jüngsten Paare können sich bereits im zweiten Lebensmonat fortpflanzen?“

Die Antwort war die folgende Reihenfolge:

Das Muster beginnt nach den ersten beiden Zahlen, 0 und 1, wobei jede Zahl in der Folge immer die Summe der beiden Zahlen davor ist. Indische Mathematiker kannten diese Folge seit dem sechsten Jahrhundert und Fibonacci nutzte sie, um das Wachstum der Kaninchenpopulationen zu berechnen.

F(n) wird verwendet, um die Anzahl der im Monat n vorhandenen Kaninchenpaare anzugeben, daher kann die Sequenz wie folgt ausgedrückt werden:

In der mathematischen Terminologie würde man dies eine Wiederholungsrelation nennen, was bedeutet, dass jeder Term der Folge (über 0 und 1 hinaus) eine Funktion der vorhergehenden Terme ist.

Es gibt auch eine Version der Sequenz, bei der die ersten beiden Zahlen beide 1 sind, etwa so:

In dieser alternativen Version ist F(0) immer noch implizit 0, aber Sie beginnen stattdessen mit F(1) und F(2). Der Algorithmus bleibt derselbe, da Sie immer die beiden vorherigen Zahlen summieren, um die nächste Zahl in der Folge zu erhalten.

Für dieses Tutorial verwenden Sie die Version der Sequenz, die mit 0 beginnt.

Untersuchung der Rekursion hinter der Fibonacci-Folge

Die Generierung der Fibonacci-Folge ist ein klassisches rekursives Problem. Von Rekursion spricht man, wenn eine Funktion auf sich selbst verweist, um das Problem, das sie zu lösen versucht, aufzuschlüsseln. Bei jedem Funktionsaufruf wird das Problem kleiner, bis es einen Basisfall erreicht. Anschließend wird das Ergebnis an jeden Zwischenaufrufer zurückgegeben, bis das Endergebnis an den ursprünglichen Aufrufer zurückgegeben wird.

Wenn Sie die Fibonacci-Zahl F(5) berechnen möchten, müssen Sie ihre Vorgänger F(4) und F( berechnen. 3), zuerst. Und um F(4) und F(3) zu berechnen, müssten Sie deren Vorgänger berechnen. Die Aufteilung von F(5) in kleinere Teilprobleme würde wie folgt aussehen:

Jedes Mal, wenn die Fibonacci-Funktion aufgerufen wird, wird sie in zwei kleinere Teilprobleme zerlegt, da Sie so die Wiederholungsbeziehung definiert haben. Wenn es den Basisfall von F(0) oder F(1) erreicht, kann es schließlich ein Ergebnis an seinen Aufrufer zurückgeben.

Um die fünfte Zahl in der Fibonacci-Folge zu berechnen, lösen Sie kleinere, aber identische Probleme, bis Sie die Basisfälle erreichen, bei denen Sie mit der Rückgabe eines Ergebnisses beginnen können:

Die farbigen Teilprobleme in diesem Diagramm stellen sich wiederholende Lösungen desselben Problems dar. Wenn Sie weiter nach oben gehen, werden Sie weitere dieser sich wiederholenden Lösungen finden. Das bedeutet, dass Sie zum rekursiven Erzeugen einer Fibonacci-Folge viele Zwischenzahlen immer wieder berechnen müssen. Dies ist eines der grundlegenden Probleme beim rekursiven Ansatz der Fibonacci-Folge.

Rekursives Generieren der Fibonacci-Folge in Python

Der gebräuchlichste und minimalste Algorithmus zum Generieren der Fibonacci-Folge erfordert, dass Sie eine rekursive Funktion programmieren, die sich selbst so oft wie nötig aufruft, bis sie die gewünschte Fibonacci-Zahl berechnet:

>>> def fibonacci_of(n): ... if n in {0, 1}: # Base case ... return n ... return fibonacci_of(n - 1) + fibonacci_of(n - 2) # Recursive case ... >>> [fibonacci_of(n) for n in range(15)] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Innerhalb von fibonacci_of() überprüfen Sie zunächst den Basisfall. Sie geben dann die Summe der Werte zurück, die sich aus dem Aufruf der Funktion mit den beiden vorhergehenden Werten von n ergibt. Das Listenverständnis am Ende des Beispiels generiert eine Fibonacci-Folge mit den ersten fünfzehn Zahlen.

Diese Funktion fällt schnell in das Wiederholungsproblem, das Sie im obigen Abschnitt gesehen haben. Die Berechnung wird umso aufwändiger, je größer n wird. Die benötigte Zeit wächst exponentiell, da die Funktion immer wieder viele identische Teilprobleme berechnet.

Hinweis: Probieren Sie diese Funktion zu Hause nicht mit einer Zahl größer als 50 aus. Abhängig von Ihrer Hardware kann es sein, dass Sie lange warten müssen, bis Sie das Ergebnis sehen - wenn Sie es bis zum Ende schaffen.

Um F(5) zu berechnen, muss sich fibonacci_of() fünfzehn Mal selbst aufrufen. Um F(n) zu berechnen, beträgt die maximale Tiefe des Aufrufbaums n, und da jeder Funktionsaufruf zwei zusätzliche Funktionsaufrufe erzeugt, ist die Die zeitliche Komplexität dieser rekursiven Funktion beträgt O(2n).

Die meisten dieser Anrufe sind überflüssig, weil Sie ihre Ergebnisse bereits berechnet haben. F(3) erscheint zweimal und F(2) erscheint dreimal. F(1) und F(0) sind Basisfälle, daher ist es in Ordnung, sie mehrmals aufzurufen. Möglicherweise möchten Sie diese verschwenderische Wiederholung vermeiden, die Gegenstand der folgenden Abschnitte ist.

Optimierung des rekursiven Algorithmus für die Fibonacci-Folge

Es gibt mindestens zwei Techniken, mit denen Sie den Algorithmus zur Generierung der Fibonacci-Folge effizienter gestalten können - mit anderen Worten, um die Berechnungszeit zu verkürzen. Diese Techniken stellen sicher, dass Sie nicht immer wieder dieselben Werte berechnen, was den ursprünglichen Algorithmus so ineffizient machte. Sie werden Memoisierung und Iteration genannt.

Den rekursiven Algorithmus auswendig lernen

Wie Sie im obigen Code gesehen haben, ruft sich die Fibonacci-Funktion mehrmals mit derselben Eingabe auf. Anstatt jedes Mal einen neuen Aufruf durchzuführen, können Sie die Ergebnisse früherer Aufrufe in etwas wie einem Speichercache speichern. Sie können eine Python-Liste verwenden, um die Ergebnisse früherer Berechnungen zu speichern. Diese Technik wird Memoisierung genannt

Die Memoisierung beschleunigt die Ausführung teurer rekursiver Funktionen, indem zuvor berechnete Ergebnisse in einem Cache gespeichert werden. Auf diese Weise muss die Funktion bei erneuter Eingabe derselben Eingabe lediglich das entsprechende Ergebnis nachschlagen und zurückgeben, ohne die Berechnung erneut ausführen zu müssen. Sie können diese Ergebnisse als zwischengespeichert oder gespeichert bezeichnen:

Bei der Memoisierung müssen Sie den Aufrufbaum der Tiefe n nur einmal nach oben durchlaufen, nachdem Sie vom Basisfall zurückgekehrt sind, während Sie alle zuvor berechneten Werte abrufen, die gelb hervorgehoben sind, F (2) und F(3), aus dem Cache zuvor.

Der orangefarbene Pfad zeigt, dass keine Eingabe der Fibonacci-Funktion mehr als einmal aufgerufen wird. Dies reduziert die zeitliche Komplexität des Algorithmus erheblich von exponentiellem O(2n) auf lineares O(n).

Selbst für die Basisfälle können Sie den Aufruf von F(0) und F(1) dadurch ersetzen, dass Sie einfach die Werte direkt aus dem Cache bei den Indizes 0 und 1 abrufen Am Ende rufen Sie die Funktion nur sechs statt fünfzehn Mal auf!

Hier ist eine mögliche Übersetzung dieser Optimierung in Python-Code:

>>> cache = {0: 0, 1: 1} >>> def fibonacci_of(n): ... if n in cache: # Base case ... return cache[n] ... # Compute and cache the Fibonacci number ... cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2) # Recursive case ... return cache[n] >>> [fibonacci_of(n) for n in range(15)] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

In diesem Beispiel verwenden Sie ein Python-Wörterbuch, um die berechneten Fibonacci-Zahlen zwischenzuspeichern. Zunächst enthält cache die Startwerte der Fibonacci-Folge, 0 und 1. Innerhalb der Funktion prüfen Sie zunächst, ob die Fibonacci-Zahl für den aktuellen Eingabewert von n bereits vorhanden ist im Cache. Wenn ja, geben Sie die vorliegende Nummer zurück.

Wenn es für den aktuellen Wert von n keine Fibonacci-Zahl gibt, berechnen Sie diese, indem Sie fibonacci_of() rekursiv aufrufen und cache aktualisieren. Der letzte Schritt besteht darin, die angeforderte Fibonacci-Zahl zurückzugeben.

Erforschung eines iterativen Algorithmus

Was wäre, wenn Sie die rekursive Fibonacci-Funktion überhaupt nicht aufrufen müssten? Sie können tatsächlich einen iterativen Algorithmus verwenden, um die Zahl an Position n in der Fibonacci-Folge zu berechnen.

Sie wissen, dass die ersten beiden Zahlen in der Folge 0 und 1 sind und dass jede nachfolgende Zahl in der Folge die Summe ihrer beiden Vorgänger ist. Sie können also einfach eine Schleife erstellen, die die beiden vorherigen Zahlen n - 1 und n - 2 addiert, um die Zahl an Position n zu finden. in der Sequenz.

Die fettgedruckten violetten Zahlen im Diagramm unten stellen die neuen Zahlen dar, die in jedem Iterationsschritt berechnet und zum cache hinzugefügt werden müssen:

Um die Fibonacci-Zahl an Position n zu berechnen, speichern Sie die ersten beiden Zahlen der Sequenz, 0 und 1, im Cache. Berechnen Sie dann nacheinander die nächsten Zahlen, bis Sie cache[n] zurückgeben können.

Generieren der Fibonacci-Folge in Python

Nachdem Sie nun die Grundlagen zum Generieren der Fibonacci-Folge kennen, ist es an der Zeit, tiefer in die Materie einzusteigen und die verschiedenen Möglichkeiten zur Implementierung des zugrunde liegenden Algorithmus in Python weiter zu untersuchen. In den folgenden Abschnitten erfahren Sie, wie Sie verschiedene Algorithmen zum Generieren der Fibonacci-Folge mithilfe von Rekursion, objektorientierter Python-Programmierung und Iteration implementieren.

Verwenden von Rekursion und einer Python-Klasse

Ihr erster Ansatz zum Generieren der Fibonacci-Folge verwendet eine Python-Klasse und eine Rekursion. Ein Vorteil der Verwendung der Klasse gegenüber der gespeicherten rekursiven Funktion, die Sie zuvor gesehen haben, besteht darin, dass eine Klasse Zustand und Verhalten (Kapselung) innerhalb desselben Objekts zusammenhält. Im Funktionsbeispiel ist cache jedoch ein völlig separates Objekt, sodass Sie keine Kontrolle darüber haben.

Nachfolgend finden Sie den Code, der Ihre klassenbasierte Lösung implementiert:

# fibonacci_class.py class Fibonacci: def __init__(self): self.cache = [0, 1] def __call__(self, n): # Validate the value of n if not (isinstance(n, int) and n >= 0): raise ValueError(f'Positive integer number expected, got "{n}"') # Check for computed Fibonacci numbers if n < len(self.cache): return self.cache[n] else: # Compute and cache the requested Fibonacci number fib_number = self(n - 1) + self(n - 2) self.cache.append(fib_number) return self.cache[n]

Hier ist eine Aufschlüsselung dessen, was im Code passiert:

Zeile 3 definiert die Klasse Fibonacci.

Zeile 4 definiert den Klasseninitialisierer .__init__(). Es handelt sich um eine spezielle Methode, mit der Sie Ihre Klasseninstanzen initialisieren können. Spezielle Methoden werden manchmal als Dunder-Methoden bezeichnet, kurz für Double-Underscore-Methoden.

Zeile 5 erstellt das Instanzattribut .cache, was bedeutet, dass jedes Mal, wenn Sie ein Fibonacci-Objekt erstellen, ein Cache dafür vorhanden ist. Dieses Attribut enthält zunächst die ersten Zahlen der Fibonacci-Folge.

Zeile 7 definiert eine weitere spezielle Methode, .__call__(). Diese Methode wandelt die Instanzen von Fibonacci in aufrufbare Objekte um.

Zeilen 9 und 10 validieren den Wert von n mithilfe einer bedingten Anweisung. Wenn n keine positive ganze Zahl ist, löst die Methode einen ValueError aus.

Zeile 13 definiert eine bedingte Anweisung, um nach Fibonacci-Zahlen zu suchen, die bereits berechnet wurden und in .cache verfügbar sind. Wenn sich die Zahl am Index n bereits in .cache befindet, wird sie in Zeile 14 zurückgegeben. Andernfalls berechnet Zeile 17 die Zahl und Zeile 18 hängt sie an .cache an, sodass Sie sie nicht erneut berechnen müssen.

Zeile 20 gibt die angeforderte Fibonacci-Zahl zurück.

Um diesen Code auszuprobieren, speichern Sie ihn in fibonacci_class.py. Führen Sie dann diesen Code in Ihrer interaktiven Shell aus:

>>> from fibonacci_class import Fibonacci >>> fibonacci_of = Fibonacci() >>> fibonacci_of(5) 5 >>> fibonacci_of(6) 8 >>> fibonacci_of(7) 13 >>> [fibonacci_of(n) for n in range(15)] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Hier erstellen Sie eine Instanz der Klasse Fibonacci mit dem Namen fibonacci_of und rufen diese dann auf. Der erste Aufruf verwendet 5 als Argument und gibt 5 zurück, was die sechste Fibonacci-Zahl ist, da Sie nullbasierte Indizes verwenden.

Diese Implementierung des Fibonacci-Sequenzalgorithmus ist recht effizient. Sobald Sie eine Instanz der Klasse haben, enthält das Attribut .cache die bereits berechneten Zahlen von Anruf zu Anruf.

Visualisierung des auswendig gelernten Fibonacci-Sequenzalgorithmus

Mithilfe einer Call-Stack-Darstellung können Sie effektiv verstehen, wie jeder Aufruf einer rekursiven Fibonacci-Funktion gehandhabt wird. Die Art und Weise, wie jeder Aufruf auf den Stapel verschoben und dort abgelegt wird, spiegelt genau wider, wie das Programm ausgeführt wird. Es zeigt deutlich, dass die Berechnung großer Zahlen lange dauern wird, wenn Sie den Algorithmus nicht optimieren.

Wenn in einem Aufrufstapel eine Funktion ein Ergebnis zurückgibt, wird ein Stapelrahmen, der den Funktionsaufruf darstellt, vom Stapel entfernt. Immer wenn Sie eine Funktion aufrufen, fügen Sie oben im Stapel einen neuen Stapelrahmen hinzu. Im Allgemeinen weist diese Operation eine Platzkomplexität von O(n) auf, da nicht mehr als n Stapelrahmen auf dem Aufrufstapel bei a vorhanden sind einmal.

Hinweis: Es gibt einen einsteigerfreundlichen Code-Editor namens Thonny, mit dem Sie den Aufrufstapel einer rekursiven Funktion grafisch visualisieren können. Sie können sich Thonny: The Beginner-Friendly Python Editor ansehen, um mehr zu erfahren.

Um den gespeicherten rekursiven Fibonacci-Algorithmus zu visualisieren, verwenden Sie eine Reihe von Diagrammen, die den Aufrufstapel darstellen. Die Schrittnummer wird durch das blaue Etikett unter jedem Aufrufstapel angezeigt.

Angenommen, Sie möchten F(5) berechnen. Dazu schieben Sie den ersten Aufruf der Funktion auf den Aufrufstapel:

Um F(5) zu berechnen, müssen Sie F(4) gemäß der Fibonacci-Rekurrenzbeziehung berechnen, also fügen Sie diesen neuen Funktionsaufruf zum Stapel hinzu:

Um F(4) zu berechnen, müssen Sie F(3) berechnen, also fügen Sie dem Stapel einen weiteren Funktionsaufruf hinzu:

Um F(3) zu berechnen, müssen Sie F(2) berechnen, also fügen Sie dem Aufrufstapel noch einen weiteren Funktionsaufruf hinzu:

Um F(2) zu berechnen, müssen Sie F(1) berechnen, also fügen Sie es dem Stapel hinzu. Da F(1) ein Basisfall ist, kehrt es sofort mit 1 zurück und Sie entfernen diesen Aufruf vom Stapel:

Jetzt beginnen Sie damit, die Ergebnisse rekursiv abzuwickeln. F(1) gibt das Ergebnis an seine aufrufende Funktion F(2) zurück. Um F(2) zu berechnen, müssen Sie auch F(0) berechnen:

Sie fügen F(0) zum Stapel hinzu. Da F(0) ein Basisfall ist, kehrt es sofort zurück und gibt Ihnen 0. Jetzt können Sie es aus dem Aufrufstapel entfernen:

Dieses Ergebnis des Aufrufs von F(0) wird an F(2) zurückgegeben. Jetzt haben Sie alles, was Sie brauchen, um F(2) zu berechnen und vom Stapel zu entfernen:

Das Ergebnis von F(2) wird an seinen Aufrufer F(3) zurückgegeben. F(3) benötigt außerdem die Ergebnisse von F(1), um seine Berechnung abzuschließen, also fügen Sie es wieder dem Stapel hinzu:

F(1) ist ein Basisfall und sein Wert ist im Cache verfügbar, sodass Sie das Ergebnis sofort zurückgeben und F(1) vom Stapel entfernen können:

Sie können die Berechnung für F(3) vervollständigen, das 2 ist:

Sie entfernen F(3) vom Stapel, nachdem die Berechnung abgeschlossen ist, und geben das Ergebnis an seinen Aufrufer F(4) zurück. F(4) benötigt außerdem das Ergebnis von F(2), um seinen Wert zu berechnen:

Sie schieben den Aufruf von F(2) auf den Stapel. Hier kommt der raffinierte Cache ins Spiel. Sie haben ihn bereits berechnet, sodass Sie den Wert einfach aus dem Cache abrufen können und so einen rekursiven Aufruf zur erneuten Berechnung des Ergebnisses von F(2) vermeiden. Der Cache gibt 1 zurück und Sie entfernen F(2) vom Stapel:

F(2) wird an seinen Aufrufer zurückgegeben, und jetzt hat F(4) alles, was es braucht, um seinen Wert zu berechnen, der 3 ist:

Als nächstes entfernen Sie F(4) vom Stapel und geben das Ergebnis an den letzten und ursprünglichen Aufrufer F(5) zurück:

F(5) hat nun das Ergebnis von F(4) und auch das Ergebnis von F(3). Sie schieben einen F(3)-Aufruf auf den Stapel und der raffinierte Cache kommt wieder ins Spiel. Sie haben zuvor F(3) berechnet, Sie müssen es also nur noch aus dem Cache abrufen. Es gibt keinen rekursiven Prozess zur Berechnung von F(3). Es gibt 2 zurück und Sie entfernen F(3) vom Stapel:

Jetzt hat F(5) alle Werte, die es zur Berechnung seines eigenen Wertes benötigt. Sie erhalten 5, indem Sie 3 und 2 addieren, und das ist der letzte Schritt, bevor Sie den F(5)-Aufruf vom Stapel nehmen. Diese Aktion beendet Ihre Folge rekursiver Funktionsaufrufe:

Der Aufrufstapel ist jetzt leer. Sie haben den letzten Schritt zur Berechnung von F(5) abgeschlossen:

Die Darstellung rekursiver Funktionsaufrufe mithilfe eines Aufrufstapeldiagramms hilft Ihnen, die gesamte Arbeit zu verstehen, die hinter den Kulissen stattfindet. Außerdem können Sie sehen, wie viele Ressourcen eine rekursive Funktion beanspruchen kann.

Wenn Sie alle diese Diagramme zusammenfügen, können Sie visualisieren, wie der gesamte Prozess aussieht:

Sie können auf das Bild oben klicken, um einzelne Schritte zu vergrößern. Wenn Sie zuvor berechnete Fibonacci-Zahlen nicht zwischenspeichern, wären einige der Stapelstufen in diesem Diagramm viel höher, was bedeutet, dass es länger dauern würde, bis sie ein Ergebnis an ihre jeweiligen Aufrufer zurückgeben.

Verwenden von Iteration und einer Python-Funktion

Das Beispiel in den vorherigen Abschnitten implementiert eine rekursive Lösung, die Memoisierung als Optimierungsstrategie verwendet. In diesem Abschnitt programmieren Sie eine Funktion, die Iteration verwendet. Der folgende Code implementiert eine iterative Version Ihres Fibonacci-Sequenzalgorithmus:

# fibonacci_func.py def fibonacci_of(n): # Validate the value of n if not (isinstance(n, int) and n >= 0): raise ValueError(f'Positive integer number expected, got "{n}"') # Handle the base cases if n in {0, 1}: return n previous, fib_number = 0, 1 for _ in range(2, n + 1): # Compute the next Fibonacci number, remember the previous one previous, fib_number = fib_number, previous + fib_number return fib_number

Anstatt die Rekursion in fibonacci_of() zu verwenden, verwenden Sie jetzt die Iteration. Diese Implementierung des Fibonacci-Sequenzalgorithmus läuft in O(n) linearer Zeit. Hier ist eine Aufschlüsselung des Codes:

Zeile 3 definiert fibonacci_of(), das eine positive Ganzzahl, n, als Argument akzeptiert.

Zeilen 5 und 6 führen die übliche Validierung von n durch.

Zeilen 9 und 10 behandeln die Basisfälle, in denen n entweder 0 oder 1 ist.

Zeile 12 definiert zwei lokale Variablen, previous und fib_number, und initialisiert sie mit den ersten beiden Zahlen in der Fibonacci-Folge.

Zeile 13 startet eine for-Schleife, die von 2 bis n + 1 iteriert. Die Schleife verwendet einen Unterstrich (_) für die Schleifenvariable, da es sich um eine Wegwerfvariable handelt und Sie diesen Wert im Code nicht verwenden.

Zeile 15 berechnet die nächste Fibonacci-Zahl in der Folge und merkt sich die vorherige.

Zeile 17 gibt die angeforderte Fibonacci-Zahl zurück.

Um diesen Code auszuprobieren, kehren Sie zu Ihrer interaktiven Sitzung zurück und führen Sie den folgenden Code aus:

>>> from fibonacci_func import fibonacci_of >>> fibonacci_of(5) 5 >>> fibonacci_of(6) 8 >>> fibonacci_of(7) 13 >>> [fibonacci_of(n) for n in range(15)] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Diese Implementierung von fibonacci_of() ist recht minimal. Es verwendet iterierbares Entpacken, um die Fibonacci-Zahlen während der Schleifen zu berechnen, was in Bezug auf den Speicher recht effizient ist. Allerdings muss jedes Mal, wenn Sie die Funktion mit einem anderen Wert von n aufrufen, die Sequenz erneut berechnet werden. Um dies zu beheben, können Sie Abschlüsse verwenden und dafür sorgen, dass sich Ihre Funktion zwischen Aufrufen die bereits berechneten Werte merkt. Probieren Sie es einfach aus!

Abschluss

Die Fibonacci-Folge kann Ihnen helfen, Ihr Verständnis der Rekursion zu verbessern. In diesem Tutorial haben Sie gelernt, was die Fibonacci-Folge ist. Sie haben auch einige gängige Algorithmen zum Generieren der Sequenz kennengelernt und erfahren, wie Sie diese in Python-Code übersetzen.

Die Fibonacci-Folge kann ein hervorragendes Sprungbrett und Einstiegspunkt in die Welt der Rekursion sein, die eine grundlegende Fähigkeit eines Programmierers darstellt.

In diesem Tutorial haben Sie Folgendes gelernt:

Generieren Sie die Fibonacci-Folge mit einem rekursiven Algorithmus

Optimieren Sie Ihren rekursiven Fibonacci-Algorithmus mithilfe der Memoisierung

Generieren Sie die Fibonacci-Folge mithilfe eines iterativen Algorithmus

Sie haben auch den auswendig gelernten rekursiven Algorithmus visualisiert, um besser zu verstehen, wie er hinter den Kulissen funktioniert. Dazu haben Sie ein Call-Stack-Diagramm verwendet.

Sobald Sie die Konzepte in diesem Tutorial beherrschen, werden sich Ihre Python-Programmierkenntnisse und Ihr rekursives algorithmisches Denken verbessern.