深入理解编译期斐波那契数列计算

C++ 中一个常见的“面试题”是借助 template 及模板元编程相关机制计算斐波那契数列。其实现并不复杂：

#include <iostream>

template <unsigned int n>
struct Calculator
{
    static const unsigned int value = Calculator<n - 1>::value + Calculator<n - 2>::value;
};

template <>
struct Calculator<1>
{
    static const unsigned int value = 1;
};

template <>
struct Calculator<2>
{
    static const unsigned int value = 1;
};

template <unsigned int n>
const unsigned int fibonacci = Calculator<n>::value;

int main(void)
{
    std::cout << fibonacci<5> << std::endl;
}

其核心在于 C++ 特有的模板参数推导与匹配机制；这一机制实质上引入了分支选择：编译器会优先匹配“更适合”的参数。因此，我们将模板参数 n 取 1 与 2 的情形特化为递归终点。

同一思路在模板偏特化中也十分典型：

#include <iostream>

template <typename T>
struct is_pointer
{
    static const bool value = false;
};

template <typename T>
struct is_pointer<T *>  // 偏特化！
{
    static const bool value = true;
};

template <>
struct is_pointer<decltype(nullptr)>
{
    static const bool value = true;
};

template <typename T>
const bool is_pointer_v = is_pointer<T>::value;

int main(void)
{
    std::cout << is_pointer_v<decltype(nullptr)> << std::endl;
    std::cout << is_pointer_v<decltype(2)> << std::endl;
    std::cout << is_pointer_v<decltype(&std::cout)> << std::endl;
}

当表达式为 &std::cout 时，C++ 会匹配更合适的模板形式 T *，于是 value 被设定为 true。

当然，“更合适”只是便于叙述的说法；在标准层面，C++ 对推导与匹配过程有严格而细密的规定。

需要注意的是，软件工程中早已有一条近乎冷酷的定律：复杂度不会消失，只会转移。模板实例化中的这类计算器，本质上是把原本属于运行期计算的复杂度平移到编译期。在绝大多数场景下，这一交换是值得的，因为我们审视实际上线的代码时通常采用渐进复杂度的框架：优化更关心增长率，尽管用户体验又提出了一个并不温和的补充命题——在相当多场景中，常数时间的改善同样不应被轻视。

然而，作为现代 C++ 滥觞的 C++11，为这类编译期计算提供了更直接的选择：constexpr。

我们实际上只是在以绕行方式实现下列函数所表达的计算：

