模板元编程的递归限制

C++的模板元编程是C++比较高级的一种技术，可以通过一些模板的技巧，来实现编译期的计算，常见的例子如求个和啊，求个Fibonacci数列啊啥的。说实话，我从没在实际项目中用过这些技术，昨天和同事聊到C++，Java以及C#的模板时，突然想到这个，就试了一下，就写了个求和的：

#include <iostream>

using namespace std;

template<int N>
class Sum
{
    public:
        enum {value = N + Sum<N-1>::value };
};

template<>
class Sum<0>
{
    public:
        enum {value = 0};
};


int main()
{
    cout << Sum<100>::value << endl;
}

无非也就是个递归，就像写普通的递归函数一样，写上递归规律（模板函数）和递归结束条件（模板函数特化），但当我把传入的值换成501时（gcc4.1?），编译器就报错了，从出错信息判断貌似编译器对模板递归有限制，后来在gcc 4.6上试了一下，他的上限是1024，而且错误信息比较靠谱：

sum.cpp:9:14: error: template instantiation depth exceeds maximum of 1024 (use -ftemplate-depth= to increase the maximum) instantiating ‘class Sum<1>’ sum.cpp:9:14: recursively instantiated from ‘Sum<1024>’ sum.cpp:9:14: instantiated from ‘Sum<1025>’ sum.cpp:22:22: instantiated from here

那就用-ftemplate-depth吧，当然能增大，但是毕竟系统资源有限，你不能无节制的往上加。编译器有此限制当然有其原因：

资源 - 每一个递归都要保存状态，内存迟早爆掉
有些写的不好的模板类，可能是无限递归 - 要不设限，编译器就hang在那边了

对于Windows下VC9，其默认限制是499（到500就挂了），查看了下编译器参数，没发现有增大最大深度的。

这事也就完了，但有人提出了个用metaprogramming求解sum的好办法（当然不是用N(N+1)/2），蛮有灵感的：

#include <iostream>
using namespace std;

template<unsigned Start, unsigned End>
struct adder{
  static unsigned const Middle = (Start + End) / 2;
  static unsigned const value = adder<Start, Middle>::value + adder<Middle+1, End>::value;
};

template<unsigned End>
struct adder<End, End>{
  static unsigned const value = End;
};

int main()
{
    cout << adder<1, 1000>::value;
}

稍微懂点算法的人，看一下就知道这是用了分治法，每次递归都是两个分叉，这样就把总数度从N降到了LgN，巨大的提高啊！

其实，所谓的编译期运算，对编译器来讲，就是运行期，所以写递归算法也好，改进递归用分治也好，和写普通代码都是一样的道理。