Recursive Struct in C++

Question

I found the following code and it seems working but I can not understand it at all.
It looks like a Recursive Struct but I never saw this before.

template<int B, int N>
struct Pow {
    enum{ value = B*Pow<B, N-1>::value };
};

template< int B >
struct Pow<B, 0> {
    enum{ value = 1 };
};
int quartic_of_three = Pow<3, 4>::value;

any idea what is this?

It uses compile-time recursion to compute B to the power of N. — Andrei Tita, Jan 04 '13 at 03:17
Very basic template metaprogramming - http://en.wikipedia.org/wiki/Template_metaprogramming — Yuushi, Jan 04 '13 at 03:18

score 3 · Accepted Answer · edited May 23 '17 at 12:18

3

it's a way to compute an integral power at compile time, relying on the compiler supporting the requisite number of template specializations (i.e., it's not exactly portable code)

read up on templates in your favorite c++ text book

if you don't have a c++ text book yet: you need it, take a look in the SO FAQ C++ book list

a much better and (in a few years) probably much more portable way in C++11 is to use a constexpr function:

#include <iostream>
using namespace std;

constexpr int constpow( int base, int n )
{
    return (n == 0? 1 : base*constpow( base, n - 1 ));
}

int main()
{
    int const quarticOfThree = constpow( 3, 4 );
    wcout << quarticOfThree << endl;
}

however, that's not supported by visual c++ 11.0, the latest version of visual c++ as i write this

edited May 23 '17 at 12:18

Community

1
1

answered Jan 04 '13 at 03:17

Cheers and hth. - Alf

142,714
15
209
331

What do you mean by "it's not exactly portable code"? I believe it's fully standard-compliant. – Andrei Tita Jan 04 '13 at 03:18
@AndreiTita: you quote a conclusion (that's the meaning of "i.e.") of a sentence with a premise. the other premise is that different compilers have different limits. so, it's standard-compliant non-portable code. – Cheers and hth. - Alf Jan 04 '13 at 03:24
Template recursion depth can be unreasonably short by the standard @andreitita – Yakk - Adam Nevraumont Jan 04 '13 at 03:25
1

`constexpr` is much less portable than templates are at this point. – Pubby Jan 04 '13 at 03:26
@Yakk C++03 recommends at least 17 but C++11 increases it to 1024, while only recommending to allow at least 512 nested `constexpr` evaluations. It's sort of academic; the only real rule is to give your compiler a metaprogram that completes in a reasonable amount of time. Compilers have these limits to cause a message to be printed, so the user doesn't wait all day for a result or get a segfault. As for compliance, the Standard just isn't making an effort to legislate metaprogam complexity. – Potatoswatter Jan 04 '13 at 03:51

didierc · Answer 2 · 2013-01-04T09:51:29.493

The important things to note in this template definition are:

the template parameters are values, and not types as many people usually expect in templates;
the field value of the struct template is computed from these parameters;
the template has a partial specialization for the second parameter N when set with 0.

As you noticed, the template recurse on the value field computation. that recursion would be infinite, if the partial specialization were not defined. When the second parameter "reaches" 0, ie. when, by following the nesting of template instantiation in the attempt of getting the successive value fields necessary to compute the outermost one, the compiler finally needs to instantiate the template with parameter N equal to 0, and selects the partial specialization version, which contains a constant value of 1 for the field. Then the compiler can compute each nested value field, to finally return to the outermost one.

Using this technique, it is possible to have the compiler compute certain values offline (ie. at compile time). This let the programmer have his constant values defined by their parameters and formula, rather than having to hardcode them, or make the compiled program compute them at each run.

But the issue with this approach, how clever it may seem, is its readability and thus ease of maintenance. That's most probably the reason why the new standard offers the constexpr concept, which is a much proper way to define so called pure computation.

It should be noted that both fields of the templates are signed, and that the computation does not try to handle the negative values in any way. If N is initially set at -1, the result could be interesting.

Recursive Struct in C++

2 Answers2