fibonacci template C++

fibonacci.cpp

template<int n>
struct fibonacci
{
  static constexpr int value = fibonacci<n-1>::value + fibonacci<n-2>::value;
};
template<>
struct fibonacci<0>
{
  static constexpr int value = 0;
};
template<>
struct fibonacci<1>
{
  static constexpr int value = 1;
};

int main()
{
    fibonacci<40>::value;
    return 0;
}

I'd like to know the complexity of this algorithm and if it's more efficient than the usual recursive algorithm which is: `int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); }

int main () { int n = 9; cout << fib(n); getchar(); return 0; }`

The template implementation is constant-time at runtime; it's evaluated at compile time. But it only works for expressions that can be evaluated at compile time - it wouldn't work for your main (because "n" isn't constant), and it wouldn't work if "n" were read from stdin; for that you'd need the usual function implementation.

Compile time implementation for the iterative approach. Which one would you use and why?

#include <iostream> 
template <unsigned N> 
struct Fibonacci 
{ 
    enum 
    { 
        prev = Fibonacci<N-1>::curr, 
        curr = Fibonacci<N-1>::curr + Fibonacci<N-1>::prev 
    }; 
}; 
template <> 
struct Fibonacci<1> { 
    enum { 
        prev = 0, 
        curr = 1 
    }; 
}; 

template <> 
struct Fibonacci<0> { 
    enum { 
        curr = 0, prev = 0 
    }; 
}; 


int main() { std::cout << Fibonacci<10>::curr << std::endl; }

Does this have an equivalent in Go after the introduction of generics?

Using

template <unsigned long long n>
struct fib {
    enum : unsigned long long { result = fib<n - 1>::result + fib<n - 2>::result };
};
template<> struct fib<0> { enum { result = 0 }; };
template<> struct fib<1> { enum { result = 1 }; };

OR

template <unsigned long long n>
struct fib {
    static constexpr unsigned long long result = fib<n - 1>::result + fib<n - 2>::result;
};
template<> struct fib<0> { static constexpr int result = 0; };
template<> struct fib<1> { static constexpr int result = 1; };

you an compute up-to fib<105>::result which is 17704020980446223138.