There are a number of ways to write recursive function definitions in C++ using the template mechanism. Here we are talking about definitions that cause the compiler to create a series of recursive functions by instantiating a recursive template function. This is different than runtime recursion that we can use when writing ordinary recursive functions.
RunTmeRecursion.cpp
#include <iostream>
#include <iomanip>
using namespace std;
long factorial(int n) {
if (n == 0) { // base case, stops the recursion
return 1;
} else {
return n * factorial(n - 1);
}
}
long fibonacci(int n) {
if (n == 0) { // base case, stops the recursion
return 0;
} else if (n == 1) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
string reverse(string str) {
if (str.length() == 0) { // base case, stops the recursion
return str;
} else {
return reverse(str.substr(1)) + str[0];
}
}
int main() {
cout << "Factorial of 5: " << factorial(5) << endl;
cout << "Fibonacci of 10: " << fibonacci(10) << endl;
cout << "Reverse of 'Hello': " << reverse("Hello") << endl;
return 0;
}
These three functions all use runtime recursion. Runtime recursion uses stack space each time the function is called. If we recurse too much, we can run out of stack space and the program will crash. In many cases recursion can be more efficiently written using loops. In the case of recursive data structures like trees, recursive functions are typically warranted.
Compile-Time Recursion
C++98 introduced templates which gave us another way to write recursive functions, ones that are computed at compile-time. The following example uses a recursive structure definition to compute a function at compile time. It is not a function in the traditional sense, but it does use the compiler's ability to compute compile-time expressions to create static constant values.
CompileTimeRecursion.cpp
#include <iostream>
#include <iomanip>
using namespace std;
template<int N>
struct Factorial {
static const int value = N * Factorial<N - 1>::value;
};
// Base case, stops the recursion
template<>
struct Factorial<0> {
static const int value = 1;
};
int main() {
int result = Factorial<5>::value; // Computes factorial of 5 at compile time
cout << "Factorial of 5: " << result << endl;
result = Factorial<10>::value; // Computes factorial of 10 at compile time
cout << "Factorial of 10: " << result << endl;
return 0;
}
We can create a family of recursive functions using non-type template parameters (NTTP) on a template function. Like all recursive definitions, we need a base case that will stop the recursion. For our template function, we create a specialization of the template that will stop the recursion.
#include <iostream>
#include <iomanip>
using namespace std;
template<int N>
void printSequence() {
cout << N << " ";
printSequence<N - 1>();
}
// Specialization for N = 0 to stop the recursion
template<>
void printSequence<0>() {
cout << endl;
}
int main(int argc, char* argv[]) {
printSequence<10>();
// printSequence<2000>(); // This won't work. Exceeds the recursion limit.
// printSequence<-1>(); // This won't work. Never hits base case.
return 0;
}
Because the compiler has limits on how deep this type of recursion can go, it is not the best approach for listing a sequence. Instead a loop would be better from a compile-time perspective and a run-time perspective as well. But this trivial example illustrates the basic structure of a recursive template function. In addition to the recursive template function, you have to have a base case that is a specialization of the template function that will eventually stop the recursion. Even with this base case, we can run into problems if a negative number is used to instantiate the template.
Variadic Template Function Recursion
Recursive template functions are a better choice when we have a recursive class definition or when we need to process variadic argument lists. The following example illustrates the recursive template function simpleFormat() with variadic parameters called parameter packs called. This template function implements a simple formatting function that takes a format string followed by zero of more additional values to be formatted. The format string should contain the placeholder {} for each value to be formatted.
SimpleFormat.cpp
#include <iostream>
#include <iomanip>
#include <string>
#include <type_traits>
using namespace std;
std::string replace(std::string str, const std::string& from, const std::string& to) {
if (from.empty()) {
return str; // Avoid infinite loop when 'from' is empty
}
size_t start_pos = 0;
if ((start_pos = str.find(from, start_pos)) != std::string::npos) {
str.replace(start_pos, from.length(), to);
start_pos += to.length(); // Move past the replacement
}
return str;
}
std::string simpleFormat(std::string format)
{
return format;
}
template<typename T>
concept Intrinsic = std::is_fundamental_v<T>;
template<Intrinsic T, typename... Args>
std::string simpleFormat(std::string format, T value, Args... args)
{
std::string result = replace(format, "{}", std::to_string(value));
return simpleFormat(result, args...);
}
template<typename... Args>
std::string simpleFormat(std::string format, std::string_view value, Args... args)
{
std::string result = replace(format, "{}", value.data());
return simpleFormat(result, args...);
}
// Define a concept that checks if a class has a toString() method
template <typename T>
concept HasToString = requires(T t) {
{ t.toString() } -> std::convertible_to<std::string_view>;
};
template<HasToString T, typename... Args>
std::string simpleFormat(std::string format, T value, Args... args)
{
std::string result = replace(format, "{}", value.toString());
return simpleFormat(result, args...);
}
class Person {
std::string name;
public:
Person(std::string name) : name(name) {}
std::string toString() const { return name; }
};
int main(int argc, char* argv[])
{
std::cout << simpleFormat("Hello {}!", "Rich") << std::endl;
std::string name = "Fred";
std::cout << simpleFormat("Hello {}!", name) << std::endl;
std::cout << simpleFormat("Hello {} and {}!", "Rich", name) << std::endl;
long v = 0x7fffffffffffffff;
std::cout << simpleFormat("{} + {} = {}", 2, v, 1. + v) << std::endl;
Person p("Sally");
std::cout << simpleFormat("Hello {}!", p) << std::endl;
return 0;
}
As with all recursive functions we need a base case that will stop the recursion.
std::string simpleFormat(std::string format)
{
return format;
}
This base case takes a single string argument that is presumably a format string with no placeholders to replace. It simply returns the passed string argument back unchanged. The recursive case will take a format string and one or more additional arguments. We actually will have three specializations for the recursive template function, one for intrinsic values, one for string-like values and one for class objects that have a toString() method. The first one we will discuss is the one that takes an intrinsic type value as the first argument after the format string. To define this function we will need a concept that matches the C++ intrinsic types. In the definition below this concept is called Intrinsic.
template<typename T>
concept Intrinsic = std::is_fundamental_v<T>;
template<Intrinsic T, typename... Args>
std::string simpleFormat(std::string format, T value, Args... args)
{
std::string result = replace(format, "{}", std::to_string(value));
return simpleFormat(result, args...);
}
This template function specialization takes the format string as the first argument, an Intrinsic value as the first value to format and a parameter pack args to represent zero or more remaining arguments. It uses the Intrinsic value passed to replace the first occurrence of the {} placeholder forming a new format string. It then recursively calls simpleFormat() using the newly created format string and the remaining arguments in the expanded parameter pack args...
The second specialization handles the case when the value to format is a string-like value, i.e. a string or a char*. It accepts the format string, the string_view and zero or more remaining arguments. It substitutes the {} placeholder with the char* data from the string_view. It then recurses with the new format string and the remaining arguments.
template<typename... Args>
std::string simpleFormat(std::string format, std::string_view value, Args... args)
{
std::string result = replace(format, "{}", value.data());
return simpleFormat(result, args...);
}
The third specialization handles objects of classes that have a toString() method. Here we use a concept called HasToString that matches classes with toString() methods. We use the toString() method to convert the object to a string that we use to replace the first occurrence of the {} placeholder. As with the other two specializations, we recurse with the new format string and remaining arguments.
// Define a concept that checks if a class has a toString() method
template <typename T>
concept HasToString = requires(T t) {
{ t.toString() } -> std::convertible_to<std::string_view>;
};
template<HasToString T, typename... Args>
std::string simpleFormat(std::string format, T value, Args... args)
{
std::string result = replace(format, "{}", value.toString());
return simpleFormat(result, args...);
}
Variadic Template Method Recursion
The classic example that uses a recursive class definition with variadic argument lists is the Tuple class. To operate on a recursive template class we will need recursive template methods.
Tuple.cpp
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
using namespace std;
// Variadic class template definition
template<typename... Types>
class Tuple;
// Base case: when there are no types (empty tuple)
template<>
class Tuple<> {
public:
template<std::size_t N>
auto& get() {
static_assert(true, "Tuple index out of range");
}
size_t size() const {
return 0;
}
};
// Recursive case: stores the first type and inherits from the Tuple with the remaining types
template<typename First, typename... Rest>
class Tuple<First, Rest...> : private Tuple<Rest...> {
First value; // Store the first value
public:
// Constructor to initialize the values
Tuple(First firstValue, Rest... restValues)
: Tuple<Rest...>(restValues...), value(firstValue) {}
// Recursive get<N>() method
template<std::size_t N>
const auto& get() const {
if constexpr (N == 0) {
return value; // Return the first element when N is 0
} else {
return Tuple<Rest...>::template get<N - 1>(); // Recurse through the tuple
}
}
size_t size() const {
return 1 + Tuple<Rest...>::size();
}
};
int main() {
Tuple<int, double, std::string, char> myTuple(42, 3.14, "Hello", 'L');
Tuple<int, int, int> myTuple2(100, 200, 300);
std::cout << "First: " << myTuple.get<0>() << std::endl;
std::cout << "Second: " << myTuple.get<1>() << std::endl;
std::cout << "Third: " << myTuple.get<2>() << std::endl;
std::cout << "Fourth: " << myTuple.get<3>() << std::endl;
std::cout << "Tuple size: " << myTuple.size() << std::endl;
std::cout << "Tuple2 size: " << myTuple2.size() << std::endl;
return 0;
}
Notice the forward declaration of the Tuple class:
template<typename... Types> class Tuple;
This forward declaration means that you are declaring the existence of the class Tuple before providing its full definition. This lets the compiler know that a class Tuple with a variadic template parameter Types... will be defined later. We will be providing the definition of this recursive class in two parts, a base case and the recursive case.
The base case takes no parameters and is the case that will stop the recursion. The recursive case, defines the class using the first argument as a member and the remaining arguments to define the recursive Tuple base class.
// Base case: when there are no types (empty tuple)
template<>
class Tuple<> {
};
// Recursive case: stores the first type and inherits from the Tuple with the remaining types
template<typename First, typename... Rest>
class Tuple<First, Rest...> : private Tuple<Rest...> {
First value; // Store the first value
public:
// Constructor to initialize the values
Tuple(First firstValue, Rest... restValues)
: Tuple<Rest...>(restValues...), value(firstValue) {}
};
The base case Tuple<> doesn't define any part of the data structure. It is defined for the sole purpose of stopping the recursion of the template class. The recursive template class declares template parameters for the first Tuple value named First and zero or more remaining ones as a parameter pack named Rest. The First parameter is used to declare a member to store the first value of the Tuple. The Rest parameter pack is then used to define the base class as a recursion on the Tuple class with the Rest parameters. The constructor is then defined in terms of the First value and the Rest... values.
Now that we have the recursive class defined, we can begin to add recursive methods that operate on the recursive data structure. The first one we will add is a size() method that will return the size of the Tuple. In the base template class we define the base case of the size() method that simply returns zero.
size_t size() const {
return 0;
}
In the recursive template class we define the recursive version of the size() method. It simply adds one plus the size of the base class Tuple.
size_t size() const {
return 1 + Tuple<Rest...>::size();
}
Because the base class size() method is hidden by the current definition of size(), we need to use scope resolution to explicitly call the size() method of the base class Tuple<Rest...>.
We can also use template methods of the template class. In this example we will use a Non-Type Template Parameter (NTTP) to implement recursion. Here we define a get<>() template method to retrieve a specific value from the Tuple based on its position in the Tuple, 0, 1, 2, etc. The base case does nothing, and in fact should never be called because the base case class has no members. To catch this error, we use a static_assert() which will generate a compile-time error if the template method is used incorrectly.
template<std::size_t N>
auto& get() {
static_assert(true, "Tuple index out of range");
}
The recursive case of the template method uses the numeric size_t parameter that it will increase on each recursion.
template<std::size_t N>
const auto& get() const {
if constexpr (N == 0) {
return value; // Return the first element when N is 0
} else {
return Tuple<Rest...>::template get<N - 1>(); // Recurse through the tuple
}
}
Notice how we do some compile-time template math with the call to get<N-1>(). When the recursion gets down to zero, get<>() will return a value, otherwise it continues to recurse.