Rekursion ist teuer? Falsch!

Welches Programm ist schneller?

int gcd (int x, int y) { // Rekursion:
  if (0==y) return x else return gcd(y,x%y);
}

int gcd (int x, int y) { // Schleife:
  while (0!=y) {int h = x%y ; x = y; y = h;}
  return x;
}
Antwort: keines, gcc erzeugt identischen Assemblercode.

Das funktioniert immer für Endrekursion (= die letzte Aktion eines Unterprogramms ist der rekursive Aufruf), diese kann durch Sprung ersetzt werden.


Johannes Waldmann 2012-06-25