Rekursives Fibonacci in C++

1. Rekursive Funktionen in C++
2. Arten der Rekursion
3. Fibonacci-Reihe
4. Fibonacci-Reihe in C++

Dieses kleine Tutorial erklärt, wie man die Fibonacci-Reihe mit der rekursiven Funktion in C++ implementiert. Dafür werden wir zuerst eine kurze Einführung in rekursive Funktionen geben.

Rekursive Funktionen in C++

Eine rekursive Funktion ruft sich innerhalb ihres eigenen Körpers auf, und die Verwendung dieses Konzepts wird als Rekursion bezeichnet. Dieses Konzept ist in vielerlei Hinsicht nützlich, und einige Funktionen können nur mit Rekursion implementiert werden.

Die obige Abbildung zeigt das Konzept der Rekursion. In der Funktion main wird eine Funktion recurse aufgerufen, und in dieser Funktion wird erneut recurse aufgerufen.

Dadurch wird ein rekursiver Aufruf erstellt, und das Programm wird seine Iterationen in dieser Funktion fortsetzen, bis eine Bedingung erfüllt ist. Normalerweise wird die if...else-Struktur in den rekursiven Funktionen verwendet, wobei ein Pfad einen rekursiven Aufruf durchführt und der andere die Funktion verlässt; Andernfalls tritt eine unendliche Rekursion auf.

Die Rekursion führt mehrere wiederholte Aufrufe der Funktion innerhalb der Funktion durch. Die rekursive Bedingung ruft die Funktion erneut auf, bis der Basisfall erfüllt ist.

Der Basisfall ist in der Funktion enthalten und beendet die Ausführung immer dann, wenn die Bedingung des Basisfalls erfüllt ist.

Code:

void recursiveFun(int x) {
  if (x == 0) return;
  x = x - 1;
  recursiveFun(x);
}

Die obige Funktion, einmal mit dem Argument x aufgerufen, ruft sich selbst rekursiv mit einem reduzierten Wert von x (d. h. [x-1, x-2,…, x-(x-1)]) auf, bis das x wird Null. Wenn x mit dem Wert Null angetroffen wird, stoppt das Programm die Generierung neuer rekursiver Aufrufe und beginnt mit der Rückgabe von Werten (falls vorhanden) von unten nach oben.

Obwohl die Rekursion verwendet werden kann, um fast alle Probleme zu lösen, gibt es ausgewählte Fälle, in denen sie wirklich vorteilhaft ist. Es wird häufig verwendet, um schwierige Probleme und Probleme zu behandeln, die einem hierarchischen Muster folgen. Es geht das Hauptproblem an, indem es kleinere Teilprobleme löst.

Arten der Rekursion

Direkte Rekursion und indirekte Rekursion sind die zwei Arten der Rekursion.

Direkte Rekursion

Die rekursive Funktion ruft sich durch direkte Rekursion direkt in ihrem eigenen Körper auf.

void recursion() { ....recursion(); }

Im Code können wir sehen, dass die Funktion sich selbst in ihrem eigenen Körper oder in Klammern aufruft.

Indirekte Rekursion

Bei der indirekten Rekursion wird die Funktion indirekt im Rumpf einer anderen Funktion aufgerufen.

void func1() { ... func2(); }
void func2() { ... func1(); }

Fibonacci-Reihe

Die Fibonacci-Reihe ist eine Menge ganzer Zahlen, bei denen jede aufeinanderfolgende Zahl die Summe der beiden vorhergehenden ist. Die ersten beiden Zahlen, 0 und 1, und die dritte werden durch Addition der ersten beiden berechnet.

Die Formel zur Berechnung der Fibonacci-Reihe lautet:

Zum Beispiel 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Wir können sehen, dass das dritte Element, 1, die Summe von 0+1 ist. Ebenso ist die vierte Zahl, 2, die Summe der vorherigen Zahlen (1+1=2).

Daher können wir das nächste Element der Reihe als 21+34 = 55 vorhersagen.

Fibonacci-Reihe in C++

Um die Fibonacci-Reihe zu implementieren, können wir eine rekursive Funktion implementieren, die als Eingabe eine Zahl annehmen kann und die Fibonacci-Reihe dieser Menge druckt. Wenn der Benutzer beispielsweise 8 eingibt, drucken wir 8 Zahlen der Serie.

Code:

#include <iostream>
using namespace std;

int fibonacci(int num) {
  if (num <= 1) return num;
  return fibonacci(num - 1) + fibonacci(num - 2);
}

int main() {
  int num;
  cout << "Enter a number: ";
  cin >> num;
  for (int a = 0; a < num; a++) {
    cout << fibonacci(a) << " ";
  }
  return 0;
}

In der Hauptfunktion haben wir den Benutzer aufgefordert, eine Nummer einzugeben. Danach haben wir eine Schleife von 0 zu dieser Eingangszahl num durchlaufen und die Iteratorvariable a an die Fibonacci-Funktion übergeben.

Diese Schleife iteriert num mal die vom Benutzer eingegebene Zahl. In der Funktion Fibonacci haben wir eine if-Bedingung, die überprüft, ob die Zahl kleiner als 1 ist, und dann diese Zahl zurückgibt.

Andernfalls wird die Funktion fibonacci für num-1 und num-2 aufgerufen, da jede nächste Zahl der Reihe berechnet wird, indem die Summe der beiden vorherigen Zahlen gebildet wird, d. h. n-1 und n-2.

Ausgang:

Der Benutzer hat die Zahl 9 eingegeben, also wurde die Fibonacci-Reihe mit 9 Werten darin gedruckt.