Was ist der Unterschied zwischen einer rekursiven Version von "find" und einer nicht rekursiven Version?

Question

In dem Buch Accelerated C++ Programmierung, auf Seite 205, gibt es die beiden folgenden Umsetzung find

template <class In, class X> In find(In begin, In end, const X& x) 

Ich bin interessiert zu wissen, was in Bezug auf die Leistung jeder Unterschied ist (ob es tatsächlich das gleiche nach ist die Kompilierung?) der folgenden zwei Implementierungen.

nicht-rekursive

template <class In, class X> In find(In begin, In end, const X& x) 
{ 
    while (begin != end && *begin != x) 
     ++begin; 
    return begin; 
} 

rekursive

template <class In, class X> In find(In begin, In end, const X& x) 
{ 
    if (begin == end || *begin == x) 
     return begin; 
    begin++; 
    return find(begin, end, x); 
} 

Durch die Verwendung von Compiler Explorer von Kerrek schlug ich bekam die folgende

nicht-rekursive https://godbolt.org/g/waKUF2

rekursive https://godbolt.org/g/VKNnYZ

Es scheint genau dasselbe nach der Kompilierung zu sein? (Wenn ich das Tool richtig verwende .. Sorry, ich bin sehr neu in C++)

Answer 1

rekursive Funktionen werden zusätzlich Elemente auf dem Stapel hinzufügen. Dies kann je nach Status des Stapels vor dem Start der Rekursion und der Anzahl der Wiederholungen zu Stackoverflow-Fehlern führen.

Jeder Funktionsaufruf schiebt Daten auf den Stapel, der die Rücksprungadresse enthält. Dies wird fortgesetzt, bis die Daten gefunden sind. Zu diesem Zeitpunkt beginnen alle Funktionen, den Wert zurückzugeben, den die letzte Funktion zurückgegeben hat, bis wir schließlich zu der Funktion zurückkehren, die das Original find aufgerufen hat.

Die genaue Menge der für jeden Funktionsaufruf gespeicherten Daten hängt von der Aufrufkonvention und der Architektur ab. Es gibt auch einen Overhead beim Schieben von Daten auf den Stapel, was den Algorithmus verlangsamen kann, aber das hängt vom Algorithmus ab.

Dies ist ausschließlich für die Rekursion, die nicht Tail Call optimiert ist.

Answer 2

Zum größten Teil ist die Rekursion langsamer und nimmt auch mehr vom Stack auf. Der Hauptvorteil der Rekursion besteht darin, dass sie für Probleme wie das Traversieren von Bäumen den Algorithmus etwas einfacher oder "eleganter" macht.

prüfen einige der Vergleiche aus: Recursion vs Iteration