template work as recursive function

Question

I found this code, and wondering whether I should really implement something like this in my real project or not.

And things confusing me are

It will take more compile time, but I should not bother about compile time at the cost of run time.
And what if N gets really a very big number then? Is there any file size limit in source code?

or its something good to know, not to implement?

#include <iostream>
using namespace std;

template<int N>
class Factorial {
public:
    static const int value = N * Factorial<N-1>::value;
};
template <>
class Factorial<1> {
public:
    static const int value = 1;
};

int main() {
  Factorial<5L> f;
  cout << "5! = " << f.value << endl;

    }

outPut:

5! = 120

slight modification in question, as i was playing with the code, found that

  Factorial<12> f1;  // works  
  Factorial<13> f2;  // doesn't work

error:

undefined reference to `Factorial<13>::value'

is it like, can go up-to 12 depth not further?

As I mention in point `3` of my [answer here](http://stackoverflow.com/a/21519186/1708801) in modern C++ a lot of these template meta programming problems can be better solved using constexpr functions. The article I link to have an extensive discussion of a lot of the trade offs. — Shafik Yaghmour, Nov 10 '14 at 19:19
In this case `N` can't really be a big number because you'll quickly get integer overflow. — Anton Savin, Nov 10 '14 at 19:20
Also, note that most compilers have a template depth limit (commonly 256). If you recurse too many times you will get a compile-time error. There are options that can raise this limit. (Of course, here you are going to overflow the `int` type long before you reach the limit -- 256! is 507 decimal digits -- but I just wanted you to be aware that there is such a limit on template recursion.) — cdhowie, Nov 10 '14 at 19:27

score 5 · Accepted Answer · edited May 23 '17 at 11:49

The answer to 1 is that it depends, template meta programming essentially involves a trade-off between doing the calculation at compile-time with the benefit that it does not have to be done at run-time. In general this technique can lead to hard to read and maintain code. So the answer ultimately depends on your need for faster run-time performance over slower compiler times and possibly harder to maintain code.

The article Want speed? Use constexpr meta-programming! explains how in modern C++ you can use constexpr functions many times as a replacement for template meta programming. This in general leads to code that is more readable and perhaps faster. Compare this template meta programming method to the constexpr example:

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

which is more concise, readable and will be executed at compile time for arguments that are constant expressions although as the linked answer explains the standard does not actually say it must be but in practice current implementations definitely do.

It is also worth noting that since the result will quickly overflow value that another advantage of constexpr is that undefined behavior is not a valid constant expression and at least the current implementations of gcc and clang will turn undefined behavior within a constexpr into an error for most cases. For example:

constexpr int n = factorial(13) ;

for me generates the following error:

error: constexpr variable 'n' must be initialized by a constant expression
constexpr int n = factorial(13) ;
              ^   ~~~~~~~~~~~~~
note: value 6227020800 is outside the range of representable values of type 'int'
return ( n == 0 ? 1 : n*factorial(n-1) ) ;
                       ^

This is also why you example:

Factorial<13> f2;

fails because a constant expression is required and gcc 4.9 gives a useful error:

error: overflow in constant expression [-fpermissive]
 static const int value = N * Factorial<N-1>::value;
                  ^

although older versions of gcc give you the less than helpful error you are seeing.

For question 2, compilers have a template recursion limit, which can usually be configured but eventually you will run out of system resources. For example the flag for gcc would be -ftemplate-depth=n:

Set the maximum instantiation depth for template classes to n. A limit on the template instantiation depth is needed to detect endless recursions during template class instantiation. ANSI/ISO C++ conforming programs must not rely on a maximum depth greater than 17 (changed to 1024 in C++11). The default value is 900, as the compiler can run out of stack space before hitting 1024 in some situations.

As in your specific problem you will need to worry about signed integer overflow, which is undefined behavior before you have system resource issues.

template work as recursive function

1 Answers1

Linked