Why can’t we have automatically deduced return types?

Well – time passed since the original question was asked and the answer now is that you can!

_{Yes, it is true that the question is tagged C++11 – with which you still cannot do what the OP is asking for. But it’s worthwhile to show what is doable with C++14 and later.}

Since C++14 this is valid:

template<class A, class B>
auto sum(A a, B b) {
    return a + b;
}

And since C++20 this is also valid:

auto sum(auto a, auto b) {
    return a + b;
}

The following is the C++11 answer, kept here for historical reasons, with some comments from the future (C++14 and later):

What if we have the following:

template<class A, class B, class C>
auto sum(A a, B b, C c) {
   if (rand () == 0) return a + b;

   // do something else...

    return a + c;
}

.. where a + b and a + c expressions yield different type of results.
What should compiler decide to put as a return type for that function and why?
This case is already covered by C++11 lambdas which allow to omit the return type as long as return statements can be deduced to the same type (NB standard quote needed, some sources claim only one return expression is allowed and that this is a gcc glitch).

_{A note from the future (C++14 and on): the example above is still not valid, you may only have a single possible return type. However if there are different return types but the actual return type can be deduced at compile type, then we have two different functions, which is valid. The following for example is valid since C++17:}

template<class A, class B, class C>
auto sum(A a, B b, C c) {
    if constexpr(std::is_same_v<A, B>) return a + b;
    else return a + c;
}

int main() {
    auto a1 = sum(1, 2l, 3.5); // 4.5
    auto a2 = sum(1, 2, 3.5); // 3
}

_{Back to the original C++11 answer, explaining why the requested syntax is not supported:}

A technical reason is that C++ allows the definition and declaration to be separate.

template<class A, class B>
auto sum(A a, B b) -> decltype(a + b);

template<class A, class B>
auto sum(A a, B b) -> decltype(a + b)
{
}

The definition of the template could be in the header. Or it could be in another file, so that you don’t have to wade through pages and pages of function definitions when looking through an interface.

C++ has to account for all possibilities. Restricting trailing return types to just function definitions means that you can’t do something as simple as this:

template<class A, class B>
class Foo
{
  auto sum(A a, B b) -> decltype(a + b);
}

template<class A, class B>
auto Foo<A, B>::sum(A a, B b) -> decltype(a + b)
{
}

_{A note from the future (C++14 and on): you still cannot have a declaration with auto return type, if the definition is not available when the compiler sees the call.}