带隐式类型推导的C++函数模板递归偏特化实现与优化

编译报错根源：函数模板不允许偏特化 #

C++标准仅支持对类模板、变量模板进行偏特化，函数模板只能做全特化，你最初尝试对带多个模板参数的recursive函数做偏特化，自然会触发编译报错。
你采用的将递归逻辑封装到可偏特化的类模板中、再暴露静态成员函数的方案，是解决这类问题的常规思路，本身没有问题。

编译时间膨胀根源：三目运算符强制实例化双分支 #

普通三目运算符的两个分支在编译期都会被强制实例化，哪怕其中一个分支逻辑永远不会被执行。假设N=10，就会产生2^10=1024个模板实例，N值稍大就会导致编译时间指数级增长，甚至编译失败。

if constexpr是编译期分支语句，只有满足条件的分支会被实例化，另一分支会被编译器直接丢弃，不会产生多余的模板实例，彻底解决编译时间膨胀的问题。
修改后的完整代码如下：

#include <iostream>
#include <Eigen/Dense>
using Mat = Eigen::MatrixXd;
using Vec = Eigen::VectorXd;
using Eigen::MatrixBase;

template <int N>
struct Recursive
{
template <typename D0, typename D1>
static inline Vec recursive(const MatrixBase<D0> &A,
                     const MatrixBase<D1> &b)
{
    if constexpr (N % 2 == 1) {
        return Recursive<N-1>::recursive(A, A * b);
    } else {
        return Recursive<N-1>::recursive(A, A.ldlt().solve(b));
    }
}

};

template<>
struct Recursive<0>
{
template <typename D0, typename D1>
static inline Vec recursive(const MatrixBase<D0> &A,
                     const MatrixBase<D1> &b)
{
    return b;
}
};

int main()
{
    Mat A(2, 2);
    A(0, 0) = 10.0;
    A(1, 1) = 10.0;

    Vec b(2);
    b(0) = 1.0;
    b(1) = 5.0;

    Vec res = Recursive<10>::recursive(A, b);
    std::cout << res << std::endl;
}

该代码在开启O2优化的情况下，编译器会完全消除递归开销，将逻辑直接优化为等价的循环结构，运行效率和手写循环完全一致。

如果你不想用递归实现，也可以借助std::make_index_sequence将逻辑展开为编译期循环，实现更直接，模板实例化数量和N成正比，编译速度更快：

#include <utility>
// 循环实现版本
template <int N, typename D0, typename D1>
Vec loop_impl(const MatrixBase<D0>& A, const MatrixBase<D1>& b)
{
    auto current = b.eval();
    [&]<std::size_t... I>(std::index_sequence<I...>) {
        (
            [&](){
                if constexpr ((N - I) % 2 == 1) {
                    current = A * current;
                } else {
                    current = A.ldlt().solve(current);
                }
            }(), ...
        );
    }(std::make_index_sequence<N>{});
    return current;
}

// 调用方式
// res = loop_impl<10>(A, b);

优化后的运行效率和递归版本没有区别。

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