Gist created by https://fiddle.jyt.io

Fib.cpp

// Fibonacci 
//press play and call a function from the terminal on the right hand side


#include<math.h>
#include<vector>
#include<functional>
#include<tuple>
#include<algorithm>

// O(n)
constexpr auto FibW(size_t n) {
  auto a = 0;
  auto b = 1;
  while(n--) {
    b += a;
    a = b-a;
  }
  return a;
}

// This slow machine will barely be able to compute FibR(30) 
// O(2^n)
constexpr auto FibR(size_t n) {
  if(n<2) {
    return n;
  } else {
    return FibR(n-1) + FibR(n-2);
  }
}


// Dynamic programming to the rescue! 
// bestcase: O(1) worstcase: O(n)
static std::vector<size_t> FibCache={0,1,1};
auto FibD(size_t n) {
  if( FibCache.size() > n ) { 
    return FibCache[n];
  }
  
  auto Fn = FibD(n-1) + FibD(n-2);
  FibCache.push_back(Fn);
  
  return Fn;
}


// O(1) in Runtime and O(n) in CompileTime 
template<size_t n>
struct Fib_t {
  static constexpr size_t value = 
    Fib_t<n-1>::value + Fib_t<n-2>::value; 
};

template<>
struct Fib_t<0> {
  static constexpr size_t value = 0;
};

template<>
struct Fib_t<1> {
  static constexpr size_t value = 1;
};


// https://en.wikipedia.org/wiki/Golden_ratio#Relationship_to_Fibonacci_sequence
const static long double G =  1.61803398874989484820;
const static long double Gn = 0.61803398874989484820;

size_t FibG(size_t n) {
  return (pow(G, n) + pow(Gn, n)) / sqrt(5);
}


// https://yongweiwu.wordpress.com/2014/12/14/y-combinator-and-cplusplus/
using std::function;
template<class F>
struct self_ref_func {
  function<F(self_ref_func)> fn;
};

template<class R, class T>
auto Y(function<function<R(T)>(function<R(T)>)> f) {   
  // Y = f.(Lx.x x) (Lx.f (Ly.(x x) y))
  using fn_1ord = function<R(T)>;
  using fn_self_ref = self_ref_func<fn_1ord>;
  fn_self_ref r = {[f](fn_self_ref x) {   
    // Lx.f (Ly.(x x) y)
    return f(fn_1ord([x](T y) {
      return x.fn(x)(y);
    }));
  }};
  return r.fn(r);
}

auto FibYC = Y<size_t, size_t>([](auto F) {
  using ReturnType = decltype(F(0));
  auto static FibCache = std::vector<ReturnType>{0, 1, 1};  
  return [F](auto n) mutable {
    if(FibCache.size()>n) return FibCache[n];
    auto fn = F(n-2) + F(n-1);
    FibCache.push_back(fn);
    return fn;
  };
});

//O(n)
auto lazyFib = []{
  return [a=0l, b=1l]() mutable {
    std::tie(a,b) = std::make_tuple(b,a+b);
    return b-a;
  };
};

auto generateN = [](auto g, size_t n) {
  std::vector<decltype(g())> v(n);
  std::generate(v.begin(),v.end(), g);
  return v;
};
// generateN(lazyFib(),50)[49]


// [fn, fn-1] = [[1,1],[1,0]]^n * [1,0]
// O(log2(n))
auto FibMat = [](size_t n) {
  if(n<2) return n;
  size_t v[4] = {1, 1, 1, 0}; 
  for (int bi=log2(n)-1; bi>=0; --bi) { // fast matrix-exponentiation
    bool b = (n&(1<<bi))? 1 : 0;
    auto sq = v[2]*v[2];
    std::tie(v[1], v[2], v[3]) = std::make_tuple(
      pow(v[1], 2) + sq, 
      (v[1]+v[3])*v[2], 
      sq+pow(v[3], 2)
    );
    if(b) {
      std::tie(v[1], v[2], v[3]) = std::make_tuple(v[1]+v[2], v[1], v[2]);
    }
  }
  return v[2];
};