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

Barbee

Of course any real-world computer program, including your compiler, has some finite limit of what it can do. You can solve this particular problem by replacing Sum<N>::value by N * (N + 1) / 2. – Glanti

GCC has an option, -ftemplate-depth, which varies the recursion limit. I can only assume other compilers have similar options – Alienist

I recommend you look at my answer here, where I ran into the same problem at first, but worked around it by using divide-and-conquer. – Kaceykachina

@Kaceykachina thanks, but I am not looking for solve the problem of calculate the sum, but rather find ways to enlarge the limits, now I know for gcc we can use ftemplate-depth, but don't know how to do in windows for vc++ – Barbee

My answer shows a way that makes the default limit a non-issue. – Kaceykachina

@Kaceykachina yea, I like your solution, it use compiler time divide-and-conquer, which shorten the depth from O(n) to O(lgn) – Barbee

can anyone tell how to inclrease this maximum in visual studio (2005, but i guess any version will do) – Miquelmiquela

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)

Huddleston

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 };
};

Doenitz