Implementierung der Fibonacci-Folge in JavaScript: Gängige Ansätze und Variationen

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.

Was ist die Fibonacci-Folge?

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

Gemeinsame Implementierungsansätze

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

Bonus: Rückgabe der Fibonacci-Folge als Array

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:

1. Für 0 und 1 geben wir fest codierte Arrays zurück.
2. 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 < 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:

1. Wenn die Eingabe 0 ist, geben wir ein Array mit nur dem Element 0 zurück.
2. 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 bis n und erhöhen in jeder Iteration die Summe von prev und next bis 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 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!