Verständnisfrage zu rekursiver Templatefunktion

Hallo, ich wollte eine Funktion schreiben, die mir zur Compilezeit die Fakultät einer Zahl ausgibt:

template<int N> static int fak()
{
    if     (N<=1) return 1;
    else if(N==2) return 2;
    else          return N*fak<N-1>();
}

int main()
{
    const int test = fak<1>();
}

Allerdings verweigern meine Compiler das Kompilieren (GCC sagt, die Templatetiefe von 500 würde überschritten, Microsoft sagt, die Funktion sei zu komplex). Dabei würde obiger Code die Funktion doch garnicht rekursiv aufrufen. Wieso verweigern meine Compiler ihren Dienst? Kann man das Problem überhaupt so lösen?

oneill5000

Ich denke mal der Compiler wird bei so einer Funktion nicht "gucken", wie du sie aufrufst, sondern wie sie aufgebaut ist. Und bei einem beispielsweise 32Bit integer, kann deine Funktion ganz schön oft Rekusrsiv aufgerufen werden. Was ihm wohl nicht gefällt.

pumuckl

Zur Erklärung: der Compiler sieht beim Instantiieren von fak<2>, dass darin fak<1> benutzt wird, instantiiert dies, sieht, dass darin fak<0> benutzt wird, instanttiiert dies, sieht dass darin fak<-1> benutzt wird, instantiiert dies,...

Dass die Funktionen die er da instantiiert nie aufgerufen werden kratzt ihn erstmal garnicht. Die einzige Möglichkeit ist, die Rekursion durch Spezialisierungen abzubrechen, z.B. wie folgt:

template<int N> int fak()
{
  return N*fak<N-1>();
}

template <> int fak<0>()
{ 
  return 1;
}

Das sollte reichen. Der Wert wird dann allerdings eigentlich immernoch zur Laufzeit berechnet (bei guter Optimierung vermutlich nicht mehr).

Mit einem struct ist das alles Compilezeit-Angelegenheit:

template <int N> 
struct Fak
{
  const static int value = N*Fak<N-1>::value;
};
template<>
struct Fak<0>
{
  const static int value = 1;
};

Das mit der Rekursionstiefe bei template-instantiierungen ist leider tatsächlich ein Manko. Auf dem Forentreffen hatten wir eine kleine Aufgabe, eine Abwandlung von Joseph's Problem. Die konnte auch durch Metaprogrammierung gelöst werden, allerdings nur für sehr kleine Werte (1 bis 6 oder so), danach war vorbei wegen der Rekursionstiefe