Sum integers using template recursion going upwards possible?

Question

Using recursive templates, I would like to calculate the sum of the first n integers going from 0 to n. I.e. SumUp<10>::n would be 55. I wonder because I'm used to recursion going downwards (ie. from n to 0). Is it possible to go from 0 to n? Here's my attempt:

template<int n> struct SumUp {
    static constexpr int n = n;
};

template<> struct SumUp<0> {
    static constexpr int n = 0 + SumUp<n + 1>::n;  // <- Problem
};

The problem is, that in the second template, n is not known and therefore doesn't compile.

Answer 1

"Downwards" recursion counts upwards already.

When you do, for instance

int sum(int N)
{
    if (N == 0) return 0;
    return sum(N-1) + N
}

You actually compute sum(0) first.
Then sum(1) = sum(0) + 1
Then sum(2) = sum(1) + 2
Then sum(3) = sum(2) + 3

I wrote it as a regular function, but same holds regardless of language, be it runtime c++, templates, or visual basic.

Now if you want to reverse this and count downwards, you need to keep track of the target.

template<int N, int i = 0> struct SumUp {
    static constexpr int n = i + SumUp<N, i+1>::n;
};

template<int N> struct SumUp<N, N> {
    static constexpr int n = N;
};

static_assert(SumUp<1>::n == 1);
static_assert(SumUp<2>::n == 3);
static_assert(SumUp<3>::n == 6);
static_assert(SumUp<4>::n == 10);

• First part defines SumUp<n, i> as the sum of integers in range [i..n].
• Second part defines a stop condition when n == i.