**标题：**

作者

如何在 C++20 中实现 constexpr 递归函数？

正文：
在 C++20 之前，constexpr 函数只能包含非常有限的语言特性——没有循环、没有 if 语句、没有异常处理，甚至不允许递归。随着标准的演进，C++20 将 constexpr 允许使用几乎所有编译期可求值的语句，使得我们可以在编译期完成复杂计算。本文将演示如何在 C++20 中实现一个递归 constexpr 函数，计算斐波那契数列，并讨论其使用场景、实现细节与性能考虑。

1. 先决条件

  • 编译器支持：确保使用支持 C++20 的编译器，例如 GCC 11+、Clang 13+ 或 MSVC 16.11+。
  • 编译命令：g++ -std=c++20 -O2 -march=native main.cpp。
  • constexpr 规则：在 C++20 中，constexpr 函数可以：
    • 包含 if、switch、循环 (for, while, do-while)。
    • 包含非 constexpr 函数的调用（只要它们本身是 constexpr）。
    • 触发 static_assert。
    • 产生运行时错误（使用 throw 语句）。

2. 斐波那契数列的递归实现

斐波那契数列定义为：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)   (n >= 2)

下面给出一个 constexpr 递归实现。

#include <iostream>
#include <array>
#include <stdexcept>

// 递归 constexpr 斐波那契
constexpr std::uint64_t fib(unsigned n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

2.1 编译期求值

我们可以直接在编译期使用 constexpr 变量或 static_assert 进行检查。

constexpr std::uint64_t f20 = fib(20);   // 约 6 秒的编译时间取决于 n
static_assert(f20 == 6765, "fib(20) 必须等于 6765");

如果把 f20 用作 constexpr 变量，编译器会在编译期求值 fib(20)。如果值不匹配，编译器报错。

2.2 递归深度限制

C++20 标准对递归深度没有硬性限制，但编译器会受到栈深度和模板实例化次数的限制。对于较大的 n，递归会导致编译时间变长，甚至超出编译器最大递归深度。通常 n <= 40 在大多数编译器下能正常编译。

3. 迭代版与尾递归

递归实现直观，但编译器优化并不总是将其转化为迭代代码。C++20 引入了 constexpr 循环，允许我们用迭代方式实现相同功能，同时减少编译时间。

constexpr std::uint64_t fib_iter(unsigned n) {
    std::uint64_t a = 0, b = 1;
    for (unsigned i = 0; i < n; ++i) {
        std::uint64_t tmp = a + b;
        a = b;
        b = tmp;
    }
    return a;
}

fib_iter 与 fib 结果相同，但编译时会更快，尤其是 n 较大时。

4. 使用模板元编程的比较

除了 constexpr 函数，C++ 模板元编程也能在编译期计算斐波那契：

template <unsigned N>
struct fib_t {
    static constexpr std::uint64_t value = fib_t<N-1>::value + fib_t<N-2>::value;
};

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

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

`fib_t

::value` 在编译期被实例化。与 `constexpr` 递归相比，模板元编程更易受编译器实例化深度限制，但可以利用模板特化避免无谓的递归。 — ### 5. 运行时 vs 编译时 – **编译时**：若 `n` 是常量表达式，编译器会在编译期求值，生成的二进制中不包含递归代码。适用于需要在运行时访问常量表、减少运行时开销的场景。 – **运行时**：若 `n` 是动态值，则 `constexpr` 递归会被降级为普通函数，在运行时执行。此时使用迭代版更高效。 — ### 6. 性能比较（示例） “`cpp int main() { constexpr auto val1 = fib(20); constexpr auto val2 = fib_iter(20); std::cout

发表评论