Ist eine Rekursion jemals schneller als eine Schleife?

Question

Ich weiß, dass die Rekursion manchmal viel sauberer ist als eine Schleife, und ich frage nicht, wann ich die Rekursion über die Iteration verwenden sollte, ich weiß, dass es bereits viele Fragen dazu gibt.

Meine Frage ist: Ist Rekursion immer schneller als eine Schleife? Mir scheint, dass man eine Schleife immer verfeinern und schneller ausführen kann als eine rekursive Funktion, weil die Schleife nicht ständig neue Stackframes aufbaut.

Ich bin speziell auf der Suche danach, ob die Rekursion in Anwendungen schneller ist, in denen die Rekursion der richtige Weg ist, um die Daten zu verarbeiten, wie z. B. in einigen Sortierfunktionen, in binären Bäumen, usw.

Answer 1

Dies ist eine Vermutung. Im Allgemeinen schlägt Rekursion wahrscheinlich nicht oft oder nie Schleifen auf Probleme von anständiger Größe, wenn beide wirklich gute Algorithmen verwenden (ohne Berücksichtigung der Implementierungsschwierigkeiten), kann es anders sein, wenn mit einer Sprache verwendet w/ Heckaufruf-Rekursion (mit einem rekursiven Algorithmus und mit Schleifen als Teil der Sprache), die wahrscheinlich eine sehr ähnliche Rekursion haben und möglicherweise sogar einige Zeit vorziehen würden.

Answer 2

Der Theorie nach ist es dasselbe. Rekursion und Schleife mit der gleichen O()-Komplexität arbeiten mit der gleichen theoretischen Geschwindigkeit, aber natürlich hängt die reale Geschwindigkeit von Sprache, Compiler und Prozessor ab. Ein Beispiel mit einer Potenz der Zahl kann in der Iterationsform mit O(ln(n)) kodiert werden:

  int power(int t, int k) {
  int res = 1;
  while (k) {
    if (k & 1) res *= t;
    t *= t;
    k >>= 1;
  }
  return res;
  }