wake-up-neo.com

Schwanzrekursion in C++

Kann mir jemand eine einfache rekursive Funktion in C++ zeigen?

Warum ist die Rekursion des Schwanzes besser, wenn überhaupt?

Welche anderen Rekursionsarten gibt es neben der Rekursion des Endes?

53
neuromancer

Eine einfache rekursive Funktion:

unsigned int f( unsigned int a ) {
   if ( a == 0 ) {
      return a;
   }
   return f( a - 1 );   // tail recursion
}

Schwanzrekursion ist im Grunde, wenn:

  • es gibt nur einen einzigen rekursiven Aufruf
  • dieser Aufruf ist die letzte Anweisung in der Funktion

Und es ist nicht "besser", außer in dem Sinne, dass ein guter Compiler die Rekursion entfernen und in eine Schleife verwandeln kann. Dies ist möglicherweise schneller und spart bei der Stack-Nutzung. Der GCC-Compiler kann diese Optimierung durchführen.

58
anon

Tail Recession in C++ sieht genauso aus wie C oder jede andere Sprache.

void countdown( int count ) {
    if ( count ) return countdown( count - 1 );
}

Die Rekursion für das Tail (und das Tail Call im Allgemeinen) erfordert das Löschen des Stackframes des Aufrufers, bevor das Tail Call ausgeführt wird. Für den Programmierer ist die Schwanzrekursion einer Schleife ähnlich, wobei return auf goto first_line; reduziert wird. Der Compiler muss jedoch erkennen, was Sie tun, und wenn dies nicht der Fall ist, wird noch ein zusätzlicher Stack-Frame vorhanden sein. Die meisten Compiler unterstützen dies, aber das Schreiben einer Schleife oder goto ist in der Regel einfacher und mit weniger Risiken verbunden.

Nichtrekursive Endaufrufe können eine zufällige Verzweigung (wie goto zur ersten Zeile einer anderen Funktion) ermöglichen, was eine einzigartigere Funktion darstellt.

Beachten Sie, dass sich in C++ kein Objekt mit einem nicht trivialen Destruktor im Geltungsbereich der return-Anweisung befinden kann. Für die Bereinigung nach Funktionsende muss der Angerufene zum Anrufer zurückkehren, wodurch der Rückruf entfällt.

Beachten Sie (in jeder Sprache), dass die Endrekursion bei jedem Schritt den gesamten Status des Algorithmus durch die Funktionsargumentliste durchläuft. (Dies ergibt sich aus der Anforderung, dass der Stack-Frame der Funktion vor dem nächsten Aufruf beseitigt werden muss ... Sie können keine Daten in lokalen Variablen speichern.) Außerdem kann auf den Rückgabewert der Funktion keine Operation angewendet werden, bevor der Rückgabewert zurückgegeben wird .

int factorial( int n, int acc = 1 ) {
    if ( n == 0 ) return acc;
    else return factorial( n-1, acc * n );
}
40
Potatoswatter

Schwanzrekursion ist ein Sonderfall eines Rückrufs. Bei einem Rückruf kann der Compiler erkennen, dass nach der Rückkehr von einer aufgerufenen Funktion keine Vorgänge ausgeführt werden müssen - die Rückkehr der aufgerufenen Funktion wird im Wesentlichen zu ihrer eigenen. Der Compiler kann oft einige Stack-Fix-Up-Operationen ausführen und dann an die Adresse des ersten Befehls der aufgerufenen Funktion springen (anstatt ihn aufzurufen).

Neben dem Beseitigen einiger Rückrufe ist es auch eine gute Sache, dass Sie die Stack-Nutzung reduzieren. Auf einigen Plattformen oder in Betriebssystemcode kann der Stack sehr begrenzt sein, und auf fortschrittlichen Maschinen wie den x86-CPUs in unseren Desktops führt die Verringerung der Stack-Nutzung zu einer Verbesserung der Datencache-Leistung.

In der Endrekursion entspricht die aufgerufene Funktion der aufrufenden Funktion. Dies kann in Schleifen umgewandelt werden, was genau dem Sprung in der oben genannten Optimierung der Rückrufe entspricht. Da dies die gleiche Funktion ist (callee und caller), müssen vor dem Sprung weniger Stapelkorrekturen durchgeführt werden.

