# Calculating Factorials

suggest change

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