Calculating Factorials

Factorials can be computed at compile-time using template metaprogramming techniques.

#include <iostream>

template<unsigned int n>
struct factorial
{
    enum
    {
        value = n * factorial<n - 1>::value
    };
};

template<>
struct factorial<0>
{
    enum { value = 1 };
};

int main()
{
    std::cout << factorial<7>::value << std::endl;    // prints "5040"
}

5040

factorial is a struct, but in template metaprogramming it is treated as a template metafunction. By convention, template metafunctions are evaluated by checking a particular member, either ::type for metafunctions that result in types, or ::value for metafunctions that generate values.

In the above code, we evaluate the factorial metafunction by instantiating the template with the parameters we want to pass, and using ::value to get the result of the evaluation.

The metafunction itself relies on recursively instantiating the same metafunction with smaller values. The factorial<0> specialization represents the terminating condition. Template metaprogramming has most of the restrictions of a functional programming language, so recursion is the primary “looping” construct.

Since template metafunctions execute at compile time, their results can be used in contexts that require compile-time values. For example:

int my_array[factorial<5>::value];

Automatic arrays must have a compile-time defined size. And the result of a metafunction is a compile-time constant, so it can be used here.

Limitation: Most of the compilers won’t allow recursion depth beyond a limit. For example, g++ compiler by default limits recursion depeth to 256 levels. In case of g++, programmer can set recursion depth using -ftemplate-depth-X option.

Since C++11, the std::integral_constant template can be used for this kind of template computation:

#include <iostream>
#include <type_traits>

template<long long n>
struct factorial :
  std::integral_constant<long long, n * factorial<n - 1>::value> {};

template<>
struct factorial<0> :
  std::integral_constant<long long, 1> {};

int main()
{
    std::cout << factorial<7>::value << std::endl;
}

5040

Additionally, constexpr functions become a cleaner alternative.

#include <iostream>

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

int main()
{
  char test[factorial(3)];
  std::cout << factorial(7) << '\n';
}

5040

The body of factorial() is written as a single statement because in C++11 constexpr functions can only use a quite limited subset of the language.

Since C++14, many restrictions for constexpr functions have been dropped and they can now be written much more conveniently:

#include <iostream>

constexpr long long factorial(long long n)
{
  if (n == 0)
    return 1;
  else
    return n * factorial(n - 1);
}

int main()
{
  char test[factorial(3)];
  std::cout << factorial(7) << '\n';
}

5040

Or even:

#include <iostream>

constexpr long long factorial(int n)
{
  long long result = 1;
  for (int i = 1; i <= n; ++i) {
    result *= i;
  }
  return result;
}

int main()
{
  char test[factorial(3)];
  std::cout << factorial(7) << '\n';
}

5040

Since C++17 one can use fold expression to calculate factorial:

#include <iostream>
#include <utility>

template <class T, T N, class I = std::make_integer_sequence<T, N>>
struct factorial;

template <class T, T N, T... Is>
struct factorial<T,N,std::index_sequence<T, Is...>> {
   static constexpr T value = (static_cast<T>(1) * ... * (Is + 1));
};

int main() {
   std::cout << factorial<int, 5>::value << std::endl;
}