C++
Rekursion in C ++

Verwenden der Schwanzrekursion und Fibonnaci-Rekursion, um die Fibonnaci-Sequenz zu lösen

Der einfachste und naheliegendste Weg, Rekursion zu verwenden, um den N-ten Term der Fibonnaci-Sequenz zu erhalten, ist dies

int get_term_fib(int n)
{
  if (n == 0)
    return 0;
  if (n == 1)
    return 1;
  return get_term_fib(n - 1) + get_term_fib(n - 2);
}

Dieser Algorithmus skaliert jedoch nicht für höhere Ausdrücke: Für immer größere n nimmt die Anzahl der Funktionsaufrufe, die Sie machen müssen, exponentiell zu. Dies kann durch eine einfache Schwanzrekursion ersetzt werden.

int get_term_fib(int n, int prev = 0, int curr = 1)
{
  if (n == 0)
    return prev;
  if (n == 1)
    return curr;
  return get_term_fib(n - 1, curr, prev + curr);
}

Jeder Aufruf der Funktion berechnet jetzt sofort den nächsten Term in der Fibonnaci-Sequenz, sodass die Anzahl der Funktionsaufrufe linear mit n skaliert.

Rekursion mit Memoisierung

Rekursive Funktionen können recht teuer werden. Wenn es sich um reine Funktionen handelt (Funktionen, die beim Aufruf mit denselben Argumenten immer denselben Wert zurückgeben und die weder vom externen Zustand abhängen noch diesen ändern), können sie auf Kosten des Speichers durch Speichern der bereits berechneten Werte erheblich schneller gemacht werden.

Das Folgende ist eine Implementierung der Fibonacci-Sequenz mit Memoisierung:

#include <map>

int fibonacci(int n)
{
  static std::map<int, int> values;
  if (n==0 || n==1)
    return n;
  std::map<int,int>::iterator iter = values.find(n);
  if (iter == values.end())
  {
    return values[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  else
  {
    return iter->second;
  }
}

Beachten Sie, dass diese Funktion trotz der einfachen Rekursionsformel beim ersten Aufruf $ O (n) $ ist. Bei nachfolgenden Aufrufen mit dem gleichen Wert ist es natürlich $ O (1) $.

Beachten Sie jedoch, dass diese Implementierung nicht wiedereintrittsfähig ist. Außerdem können gespeicherte Werte nicht gelöscht werden. Eine alternative Implementierung wäre, die Map als zusätzliches Argument übergeben zu lassen:

#include <map>

int fibonacci(int n, std::map<int, int> values)
{
  if (n==0 || n==1)
    return n;
  std::map<int,int>::iterator iter = values.find(n);
  if (iter == values.end())
  {
    return values[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  else
  {
    return iter->second;
  }
}

Bei dieser Version muss der Anrufer die Karte mit den gespeicherten Werten verwalten. Dies hat den Vorteil, dass die Funktion jetzt wiedereintrittsfähig ist und der Aufrufer nicht mehr benötigte Werte entfernen kann, um Speicherplatz zu sparen. Es hat den Nachteil, dass es die Einkapselung bricht; Der Aufrufer kann die Ausgabe ändern, indem er die Karte mit falschen Werten auffüllt.