Template metaprogramming recursion up limits?

Question

I am writing a very simple template class using Metaprogramming to compute sum in compile time, as below:

#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<501>::value << endl;
}

The interesting thing is:

• When I print Sum<500> and below, it works fine

• When it comes to Sum<501>, the compile failed with:

  sum.cpp:9: instantiated from Sum<500>' sum.cpp:9: instantiated fromSum<501>' sum.cpp:22: instantiated from here

  sum.cpp:9: error: incomplete type Sum<1>' used in nested name specifier sum.cpp:9: error: enumerator value forvalue' not integer constant

• Sum<501> will report error of Sum<1>, Sum<502> will report error of Sum<2>, the difference is always 2, it seems to me the compiler has a limit resource of 500.

Any idea about this? and is their a way to break this limits?

Thanks.

Edit:
Thanks guys, the point is not about the algorithm, but rather the compiler limitation - I know there is an easy way to get sum:)

Edit2:

• Use gcc 4.6 +, the error message is much more helpful

  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

so yes, use ftemplate-depth is the right way. But how about in windows? the uplimits for VC9.0 is 499, and seems there is no option to set the template depth, see here

Answer 1

If you are using GCC, you can set the template recursion depth with -ftemplate-depth=X, where X is the required depth:

g++ ...... -ftemplate-depth=750

Bear in mind that this is not just some limit that you can set arbitrarily high. At some point you will run into OS and hardware limitations.

Concerning your actual sum function, there is a well known analytical solution to the Sum of the first N positive integers.

(i.e. n*(n+1)/2)

Answer 2

Annex B specifies recommended minimum limits; for recursively nested template instantiations the recommended minimum limit is 1024. Your implementation appears to have a limit of 500; this is still compliant, as the recommended minimum limits are only guidelines.

Your compiler may have a command line flag or other option to increase its recursively nested template instantiation limit.

The simplest fix is to use a nonrecursive algorithm; in your case,

template<int N>
class Sum
{
    public:
        enum {value = N * (N + 1) / 2 };
};