Recursive templates
- C++ course
- Expert
- Lesson 2/47
- 5 min
Learn compile-time loops with recursive templates.
Recursive templates
A recursive template is a compile-time loop where a template refers to itself. Factorial is written this way: the general case Factorial<N>::value = N * Factorial<N-1>::value, and the base case Factorial<0>::value = 1 is given as a specialization.
Example: template <int N> struct Factorial { static const int value = N * Factorial<N-1>::value; }; and template <> struct Factorial<0> { static const int value = 1; };. The compiler unfolds 3 * 2 * 1 * 1 for Factorial<3> at compile time.
Stopping with specialization
For recursion to stop, a specialization is needed. template <> struct Factorial<0> is a full specialization with an empty parameter list. When the compiler reaches Factorial<0> it takes value = 1 without using the general template.
So the chain for Factorial<3>::value ends as 3 * Factorial<2> → 2 * Factorial<1> → 1 * Factorial<0> → 1. The result is 6 and is used as a constant at run time.
Practice Write the recursive Factorial
Write the general template <int N> struct Factorial with body static const int value = N * Factorial<N-1>::value;. Then add the template <> struct Factorial<0> specialization with value = 1. In main write std::cout << Factorial<5>::value;.
Starter code
#include <iostream>
// Define the Factorial template here
int main() {
// Print the result
return 0;
}Sample solution
#include <iostream>
template <int N>
struct Factorial {
static const int value = N * Factorial<N-1>::value;
};
template <>
struct Factorial<0> {
static const int value = 1;
};
int main() {
std::cout << Factorial<5>::value;
return 0;
}Expected output
120
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Complete the base case
template <> struct Factorial<0> { static const int value = ____; };template <> struct Factorial<0> { static const int value = 1; };Explanation: Write value = 1; factorial of 0 is 1.
2 What is Factorial<3>::value?
template <int N> struct Factorial { static const int value = N * Factorial<N-1>::value; };- 3
- 9
- 6 Correct answer
- 0
Explanation: The right answer is: 6. 3! = 3 * 2 * 1 = 6.
3 Match each call to its result
| Term | Meaning |
|---|---|
Factorial<1>::value |
returns 1 |
Factorial<3>::value |
returns 6 |
Factorial<4>::value |
returns 24 |
Factorial<5>::value |
returns 120 |