C++：尝试通过组合和帕斯卡三角来理解 constexpr

Question

我知道 constexpr 应该允许消除/简化过去使用的许多模板编程技巧，但我对 C++11 还是很陌生，我无法理解为什么，在计算组合函数时：

C(n,r) = n!/(r!(n-r)!) = C(n-1,r-1) + C(n-1,r)

递归方法，如预期的那样在运行时执行时速度慢得离谱，但允许计算 C(n,r) 更大的值，适用于模板，但我无法使用它constexpr。这是我正在使用的模板代码：

using factorial_t = unsigned long long;

template<size_t N, size_t R>
struct recursive_combinations {
    enum: factorial_t { value = recursive_combinations<N-1, R>::value +
                                recursive_combinations<N-1, R-1>::value};
};

template<size_t N>
struct recursive_combinations<N,0> {
    enum: factorial_t { value = 1 };
};

template<size_t N>
struct recursive_combinations<N,N> {
    enum: factorial_t { value = 1 };
};

这里是 constexpr 版本（也许我在这里做错了什么）：

constexpr const factorial_t recursiveCombinations(const size_t N, const size_t R) {
    if (R == N || R == 0) return 1;
    return recursiveCombinations(N-1, R) + recursiveCombinations(N-1, R-1);
}

当我尝试这个时：

constexpr auto comb1_50_30 = recursive_combinations<50,30>::value;

一切正常，我得到了预期结果47,129,212,243,960，这是计算阶乘得不到的

但是，当我尝试这样做时：

constexpr auto comb2_50_30 = recursiveCombinations(50, 30);

编译器（clang v5.0.1，设置为C++17模式）抱怨comb2_50_30必须用常量表达式初始化。

谁能帮我弄清楚我做错了什么，或者是否有办法让它与 constexpr 一起工作（如果没有，为什么不呢）？

Answer 1

complains that comb2_50_30 must be initialized by a constant expression.

错误的下一行告诉你原因：

note: constexpr evaluation hit maximum step limit; possible infinite loop?

您的扩展对于 constexpr 评估来说计算量太大了。您可以使用 -fconstexpr-steps=X 和 -fconstexpr-depth=X 来增加允许编译器计算 constexpr 函数的工作量，但我没能找到允许您的 recursiveCombinations(50, 30) 在 clang 上编译。

g++ 编译 constexpr 版本就好了。

Answer 2

以将结果的限制减少一个因子 min(r, n-r) 为代价，您可以使用以下更有效的实现：

constexpr uint64_t efficientCombinations(uint64_t n, uint64_t r)
{
    uint64_t accum = 1U;
    if (n - r > r) r = n - r;
    for( uint64_t x = 1; x <= n - r; ++x )
    {
        accum *= (r + x);
        accum /= x;
    }
    return accum;
}

为了与 C++11 兼容，将此迭代转换为递归很简单，即使有点混乱。

（注意：根据 "get this to work" 的问题的含义，像这样更改算法可能不是理想的方法...但它太大了，无法发表评论）

C++：尝试通过组合和帕斯卡三角来理解 constexpr

C++: Trying to understand constexpr through combinations and Pascal's Triangle

c++

templates

combinations

constexpr

c++14