Recursive template explanation C++

Question

template<typename... ArgTypes>
int add(ArgTypes... args);

template<typename T, typename... ArgTypes>
int add(T t, ArgTypes... args)
{
    int sum = 0;
    return t + add(args...);
}
template<> int add() {
    return 0;
} 

How to add more operations like multiplication and subtraction? What does template<> int add() mean?

Could anyone explain in detail how this recursive template works?

UPD: Thank you guys regarding subtraction, yes, subtraction is not commutative so it's not really suitable for such recursive templating.

UPD2: Added a call stack as a reference for community

Answer 1

Here's my attempt at an explanation.

Firstly:

template<typename... ArgTypes>
int add(ArgTypes... args);

This is the starting point. It says "there exists a function called add that takes zero or more generic arguments". It doesn't contain an implementation, so on its own it amounts to a kind of promise to the compiler that such a function will exist.

Then we have:

template<typename T, typename... ArgTypes>
int add(T t, ArgTypes... args)
{
    int sum = 0; // This line isn't doing anything!
    return t + add(args...);
}

This says "here is a function called add that takes one or more generic arguments". It includes an implementation. Part of that implemantation recursively calls add(args...) with all arguments but the first (i.e. zero or more). We've been told this exists by the first declaration above.

If there is at least one argument in args, then this recursive call will end up calling the the exact same function again. But what happens when args contains zero arguments? We need a version (specialization) of the function to handle that case, which is the only case not handled by our second definition. That's where the third declaration comes in:

template<> int add() {
    return 0;
} 

This defines a function called add that takes zero arguemnts.

So, in summary:

1. The second declaration defines a function taking one or more arguemnts
2. The third declaration defines a function taking zero arguments
3. Together, this means we have a function taking zero or more arguments, as declared by the first declaration.

Answer 2

It is quite common recursive variadic template. The idea is that we use recursion

f(x0, x1, ..., xn) = f(f(x0, x1, ..., xn-1), xn) (1),

in your sample

add(x0, x1, ..., xn) = add(x0, x1, ..., xn-1) + xn.

Variadic templates provides simple and useful way to create such a structure.

First, define the general signature of the template (without implementation, becouse we never use general form)

template<typename... ArgTypes>
int add(ArgTypes... args);

Now specialize template fuction for case with at least one parameter. We use recursion which extract first argument and calls itself recursively with reduced by one the number of parameters.

template<typename T, typename... ArgTypes>
int add(T t, ArgTypes... args)
{
    int sum = 0;
    return t + add(args...); // recursive call without first arg
}

To stop recursion, we use template specialization for empty template parameters list (we add 0 at the last step).

template<> int add() {
    return 0;
} 

For multiplication you need just change + by *, becuse general recursive form (1) is identical in both case, and change return 0 to return 1 (multiply by 1 at the last step).

In the substraction case the general form of the recursion (1) is unusable, because a-b != b-a, ambiguity arises. Also with division and other noncommutative operations. You will have to clarify operations order.

Answer 3

Could anyone explain in detail how this recursive template does work?

I can try.

First you have

template<typename... ArgTypes>
int add(ArgTypes... args);

It's a variadic template function declaration: you declare that exist an add() function that receive a variadic (zero or more) number of argumens.

Attention: you declare but not define the function.

Second: you declare and define

template<typename T, typename... ArgTypes>
int add(T t, ArgTypes... args)
{
    int sum = 0;
    return t + add(args...);
}

a different template function add() that receive a template type argument (t) and a variadic template list of arguments (args...).

The line

int sum = 0;

is completely un-useful because declare an unused variable but the following line

return t + add(args...);

do the work returning the sum between t and the sum (add(args...)) between the following args....

So with add(args...) is recursively called int add(T t, ArgTypes... args) when args... (because it's a better match) isn't empty and int add(ArgTypes... args) when args... is a empty list.

But remember that int add(ArgTypes... args) is declared but not defined.

The last point is

template<> int add() {
    return 0;
} 

that is the definition of a full specialization (remember that you can't partial specialize a template function but you can full specialize it) of the first template function in case of empty list.

Off Topic suggestion: you don't need the first template function; you can substitute it with a simpler not-template function.

You can rewrite the code as follows

int add()
 { return 0; } 

template <typename T, typename... ArgTypes>
int add(T t, ArgTypes... args)
 { return t + add(args...); }

and as suggested by Jarod42, if you can use C++17, you can completely avoid recursion using template-folding

template <typename... ArgTypes>
int add (ArgTypes... args)
 { return (... + args); }

or maybe using auto for returning type.

How to add more operations like multiplication and subtraction?

No idea about subtraction (how is defined a variadic subtraction?) but, for multiplication you can use something similar (but the ground case must return 1, not 0)

int mult ()
 { return 1; } 

template <typename T, typename... ArgTypes>
int mult (T t, ArgTypes... args)
 { return t * mult(args...); }

or using template folding, from C++17,

template <typename... ArgTypes>
int mult (ArgTypes... args)
 { return (... * args); }

Answer 4

Recursion has a base case. So you can think of template<> int add() as the template specialization covering the base case when T is an integer. This will be called when sizeof...(args) is zero. See Demo Here.

For multiplication you can do this:

template<typename T, typename... ArgTypes>
int mult(T t, ArgTypes... args)
{
    return t * mult(args...);
}
template<> int mult() {
    return 1;
} 

I'm not sure what you intend to do for subtraction though. We can have the sum (addition) of numbers and the product (multiplication) of numbers, but there is nothing like ??? (subtraction) of numbers.