编译期与运行期对比：模板计算斐波那契为何快于运行时递归

• 计算阶段完全不同，运行时零计算开销
  模板元编程属于编译期执行的逻辑，你写的Fib<N>模板实例化过程，是编译器在生成可执行文件阶段就完成全部数值计算的。等程序真正运行到cout << Fib<100>::val这行的时候，这个值已经是硬编码在二进制里的常量，等价于你直接写cout << 354224848179261915075 << '\n'，CPU不需要执行任何加法、函数调用操作，直接取常量输出就行。
  而普通运行期递归的计算逻辑，是程序启动运行后才开始在CPU上执行，所有计算步骤都要占运行时的CPU时间，速度自然比不过零计算开销的编译期常量。
• 编译期模板实例化自带结果缓存，无重复计算
  编译器在实例化模板的时候，会自动缓存已经生成过的模板实例：比如计算Fib<100>需要Fib<99>和Fib<98>的结果，后续计算Fib<99>再需要Fib<98>的时候，编译器直接拿之前已经算好的Fib<98>::val值，不会重复展开计算，整体计算复杂度是O(n)。
  而最朴素的运行期斐波那契递归没有任何缓存机制，同一个序号的斐波那契值会被重复计算指数次，时间复杂度是O(2^n)，别说第100项，就算算第40项的耗时都已经能明显感知到。
• 无运行时函数调用额外开销
  朴素运行期递归每进入一层函数，都要执行栈帧开辟、参数传递、返回值回传、栈帧销毁的额外操作，指数级的函数调用次数会把这些开销堆得非常高。而编译期的模板计算是编译器内部的静态处理流程，根本不会生成对应的运行时函数调用指令，这类开销完全不存在。

你提到的编译期计算斐波那契第100项的示例代码如下：

#include <iostream>
using namespace std;

template<unsigned long long int I>
struct Fib
{
    static const unsigned long long int val = Fib<I - 1>::val + Fib<I - 2>::val;
};

template<>
struct Fib<0>
{
    static const unsigned long long int  val = 0;
};

template<>
struct Fib<1>
{
    static const unsigned long long int  val = 1;
};

int main()
{
    cout << Fib<100>::val << '\n';
    return 0;
}

注：如果给运行期递归加上记忆化缓存、或者开启最高级优化让编译器做常量折叠，两者的运行速度差距会缩小，但模板版本的计算是C++标准明确规定的编译期行为，不依赖编译器优化等级，一定能得到编译期就确定的常量结果，不会出现优化失效导致运行时额外计算的问题。

内容的提问来源于stack exchange，提问作者Abdullah_Shosha