int fibonacci(int n)
{
    if (n == 1 or n == 2)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

过去真正的瓶颈在于，编译器并不知道这段计算应当被挪至编译期完成，于是我们只能借助 template 迫使编译器进行计算。若审视编译器本身，其真正强大之处在于它维护并运用类型信息；编译过程在相当意义上是在完成一组构造性证明，而优化的边界，正是编译器所拥有信息的边界。因此，更自然的解决方式是向编译器显式提供信息，使其能够完成编译期求值；这正是 constexpr 的位置。

它向编译器建议在编译期完成计算：

#include <iostream>

// 使用 constexpr 函数，可以进行编译期求值。
constexpr int fibonacci(int n)
{
    // C++14 之后，constexpr 函数体内可以容纳更丰富的控制逻辑，
    // 形式上已相当接近普通函数。
    if (n == 1 or n == 2)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

int main(int argc, char *argv[])
{
    // fibonacci(10) 是常量表达式，编译器可以在编译期直接求值。
    std::cout << fibonacci(10) << std::endl; // 编译后这里直接就是 std::cout << 55 << std::endl;

    // 也可以用它来定义数组大小。
    int arr[fibonacci(6)] = {}; // 定义一个大小为 8 的数组
    std::cout << "Array size: " << sizeof(arr) / sizeof(int) << std::endl;
}

不过问题也正在这个“建议”之中；正如 C++ 模板存在递归深度限制一样，面对过深的编译期运算，或面对编译器无法确认其为常量表达式的语境，constexpr 仍可能退回运行期求值。若要消除这种“建议性”，可以使用 consteval 关键字：二者都属于向编译器提供信息、从而扩大优化空间的语言设施。

这里有必要单独澄清斐波那契计算本身的复杂度。在前面的模板元编程示例中，每一个 Calculator<n> 都是一个独立类型；维护类型信息的编译器会保存这些实例，因此不会反复计算相同的子结构。其算法复杂度并非 $O(2^n)$，而是 $O(n)$：我们实际上只需要从 1 到 n 的每一种情形各计算一次，而通常 RAM 模型中的随机访问可视为常数时间。至于后面的 constexpr 方法，从现代主流编译器实现的角度看，在较高优化等级下处理常量求值上下文时，编译器通常也会通过记忆化避免重复劳动。因此，在实践中，fibonacci(10) 这类递归常量求值的编译耗时也更接近线性复杂度 $O(n)$，而非指数级。

当然，C++17 之后，constexpr 还获得了某种近似“编译期分支重载”的表达能力，即 if constexpr：它在编译期完成判断，并直接丢弃无效分支的代码：

#include <iostream>
#include <type_traits>

template<typename T>
void print_info(T value) 
{
    if constexpr (std::is_pointer_v<T>) 
    {
        // 如果 T 不是指针，下面这整块代码（包括花括号）
        // 都会被编译器丢弃，等同于从未进入实例化路径。
        // 因此即使 T 是 int，*value 这样的语法也不会导致编译失败。
        std::cout << "It's a pointer to: " << *value << std::endl;
    } 
    else 
    {
        // 反之，如果 T 是指针，这块代码会被丢弃。
        std::cout << "It's a value: " << value << std::endl;
    }
}

总的来说，这体现了 C++ 将更多语义前移至编译期处理的总体倾向。

当然，如果坚持使用可读性极差的模板元编程来构造计算器，或者只是有意试探一些边缘技法，constexpr 仍然有其用武之地：它可以制造编译期对象，并在功能表达与可读性之间提供一次相当显著的改善。

#include <iostream>

struct Point 
{
    double x, y;

    // 第一步：提供 constexpr 构造函数。
    // C++11 要求构造函数体为空，只能使用初始化列表。
    // C++14 之后限制放宽，函数体内可以包含更复杂的逻辑。
    constexpr Point(double x_val, double y_val) : x(x_val), y(y_val) {}

    // 第二步：希望在编译期调用的成员函数，也必须声明为 constexpr。
    constexpr double length_sq() const 
    {
        return x * x + y * y;
    }
    
    // 第三步（隐式）：析构函数必须是平凡的 (trivial)。
    // 默认析构函数即为平凡析构函数，因此无需显式写出。
    // ~Point() = default;
};

int main() 
{
    // 在编译期创建 Point 对象。
    constexpr Point p1(3.0, 4.0);
    constexpr Point p2(5.0, 12.0);

    // 在编译期调用成员函数，计算另一个常量。
    constexpr double len_sq = p1.length_sq(); // 编译器直接算出 25.0

    // 使用这一编译期计算结果定义数组。
    int my_array[static_cast<int>(len_sq)]; // 创建一个大小为 25 的数组
    std::cout << "Array size: " << std::size(my_array) << std::endl;

    // 还可以在编译期对这些对象进行运算。
    constexpr Point p3(p1.x + p2.x, p1.y + p2.y); // p3 是 (8.0, 16.0)
    
    std::cout << "p3.x = " << p3.x << std::endl; // 这行代码在编译后，可能直接变成了 std::cout << "p3.x = " << 8.0 << std::endl;
}

总的来说，我想指出的是：编译器优化的历史近似一场开源节流，一方面依赖优化算法自身的进步，另一方面则依赖我们向编译器提供更多信息，以推移语义约束的边界。如果从现代 C++ 的视角审视模板元编程，仍应回到 template 抽象一类过程、服务于 policy-driven 设计的本义；用模板实现编译期斐波那契数列计算，更多是 C++11 之前不得不采取的技术折返，而模板递归实例化也正是所谓“模板天书”的重要源泉。