Recursive templates don't work as expected with static variables

Question

The code

#include <iostream>
using namespace std;

template<int n> struct Fibo { static int x; };
template<> int Fibo<0>::x = 1;
template<> int Fibo<1>::x = 1;
template<int n> int Fibo<n>::x = Fibo<n-1>::x + Fibo<n-2>::x; //marked line

int main() {
    cout << Fibo<5>::x << endl;
    cout << Fibo<4>::x << endl;
    cout << Fibo<3>::x << endl;
    cout << Fibo<2>::x << endl;
    cout << Fibo<1>::x << endl;
    cout << Fibo<0>::x << endl;

    return 0;
}

outputs

0
0
1
2
1
1

in VC++. (According to user M M. it compiles as expected in gcc). When the compiler gets to the marked line with n=5 it doesn't compile that same line again for n=4, but just treats Fibo<4>::x as if it were declared with

template<> int Fibo<4>::x; // x defaults to 0

Why is that? Why does it work as expected when using

template<int n> struct Fibo { enum { x = Fibo<n-1>::x + Fibo<n-2>::x }; };
template<> struct Fibo<0> { enum { x = 1 }; };
template<> struct Fibo<1> { enum { x = 1 }; };

instead, but not with a static variable? And how do you fix the first code (without enum)?

Mastoid

It compiles fine in gcc-4.8.0 and output is "8 5 3 2 1 1". – Bunker

Nice, I never knew you could specialize static member initializers. – Broca

Thanks, M M. I'll add a note saying I used VC++. – Mastoid

Order of initialisation of static variables... – Hogen

Clang outputs 0 0 1 2 1 1 – Semen

Answer 1

The Standard is very clear on this:

14.7.1 Implicit instantiation [temp.inst]

9 The implicit instantiation of a class template does not cause any static data members of that class to be implicitly instantiated.

All the calls in main() to your Fibo<n>::x for n > 1, are explicit instantiations, that through the Fibonnaci recursion will implicitly instantiate Fibo<n-1> and Fibo<n-2> but not their members x. This means that at those points, the static members x will be evaluated to their default initialization of 0. For n=1 and n=0, the compiler will see the explicit initialization values of 1. So effectively, you get the following computation

Fibo<5>::x --> Fibo<4>::x + Fibo<3>::x --> 0 + 0 = 0
Fibo<4>::x --> Fibo<3>::x + Fibo<2>::x --> 0 + 0 = 0
Fibo<3>::x --> Fibo<2>::x + Fibo<1>::x --> 0 + 1 = 1
Fibo<2>::x --> Fibo<1>::x + Fibo<0>::x --> 1 + 1 = 2
Fibo<1>::x --> 1
Fibo<0>::x --> 1

You need to instantiate the static member x before evaluating the Fibonacci recursion. You can do this through a static const int or enum member x, or through a function (possibly constexpr in C++11) as shown by @Jarod42.

Semen

Answer 2

I'm not sure if the initialization order of the static variables of template<int n> int Fibo<n>::x = Fibo<n-1>::x + Fibo<n-2>::x; is specified...

You may write this:

template <int N> struct Fibo { int operator()() const { static int x = Fibo<N - 1>()() + Fibo<N - 2>()(); return x; } };

template <> struct Fibo<1> { int operator()() const { static int x = 1; return x; } };
template <> struct Fibo<0> { int operator()() const { static int x = 1; return x; } };

The dependencies are respected.

[Edit]

In a case where the value may be modified (according to your comment), you may use similar technique but returning reference:

template <int N> struct Fibo {
private:
    int& operator()() { static int x = Fibo<N - 1>()() + Fibo<N - 2>()(); return x; }

public:
    int operator()() const { return const_cast<Fibo&>(*this)(); }
    // This change Fibo<0> and Fibo<1> and then update value up to Fibo<N>.
    int operator(int fibo0, int fibo1) {
        int n_1 = Fibo<N - 1>()(fibo1, fibo2);
        (*this)() = n_1 + Fibo<N - 2>()();
    }
};

template <> struct Fibo<1> {
private:
    int& operator()() { static int x = 1; return x; }
public:
    int operator()() const { return const_cast<Fibo&>(*this)(); }
    void operator(int fibo0, int fibo1) { Fibo<0>()(fibo0); (*this)() = fibo1; }
};

template <> struct Fibo<0> {
private:
    int& operator()() { static int x = 1; return x; }
public:
    int operator()() const { return const_cast<Fibo&>(*this)(); }
    void operator(int fibo0) { (*this)() = fibo0; }
};

Hogen

I used static members instead of enumerated types because I sometimes want to change their values during runtime. Of course, it doesn't make sense to change the Fibonacci sequence, but that was just a simple example to a much longer code I have that suffers the same issue. – Mastoid

So, instead of returning int, you may return int& in my example to modify the value later... – Hogen

Answer 3

The solution presented by @Jarod42 appears overly complicated to me.

Consider instead the simpler code below.

template<int N>
struct fib {
    static const int val = fib<N-1>::val + fib<N-2>::val;
};

template<>
struct fib<0> { static const int val = 0;};

template<>
struct fib<1> { static const int val = 1;};

int main() {
    std::cout << fib<45>::val << "\n";
    return 0;
}

Devotion