Is accumulate iterative or recursive?

In the book Fully Functional C++ with Range-v3 we briefly mentioned that the function accumulate is in principle equivalent to the left fold of functional programming, i.e. should in theory encapsulate recursion. The truth is a bit more complicated.

Traditional recursion is often not optimal and might quickly lead to a stackoverflow. To avoid this, compilers might (but are not obliged to) perform the so-called tail-call optimization, i.e. effectively generating an assembly that would have been the result of the code in the red section in the infographics below.

As we already mentioned, compilers aren't obliged to perform tail-call optimization and instead, in the name of efficiency, might resort to an iterative implementation such as the one mentioned at cppreference:

template<class InputIt, class T, class BinaryOperation>
constexpr 
T accumulate(InputIt first, InputIt last, T init, 
             BinaryOperation op)
{
    for (; first != last; ++first) {
        init = op(std::move(init), *first); 
    }
    return init;
}

From the point of view of an API user, the backend implementation doesn't matter and it's perfectly alright to use the analogy between the recursive left fold and accumulate.

Tagged: Range-v3