C++14: deduced (auto) return types from constexpr with ternary expressions

Question

I am experimenting with constexpr functions in C++14. The following code, which computes the factorial works as expected:

template <typename T>
constexpr auto fact(T a) {
    if(a==1)
        return 1;
    return a*fact(a-1);
}

int main(void) {
    static_assert(fact(3)==6,  "fact doesn't work");
}

when it is compiled as follows with clang:

> clang++ --version
clang version 3.5.0 (tags/RELEASE_350/final)
Target: x86_64-unknown-linux-gnu
Thread model: posix
> clang++ -std=c++14 constexpr.cpp

However, when I change the fact definition to use the ternary ? operator:

template <typename T>
constexpr auto fact(T a) {
    return a==1 ? 1 : a*fact(a-1);
}

I get the following compiler error:

> clang++ -std=c++14 constexpr.cpp
constexpr.cpp:12:31: fatal error: recursive template instantiation exceeded maximum depth of
      256
    return a==T(1) ? T(1) : a*fact(a-1);
        ... snip ...
constexpr.cpp:16:19: note: in instantiation of function template specialization 'fact<int>'
      requested here
    static_assert(fact(3)==6,  "fact doesn't work");

The problem is fixed if I explicitly state the return type T (instead of using auto to deduce the return type)

template <typename T>
constexpr T fact(T a) {
    return a==1 ? 1 : a*fact(a-1);
}

If I remove the template parameter, the pattern is repeated (the ternary version fails, and the if version works)

// this works just fine
constexpr auto fact(int a) {
    if(a==1)
        return 1;
    return a*fact(a-1);
}

whereas this fails

constexpr auto fact(int a) {
    return a==1 ? 1 : a*fact(a-1);
}

with the following error

> clang++ -std=c++14 constexpr.cpp
constexpr.cpp:16:25: error: function 'fact' with deduced return type cannot be used before it
      is defined
    return a==1 ? 1 : a*fact(a-1);
                        ^
constexpr.cpp:15:16: note: 'fact' declared here
constexpr auto fact(int a) {
               ^
constexpr.cpp:20:26: error: invalid operands to binary expression ('void' and 'int')
    static_assert(fact(3)==6,  "fact doesn't work");
                  ~~~~~~~^ ~
2 errors generated.

What is going on here?

Answer 1

The resulting type from evaluating a ternary expression is the common type of its second and third arguments.

By having the compiler deduce the return type, you force it to evaluate both of these arguments to the ternary expression. This means that the recursion doesn't end even when the terminating condition is reached, because when a==1, to figure out the return type of fact(0) the compiler must continue evaluating further recursive calls to fact, and endless recursion ensues.

By stating the return type, fact(0) does not need to be evaluated when a==1, and the recursion is able to terminate.

---

As for the case with the two return statements, the relevant standard clause is —

(from N4296) §7.1.6.4/9 [dcl.spec.auto]

If a function with a declared return type that contains a placeholder type has multiple return statements, the return type is deduced for each return statement. If the type deduced is not the same in each deduction, the program is ill-formed.

In your example, in the call to fact<int>(1), the return type deduced from the first return statement is int, so the return type of fact<int>(0) in the second return statement cannot be anything but int as well. This means the compiler does not need to evaluate the body of fact<int>(0) and the recursion can terminate.

Indeed, if you force evaluation of the call to fact in the second return statement as well, for instance by changing the first example so that T is a non-type template argument

template <unsigned T>
constexpr auto fact() {
    if(T==1)
        return 1;
    return T*fact<T-1>();
}

clang does fail with the error

fatal error: recursive template instantiation exceeded maximum depth of 256

Live demo