C++模板元编程的归纳法是什么？

Question

当谈到模板元程序时，人们总是说使用归纳法解决问题。例如看到这个答案：

我知道归纳证明等，但是这个理论如何用于解决元程序？。我喜欢有例子的例子:)

Answer 1

正如在 OP 下的一条评论中所观察到的，TMP 技术本质上是递归的，我想这可以看作是一种“逆向归纳法”（最初是费马的想法）。这个想法是，对于一些 N，你根据一些较小的 N 定义你想要的相应的东西，最终在一些基本情况下终止。

考虑以下阶乘 TMP 代码：

template <int N>
struct Factorial {
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> {
    enum { value = 1 };
};

void foo() {
    std::cout << Factorial<0>::value << "," << Factorial<3>::value; 
    // outputs 1, 6
}

因此，一般情况 (N) 由模板给出，其值根据（可能更专业的）模板的较小值定义，终止于某个下限。

Answer 2

归纳证明通常具有以下结构：

表明对于某个值 Y
证明如果 X 对于 Y 为真，那么它对于其他一些值 Y + delta 仍然为真
因此得出结论 X 对于所有 Y + delta * N 都成立

（...在很多情况下，如果 delta 为 1 就非常方便，所以我们可以说 "X is true for all non-negative integers"，或者类似的顺序）。在相当多的情况下，在两个方向上扩展证明也很方便，因此我们可以说 X 对于所有整数都成立（举一个明显的例子）。

大多数纯递归解决方案（无论是模板元编程还是其他）倾向于遵循大致相同的结构。特别是，我们从处理一些简单的案例开始，然后根据基本案例的应用加上一些扩展步骤来定义更复杂的案例。

暂时忽略模板元编程，这可能在树的前序、中序和后序遍历的递归算法中最容易看到。对于这些，我们定义了一个基本案例来处理树的单个节点中的数据。这通常与树遍历本身无关，所以我们通常将其视为名为 process 或类似名称的函数。有了这个，我们就可以定义树遍历了：

void in_order(Tree *t) { 
    if (nullptr == t)
        return;
    in_order(t->left);
    process(t);
    in_order(t->right);
}

// preorder and postorder are same except for the order of `process` vs. recursion.

许多人认为这是独一无二的（或至少不寻常地适用于）模板元编程的原因是，这是一个 C++ 实际上只允许纯递归解决方案的领域——与普通的 C++ 不同，你没有循环或变量。类似的其他语言已经出现了很长一段时间，但其中大部分还没有真正成为主流。有相当多的语言倾向于遵循这种风格，尽管它们并不是真正需要它——但是虽然其中一些已经接近主流，但大多数仍然处于边缘。

Answer 3

"Induction" 只是从不同的角度来看递归。在每一种情况下，您都需要一个或多个基本案例，在这些案例中，可以在不递归的情况下解决问题，并且您需要一个递归案例，在递归案例中，可以通过使用更接近基本案例的相关问题的解决方案来解决问题。

在运行-时间递归编程中，基本情况可以通过运行-时间条件来检测。在递归元编程中，即使是编译时条件也不足以处理基本情况。您需要使用重载或专门化来涵盖基本情况的单独定义。

我自己第一次用的时候比较乱，不能全文引用，但大概的思路可能有借鉴意义。编译器在展开短循环之前进行了各种优化，并在展开短循环之后进行了各种其他优化。但我确实需要在之后完成其中一项 "before" 优化。所以我需要强制编译器在编译早期解除一些短循环，大致是：

template<unsigned N>
struct unwind {
   void operator()(X*p) { unwind<N-1>()(p); work(p[N]); } };
template<>
struct unwind<0> {
   void operator()(X*p) { work(p[0]); } };

当您使用编译时递归而不是运行时间循环时，编译器将在进行任何优化之前展开整个循环，因此在循环展开之前完成的类型优化会展开我的 work 代码在循环展开完成后才可见。

C++模板元编程的归纳法是什么？

What is induction method when it comes to C++ template metaprogramming?

c++

templates

template-meta-programming