Das Folgende zeigt eine gängige Methode, um einen rekursiven Aufruf durchzuführen, der für einen Compiler schwieriger wäre, sich in eine Schleife zu verwandeln:

int sum(int a[], unsigned len) {
     if (len==0) {
         return 0;
     }
     return a[0] + sum(a+1,len-1);
}

Dies ist so einfach, dass viele Compiler es wahrscheinlich trotzdem herausfinden könnten, aber wie Sie sehen, gibt es einen Zusatz, der erfolgen muss, nachdem die Rückgabe aus der gerufenen Summe eine Zahl zurückgibt, so dass eine einfache Optimierung des Rückrufaufrufs nicht möglich ist.

Wenn du. .. getan hast:

static int sum_helper(int acc, unsigned len, int a[]) {
     if (len == 0) {
        return acc;
     }
     return sum_helper(acc+a[0], len-1, a+1);
}
int sum(int a[], unsigned len) {
     return sum_helper(0, len, a);
}

Sie können die Anrufe in beiden Funktionen als Endrufe nutzen. Hier besteht die Hauptaufgabe der Summenfunktion darin, einen Wert zu verschieben und ein Register oder eine Stapelposition zu löschen. Der sum_helper erledigt alle Berechnungen.

Da Sie in Ihrer Frage C++ erwähnt haben, werde ich einige besondere Dinge dazu erwähnen. C++ verbirgt einige Dinge, die C nicht für Sie bereithält. Diese Destruktoren sind die Hauptsache, die der Optimierung der Rückrufe entgegenstehen wird.

int boo(yin * x, yang *y) {
    dharma z = x->foo() + y->bar();
    return z.baz();
}

In diesem Beispiel ist der Aufruf von baz nicht wirklich ein Schlussruf, da z nach der Rückkehr von baz zerstört werden muss. Ich glaube, dass die Regeln von C++ die Optimierung erschweren können, selbst wenn die Variable für die Dauer des Aufrufs nicht benötigt wird, z.

int boo(yin * x, yang *y) {
    dharma z = x->foo() + y->bar();
    int u = z.baz();
    return qwerty(u);
}

z muss nach der Rückkehr von qwerty hier möglicherweise zerstört werden.

Eine andere Sache wäre die implizite Typkonvertierung, die auch in C auftreten kann, aber in C++ komplizierter und üblicher sein kann.

static double sum_helper(double acc, unsigned len, double a[]) {
     if (len == 0) {
        return acc;
     }
     return sum_helper(acc+a[0], len-1, a+1);
}
int sum(double a[], unsigned len) {
     return sum_helper(0.0, len, a);
}

Hier ist der Aufruf von sum_helper kein Schwanzaufruf, da sum_helper ein Double zurückgibt und sum die Summe in ein int konvertieren muss.

In C++ ist es üblich, eine Objektreferenz zurückzugeben, die alle Arten von unterschiedlichen Interpretationen haben kann, von denen jede eine andere Typkonvertierung sein kann... Zum Beispiel:

bool write_it(int it) {
      return cout << it;
}

Hier wird ein Aufruf an cout.operator << als letzte Anweisung gemacht. cout gibt einen Verweis auf sich selbst zurück (weshalb Sie viele Dinge in einer durch << getrennten Liste zusammenfassen können), die Sie dann zwingen, als bool ausgewertet zu werden, wodurch eine andere Methode von cout aufgerufen wird, Operator bool ( ). Dieser cout.operator bool () kann in diesem Fall als Rückruf aufgerufen werden, der Operator << jedoch nicht.

BEARBEITEN:

Erwähnenswert ist, dass ein Hauptgrund für die Optimierung der Rückrufaufrufe in C darin besteht, dass der Compiler weiß, dass die aufgerufene Funktion ihren Rückgabewert an derselben Stelle speichert, an der die aufrufende Funktion ihren Rückgabewert sicherstellen muss gespeichert in.

26
nategoose

Tail-Rekursion ist auf Compiler-Ebene in C++ nicht wirklich vorhanden. 

