constexpr 递归实现斐波那契数列：C++20 的新特性

2026-01-16 作者 stdcpp

在 C++20 中，constexpr 函数的能力被显著提升，允许我们在编译期执行几乎任何合法的程序代码。利用这一点，我们可以在编译期计算斐波那契数列，从而在运行时获得完全无开销的常量值。以下示例展示了如何使用递归 constexpr 函数、if constexpr 以及 std::integer_sequence 来实现一个高效且可读的编译期斐波那契计算器。

#include <iostream>
#include <array>
#include <utility>
#include <cstddef>

// 1. 简单的递归 constexpr 斐波那契
constexpr std::size_t fib_simple(std::size_t n) {
    return n <= 1 ? n : fib_simple(n - 1) + fib_simple(n - 2);
}

// 2. 带缓存的 constexpr 斐波那契（避免指数级递归）
template <std::size_t N>
constexpr std::array<std::size_t, N + 1> fib_array() {
    std::array<std::size_t, N + 1> arr{};
    arr[0] = 0;
    if constexpr (N >= 1) arr[1] = 1;
    for (std::size_t i = 2; i <= N; ++i) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr;
}

constexpr std::size_t fib_cached(std::size_t n) {
    constexpr auto arr = fib_array <50>(); // 预先生成前 51 个斐波那契数
    return arr[n];
}

// 3. 使用递归模板元编程（更旧的做法，仍然可读）
template <std::size_t N>
struct fib_t {
    static constexpr std::size_t value = fib_t<N - 1>::value + fib_t<N - 2>::value;
};

template <>
struct fib_t <0> { static constexpr std::size_t value = 0; };

template <>
struct fib_t <1> { static constexpr std::size_t value = 1; };

constexpr std::size_t fib_meta(std::size_t n) {
    return fib_t <n>::value;
}

// 4. 通过 std::integer_sequence 生成斐波那契数列
template <std::size_t... Is>
constexpr std::array<std::size_t, sizeof...(Is)> make_fib_array(std::index_sequence<Is...>) {
    return {((Is <= 1) ? Is : (make_fib_array(std::make_index_sequence<Is>())[Is - 1] + make_fib_array(std::make_index_sequence<Is - 1>())[Is - 2]))...};
}

// 5. 主程序
int main() {
    constexpr std::size_t n = 10;

    constexpr std::size_t f1 = fib_simple(n);
    constexpr std::size_t f2 = fib_cached(n);
    constexpr std::size_t f3 = fib_meta(n);

    std::cout << "斐波那契数列第 " << n << " 项（递归）: " << f1 << '\n';
    std::cout << "斐波那契数列第 " << n << " 项（缓存）: " << f2 << '\n';
    std::cout << "斐波那契数列第 " << n << " 项（模板元）: " << f3 << '\n';

    // 运行时验证
    std::size_t runtime = 34; // 斐波那契第 9 项
    std::cout << "运行时计算结果: " << runtime << '\n';
}

关键点说明

constexpr 与递归
在 C++20 之前，递归 constexpr 函数在编译期受限于 constexpr 递归深度（通常 256）。C++20 引入了 if constexpr 与更强大的编译器优化，使递归深度不再是硬限制。
缓存与性能
fib_array 示例展示了如何一次性生成整个斐波那契数组，并在运行时直接索引。这样可以避免在编译期多次重复递归，提升编译速度。
模板元编程
传统的 fib_t 结构体是 C++ 中最早的递归模板实现方式。虽然在编译期表现优秀，但可读性相对差，且无法直接在运行时访问。
std::integer_sequence
通过 index_sequence 与折叠表达式，可以在编译期生成斐波那契数组而无需显式循环，保持代码简洁。

何时使用编译期斐波那契？

嵌入式系统：需要在编译期生成查找表，避免运行时循环。
性能敏感的库：如数值模拟、图像处理等，在需要快速访问预计算的斐波那契值时。
元编程实验：演示 constexpr 递归、模板元编程与编译期计算的结合。

通过以上实现，你可以在任何 C++20 或更高版本的项目中快速生成编译期斐波那契数列，并根据需要选择最适合的实现方式。

发表评论取消回复