Recursive lambda functions in C++11

Question

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.

I have another solution, but work only with stateless lambdas:

void f()
{
    static int (*self)(int) = [](int i)->int { return i>0 ? self(i-1)*i : 1; };
    std::cout<<self(10);
}

Trick here is that lambdas can access static variables and you can convert stateless ones to function pointer.

You can use it with standard lambdas:

void g()
{
    int sum;
    auto rec = [&sum](int i) -> int
    {
        static int (*inner)(int&, int) = [](int& _sum, int i)->int 
        {
            _sum += i;
            return i>0 ? inner(_sum, i-1)*i : 1; 
        };
        return inner(sum, i);
    };
}

Its work in GCC 4.7

To make lambda recursive without using external classes and functions (like std::function or fixed-point combinator) one can use the following construction in C++14 (live example):

#include <utility>
#include <list>
#include <memory>
#include <iostream>

int main()
{
    struct tree
    {
        int payload;
        std::list< tree > children = {}; // std::list of incomplete type is allowed
    };
    std::size_t indent = 0;
    // indication of result type here is essential
    const auto print = [&] (const auto & self, const tree & node) -> void
    {
        std::cout << std::string(indent, ' ') << node.payload << '\n';
        ++indent;
        for (const tree & t : node.children) {
            self(self, t);
        }
        --indent;
    };
    print(print, {1, {{2, {{8}}}, {3, {{5, {{7}}}, {6}}}, {4}}});
}

prints:

1
 2
  8
 3
  5
   7
  6
 4

Note, result type of lambda should be specified explicitly.