Als Entwickler sind Sie wahrscheinlich schon einmal auf die Aufgabe gestoßen, eine Funktion zum Berechnen von Werten in der Fibonacci-Folge zu schreiben. Dieses klassische Problem tritt häufig bei Codierungsinterviews auf, bei denen typischerweise eine rekursive Implementierung erforderlich ist. Interviewer fordern jedoch manchmal spezifische Vorgehensweisen. In diesem Artikel untersuchen wir die gängigsten Implementierungen von Fibonacci-Folgen in JavaScript.
Lasst uns zunächst unser Gedächtnis auffrischen. Die Fibonacci-Folge ist eine Reihe von Zahlen, bei der jede Zahl die Summe der beiden vorhergehenden ist. Es beginnt mit 0 und 1:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
1. Rekursiver Ansatz
Die traditionellste Anfrage ist eine rekursive Implementierung:
function fibonacciRecursive(n) { if (n < 1) { return 0; } if (n === 1) { return 1; } return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2); }
Obwohl dieser Ansatz unkompliziert ist, ist er für große Werte von n nicht performant. Auf einem MacBook Pro i9 mit 16 GB RAM dauerte die Berechnung der 40. Fibonacci-Zahl etwa 1,5 Sekunden:
console.time('Recursive'); fibonacciRecursive(40); console.timeEnd('Recursive'); VM379:3 Recursive: 1521.569091796875 ms
Der Versuch, die 50. Zahl zu berechnen, führte dazu, dass der Chrome-Tab nicht mehr reagierte.
2. Rekursiver Ansatz mit Caching (Memoisierung)
Die nächste Variante dieser Frage besteht darin, die Leistung zu verbessern, indem wir unserer rekursiven Implementierung einen Caching-Mechanismus hinzufügen:
function fibonacciCached(n, cached = {[0]: 0, [1]: 1}) { if (n < 1) { return 0; } if (n === 1) { return 1; } if (cached[n]) { return cached[n]; } cached[n] = fibonacciCached(n - 1, cached) + fibonacciCached(n - 2, cached); return cached[n]; }
Dieser Ansatz führt ein zwischengespeichertes Objekt mit Anfangswerten für 0 und 1 ein. Für jede gegebene Zahl prüfen wir zunächst, ob wir ihren Fibonacci-Wert bereits berechnet haben. Wenn ja, geben wir das zwischengespeicherte Ergebnis zurück, anstatt es neu zu berechnen. Andernfalls berechnen wir diesen Wert und speichern ihn im Cache.
Die Leistungsverbesserung ist erheblich (natürlich aufgrund des zusätzlich genutzten Speichers). Die Berechnung der 40. Fibonacci-Zahl dauerte ~0,02 ms:
console.time('Recursive, with caching'); fibonacciCached(40); console.timeEnd('Recursive, with caching'); VM382:3 Recursive, with caching: 0.01806640625 ms
3. Iterativer Ansatz mit einer for-Schleife
Eine weitere gängige Variante ist die Implementierung der Fibonacci-Folge mithilfe einer for-Schleife:
function fibonacciWithIteration(n) { if (n <= 0) { return 0; } if (n === 1) { return 1; } let prev = 0; let next = 1; let result = 1; for (let i = 2; i <= n; i++) { result = prev + next; [prev, next] = [next, prev + next]; } return result; }
Dieser Ansatz ist viel schneller als die grundlegende rekursive Methode (die ohne Caching):
console.time('With iteration'); fibonacciWithIteration(40); console.timeEnd('With iteration'); VM44:22 With iteration: 0.10107421875 ms
Der iterative Ansatz kann sehr große Eingabewerte effizient verarbeiten:
console.time('With iteration'); const result = fibonacciWithIteration(1400); console.log(result); console.timeEnd('With iteration'); VM325:22 1.7108476902340223e+292 VM325:23 With iteration: 0.5830078125 ms
Interviewer bitten Sie möglicherweise auch, die gesamte Fibonacci-Folge bis zur n-ten Zahl als Array zurückzugeben. Lassen Sie uns dies sowohl mit rekursiven als auch mit iterativen Ansätzen implementieren.
Rekursiver Ansatz
function fibonacciSequence(n) { if (n === 0) { return [0]; } if (n === 1) { return [0, 1]; } const arr = fibonacciSequence(n - 1); const currentValue = arr[n - 1] + arr[n - 2]; return [...arr, currentValue]; } console.log(fibonacciSequence(5)); // [0, 1, 1, 2, 3, 5]
Diese Funktion funktioniert wie folgt:
Iterativer Ansatz
function fibonacciSequenceWithIteration(n) { if (n < 1) { return [0]; } let prev = 0; let next = 1; const arr = [prev, next]; for (let i = 2; i <= n; i++) { arr.push(prev + next); [prev, next] = [next, prev + next]; } return arr; } console.log(fibonacciSequenceWithIteration(5)); // [0, 1, 1, 2, 3, 5]
Diese Funktion funktioniert wie folgt:
Obwohl dieser Artikel mehrere gängige Implementierungen von Fibonacci-Sequenzen behandelt, handelt es sich nicht um eine erschöpfende Liste. Wenn Sie in Interviews oder Ihrer Arbeit auf andere Variationen gestoßen sind, teilen Sie diese bitte in den Kommentaren mit!
Bleiben Sie mit den neuesten Nachrichten zu JavaScript und Softwareentwicklung auf dem Laufenden! Treten Sie meinem Telegram-Kanal bei, um weitere Einblicke und Diskussionen zu erhalten: TechSavvy: Frontend & Backend.
Das obige ist der detaillierte Inhalt vonImplementierung der Fibonacci-Folge in JavaScript: Gängige Ansätze und Variationen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!