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 Fibonacci-Sequenz-Implementierungen in JavaScript.

Was ist die Fibonacci-Folge?

Lassen Sie 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, …

Gemeinsame Implementierungsansätze

1. Rekursiver Ansatz

Die traditionellste Anfrage ist eine rekursive Implementierung:

function fibonacciRecursive(n) {
  if (n 



Obwohl dieser Ansatz einfach 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 



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 



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





  
  
  Bonus: Rückgabe der Fibonacci-Folge als Array


Interviewer könnten Sie auch bitten, 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:

Für 0 und 1 geben wir fest codierte Arrays zurück.
Für andere Fälle:

• Wir erhalten die Sequenz für die vorherige Nummer und speichern sie in arr.
• Wir berechnen den aktuellen Wert, indem wir die letzten beiden Werte von arr summieren.
• Wir kombinieren arr und currentValue in einem neuen Array und geben es zurück.

Iterativer Ansatz

function fibonacciSequenceWithIteration(n) {
  if (n 



Diese Funktion funktioniert wie folgt:

Wenn die Eingabe 0 ist, geben wir ein Array mit nur dem Element 0 zurück.
Für andere Fälle:

• Wir initialisieren die Variablen prev und next, um die vorherigen und nächsten Werte zu speichern.
• Wir erstellen arr mit Anfangswerten [0, 1].
• Wir iterieren von 2 nach n und verschieben in jeder Iteration die Summe von prev und next nach arr.
• Wir aktualisieren die vorherigen und nächsten Werte und fahren mit der nächsten Iteration fort.

Abschluss

Obwohl dieser Artikel mehrere gängige Implementierungen von Fibonacci-Sequenzen behandelt, handelt es sich nicht um eine erschöpfende Liste. Wenn Ihnen in Interviews oder Ihrer Arbeit andere Variationen aufgefallen 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.