Recursive lambda functions in C++11

Think about the difference between the auto version and the fully specified type version. The auto keyword infers its type from whatever it's initialized with, but what you're initializing it with needs to know what its type is (in this case, the lambda closure needs to know the types it's capturing). Something of a chicken-and-egg problem.

On the other hand, a fully specified function object's type doesn't need to "know" anything about what is being assigned to it, and so the lambda's closure can likewise be fully informed about the types its capturing.

Consider this slight modification of your code and it may make more sense:

std::function<int(int,int)> sum;
sum = [term,next,&sum](int a, int b)->int {
if(a>b)
    return 0;
else
    return term(a) + sum(next(a),b);
};

Obviously, this wouldn't work with auto. Recursive lambda functions work perfectly well (at least they do in MSVC, where I have experience with them), it's just that they aren't really compatible with type inference.

The trick is to feed in the lambda implementation to itself as a parameter, not by capture.

const auto sum = [term,next](int a, int b) {
  auto sum_impl=[term,next](int a,int b,auto& sum_ref) mutable {
    if(a>b){
      return 0;
    }
    return term(a) + sum_ref(next(a),b,sum_ref);
  };
  return sum_impl(a,b,sum_impl);
};

All problems in computer science can be solved by another level of indirection. I first found this easy trick at http://pedromelendez.com/blog/2015/07/16/recursive-lambdas-in-c14/

It does require C++14 while the question is on C++11, but perhaps interesting to most.

Going via std::function is also possible but can result in slower code. But not always. Have a look at the answers to std::function vs template

---

This is not just a peculiarity about C++, it's directly mapping to the mathematics of lambda calculus. From Wikipedia:

Lambda calculus cannot express this as directly as some other notations:
all functions are anonymous in lambda calculus, so we can't refer to a
value which is yet to be defined, inside the lambda term defining that
same value. However, recursion can still be achieved by arranging for a
lambda expression to receive itself as its argument value

With C++14, it is now quite easy to make an efficient recursive lambda without having to incur the additional overhead of std::function, in just a few lines of code:

template <class F>
struct y_combinator {
    F f; // the lambda will be stored here
    
    // a forwarding operator():
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        // we pass ourselves to f, then the arguments.
        return f(*this, std::forward<Args>(args)...);
    }
};

// helper function that deduces the type of the lambda:
template <class F>
y_combinator<std::decay_t<F>> make_y_combinator(F&& f) {
    return {std::forward<F>(f)};
}

with which your original sum attempt becomes:

auto sum = make_y_combinator([term,next](auto sum, int a, int b) {
  if (a>b) {
    return 0;
  }
  else {
    return term(a) + sum(next(a),b);
  }
});

---

In C++17, with CTAD, we can add a deduction guide:

template <class F> y_combinator(F) -> y_combinator<F>;

Which obviates the need for the helper function. We can just write y_combinator{[](auto self, ...){...}} directly.

---

In C++20, with CTAD for aggregates, the deduction guide won't be necessary.