编译时递归是如何工作的？

Question

我在这里找到了一段代码Printing 1 to 1000 without loop or conditionals

请问有人可以解释一下编译时递归是如何工作的吗，我在谷歌上没找到相关信息

// compile time recursion
template<int N> void f1()
{ 
    f1<N-1>(); 
    cout << N << '\n'; 
}

template<> void f1<1>() 
{ 
    cout << 1 << '\n'; 
}


int main()
{
    f1<1000>();
}

谢谢！

- VextoR

---

实际上有一个技巧，专业化是一种条件语句，尽管没有 if 关键字... - Matthieu M.

这与运行时递归相比快多少有一个经验法则吗？ - David Doria

使用这种方法代替常规递归的好处是什么？ - zzzzz

Answer 1

它重复使用 f1<N> 模板，并将 N 的值递减（f1<N>() 调用 f1<N-1> 等等）。当 N==1 时的显式特化结束了递归：一旦 N 变成 1，编译器将选择专门化的函数而不是模板函数。

f1<1000>() 导致编译器实例化 f1<N> 999 次（不包括最后一次调用 f1<1>）。这就是为什么使用模板元编程技术的代码编译可能需要一些时间的原因。

整个过程严重依赖于编译器的优化能力 - 理想情况下，它应该完全消除递归（递归只是使用模板来模拟一个 for 循环的 hack）。

- Alexander Gessler

Answer 2

从概念上讲，它与运行时递归几乎相同。 f1<1000> 调用 f1<999>，然后打印出 1000。 f1<999> 调用 f1<998>，然后打印出 999，以此类推。一旦到达 1，模板特化就充当递归的基本情况来终止递归。

- Mark B

---

为什么它会从0打印到1000而不是从1000到0？ - VextoR

@VextoR：这是因为它首先调用f1<N-1>，然后打印输出。 - sharptooth

因为它在实例化下一个模板之后才向控制台输出N。 - Maxpm

@sharptooth <N-1> == 999？它应该打印“999”吗？ - VextoR

@VextoR：不，它首先调用 f1<999>()，然后打印1000。 - sharptooth

Answer 3

这并不能保证是纯的编译时递归。编译器将不得不实例化函数f1()的所有参数值，从2到1000，并相互调用。

然后，编译器可能会看到这些调用可以转换为一系列cout << ...语句。也许它会消除调用，也许不会-这取决于编译器。从C++的角度来看，这是一系列函数调用，只要不更改行为，编译器就可以做任何事情。

- sharptooth

Answer 4

很简单，每个模板实例化都会创建一个带有更改参数的新函数。例如，如果您定义了：f1_1000（），f1_999（）等。

每个函数调用名称中少1的函数。由于有不同的模板而不是递归来定义f1_1（），因此我们还有一个停止情况。

- kriss

Answer 5

你可以在这里找到阶乘计算的解释。

顺便提一下，你的函数不能处理负数。

- BЈовић