Obwohl Sie Programme schreiben können, die die Tail-Rekursion verwenden, können Sie nicht die erblichen Vorteile der Tail-Rekursion durch Unterstützung von Compilern/Interpreten/Sprachen implementieren. Zum Beispiel unterstützt Scheme eine Optimierung der Schwanzrekursion, sodass die Rekursion im Wesentlichen in Iteration geändert wird. Dadurch werden Stapelüberläufe schneller und unverwundbarer. C++ hat so etwas nicht. (zumindest keinen Compiler, den ich gesehen habe)

Offensichtlich existieren Tail-Rekursionsoptimierungen sowohl in MSVC++ als auch GCC. Siehe diese Frage für Details.

1
Earlz

Wikipedia hat einen anständigen Artikel zur Rekursion des Schwanzes . Grundsätzlich ist die Rekursion des Endes besser als die normale Rekursion, da die Optimierung in einer iterativen Schleife unkompliziert ist und iterative Schleifen im Allgemeinen effizienter sind als rekursive Funktionsaufrufe. Dies ist besonders wichtig in funktionalen Sprachen, in denen Sie keine Schleifen haben.

Für C++ ist es immer noch gut, wenn Sie Ihre rekursiven Schleifen mit Tail-Rekursion schreiben können, da sie besser optimiert werden können. In solchen Fällen können Sie dies jedoch grundsätzlich nur iterativ tun, sodass der Gewinn nicht so groß ist, wie er es wäre in einer funktionalen Sprache sein.

0

Die Rekursion "Schwanz" ist ein Trick, um tatsächlich zwei Probleme gleichzeitig zu bewältigen. Die erste besteht darin, eine Schleife auszuführen, wenn die Anzahl der durchzuführenden Iterationen schwer zu ermitteln ist. 

Obwohl dies mit einer einfachen Rekursion herausgearbeitet werden kann, tritt das zweite Problem auf, das der Stapelüberlauf ist, da der rekursive Aufruf zu oft ausgeführt wird. Der Schlussruf ist die Lösung, wenn er von einer "compute and carry" -Technik begleitet wird. 

In Basic CS lernen Sie, dass ein Computeralgorithmus eine Invariante und eine Beendigungsbedingung haben muss. Dies ist die Basis für das Erstellen der Schwanzrekursion.

  1. Alle Berechnungen finden in der Argumentübergabe statt.
  2. Alle Ergebnisse müssen an Funktionsaufrufe übergeben werden.
  3. Der Schlussanruf ist der letzte Anruf und erfolgt bei Beendigung.

Um es einfach auszudrücken, musskeine Berechnung mit dem Rückgabewert Ihrer Funktionerfolgen.

Nehmen Sie zum Beispiel die Berechnung einer Potenz von 10, die trivial ist und von einer Schleife geschrieben werden kann.

Sollte ungefähr so ​​aussehen

template<typename T> T pow10(T const p, T const res =1)
{
return p ? res: pow10(--p,10*res);
}

Dies ergibt eine Ausführung, z. B. 4:

ret, p, res

-, 4,1

-, 3,10

-, 2.100

- 1,1000

- 0,10000 

10000, -, -

Es ist klar, dass der Compiler nur Werte kopieren muss, ohne den Stackzeiger zu ändern, und wenn der Abrufaufruf geschieht, um das Ergebnis zurückzugeben.

Die Rekursion von Tails ist sehr wichtig, da sie fertige Kompilierzeitauswertungen bereitstellen kann, z. Das obige kann gemacht werden.

template<int N,int R=1> struct powc10
{
int operator()() const
{
return  powc10<N-1, 10*R>()();
}
};

template<int R> struct powc10<0,R>
{

int operator()() const
{
return  R;
}

};

dies kann als powc10<10>()() verwendet werden, um die 10. Potenz zur Kompilierzeit zu berechnen. 

Bei den meisten Compilern gibt es ein Limit von verschachtelten Aufrufen, sodass der Trick beim Abruf des Abrufs hilfreich ist. Offensichtlich gibt es keine Meta-Programmierschleifen, daher müssen Sie Rekursion verwenden.

0
g24l