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

Fib.cpp

// Fibonacci 


#include<math.h>
#include<vector>


// This slow machine will barely be able to compute Fib1(30) 
// O(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 = Fib2(n-1) + Fib2(n-2);
  FibCache.push_back(Fn);
  
  return Fn;
}


// O(1) in Runtime but O(2^n) in CompileTime 
// => but in Jyt CompileTime Is also RunTime!
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;
};


// Why does This work?

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://en.wikipedia.org/wiki/Golden_ratio#Relationship_to_Fibonacci_sequence