GCC Tail Call Optimization (?)

crt32

#include <iostream>
using namespace std;

int factorial(int n) {
	int fac = 1;
	for (int i = 2; i <= n; ++i)
		fac *= i;
	return fac;
}

int factorial2(int n) {
	return n <= 1 ? 1 : factorial2(n-1) * n;
}

int factorial3(int n, int r = 1) {
	return n <= 1 ? r : factorial3(n-1, n*r);
}

int main() {
	cout << factorial(50000000) << endl;
	cout << factorial2(50000000) << endl;
	cout << factorial3(50000000) << endl;
}

Wenn ich den Code mit g++ 4.5.2 compiliere, gibt es egal ob mit -O2, -Os oder -O3 ein keiner Stelle einen stack overflow.
Kann jemand erklären, wie die Rekursion in factorial2 hier weg-optimiert wird?

Unter g++ 4.2.1 allerdings wird die Rekusion in factorial2 nur mit -O2 weg-optimiert.
Mit -Os oder -O3 gibt es in factorial2 einen stack overflow, nicht aber in factorial3. (Wie es meiner Meinung nach auch sein sollte?)

Ich suche ein Beispiel, an dem man gut zeigen kann, wozu man tail recursion braucht. Ist halt etwas doof, wenn dann g++ 4.5.2 daher kommt und die nicht-tail-recursive Funktion auch noch weg-optimiert.

SeppJ

crt32 schrieb:

Ich suche ein Beispiel, an dem man gut zeigen kann, wozu man tail recursion braucht.

Hast du hier nicht ein ziemlich gutes Beispiel gefunden? Das würde sonst sicher schiefgehen und wäre ziemlich lahm. So kann der Comoiler eine Schleife draus machen.

Ist halt etwas doof, wenn dann g++ 4.5.2 daher kommt und die nicht-tail-recursive Funktion auch noch weg-optimiert.

Entweder ist der g++ ziemlich gut im Umstellen von ausdrücken oder er rechnet alles schon zur Compilezeit aus. Schließlich ist schon bekannt, welche Werte auftreten werden. Nimm mal als Werte keine Compilezeitkonstanten sondern Benutzereingaben und gib dann richtig große Werte ein.

edit: Und da es, wie camper sagt, undefiniertes Verhalten ist, wird eventuell alles wegoptimiert. Nimm daher auch mal einen unsigned Datentyp, bei dem ist definiert, was bei Überlauf passiert.

camper

Dieses Programm hat sowieso undefiniertes Verhalten, weil es ziemlich schnell zu integer-Überläufen kommt.

knivil

factorial2 ist rekursiv, kann aber sehr leicht vom Compiler in die endrekursive Variante umgeschrieben werden. Prinzipiell ist es ein fold-right ueber den natuerlichen Zahlen. Da die Multiplikation kommukativ ist, ist die Faltung von rechts aequivalent zur Faltung von links. Das erkennt und nutzt der Compiler. ... Falls du nur wenig verstanden hast, sollten in diesem Post genug Schluesselworte fuer google enthalten sein.

crt32

SeppJ schrieb:

crt32 schrieb:

Ich suche ein Beispiel, an dem man gut zeigen kann, wozu man tail recursion braucht.

Hast du hier nicht ein ziemlich gutes Beispiel gefunden? Das würde sonst sicher schiefgehen und wäre ziemlich lahm. So kann der Comoiler eine Schleife draus machen.

Mir gings halt darum, zu sehen, dass die Implementierung ohne tail recursion einen stack overflow produziert und die andere nicht.

SeppJ schrieb:

factorial2 ist rekursiv, kann aber sehr leicht vom Compiler in die endrekursive Variante umgeschrieben werden. Prinzipiell ist es ein fold-right ueber den natuerlichen Zahlen. Da die Multiplikation kommukativ ist, ist die Faltung von rechts aequivalent zur Faltung von links. Das erkennt und nutzt der Compiler.

Danke, ich wusste nicht, dass der Compiler das erkennen kann.