如何使用模板在编译时找到两个数字的HCF？

Question

我想使用使用模板递归的枚举值来计算两个数字的HCF：

#include <stdio.h>
template<int x,int y,int r>
struct s{
    enum{e=x%r==0 && y%r==0?r:s<x,y,r-1>::e};
};

int main(){
    printf("%d\n",s<3,5,MIN(3,5)>::e);
    return 0;
};

哪个x和y是两个数字，r是要测试的值，原则是找一个数字除以x和y，从x和y的最小值开始，然后减少1，直到r的值可以同时除以x和y。但是由于以下错误，这段代码无法编译：

xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, -252>'     requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, -251>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, -250>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, -249>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, -248>' requested here
xxx.cpp:4:31: note: (skipping 246 contexts in backtrace; use -ftemplate-backtrace-limit=0 to see all)
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, -1>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, 0>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, 1>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, 2>' requested here
xxx.cpp:8:19: note: in instantiation of template class 's<3, 5, 3>' requested here
printf("%d\n",s<3,5,3>::e);
              ^
xxx.cpp:4:31: note: use -ftemplate-depth=N to increase recursive template instantiation depth
enum{e=x%r==0 && y%r==0?r:s<x,y,r-1>::e};
                          ^
1 error generated.

有什么问题吗？

Answer 1

@月光的评论是核心的答案，但让我把它扩展到一个完整的答案。

编译器的输出幸运地显示了相关的实例化：

xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, -1>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, 0>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, 1>' requested here

让我们来看看实际的实例化

template<int x = 3, int y = 5, int r = 0>
struct s{
    enum{e = 3%0==0 && 5%0==0 ? 0 : s<5,3,-1>::e};
};

显然，有两件事是错误的：

1. 3 % 0是除以零
2. s<5,3,-1>的实例化是不必要的。

这在constexpr中很容易修复，但是让我们继续使用模板化的解决方案。递归在结尾需要一个特例，而HCF(x,y)=1是同素的特例.

template <int x, int y> 
struct s<x,y,1> { enum e = 1 };

尽管如此，你真的应该使用欧几里得算法，因为这种蛮力搜索不会对像s<300,300,300>这样简单的东西起作用。