Recursive lambda functions in C++11

user_100405 0
Viewed 117368

I am new to C++11. I am writing the following recursive lambda function, but it doesn't compile.

sum.cpp

#include <iostream>
#include <functional>

auto term = [](int a)->int {
  return a*a;
};

auto next = [](int a)->int {
  return ++a;
};

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

int main(){
  std::cout<<sum(1,10)<<std::endl;
  return 0;
}

compilation error:

vimal@linux-718q:~/Study/09C++/c++0x/lambda> g++ -std=c++0x sum.cpp

sum.cpp: In lambda function: sum.cpp:18:36: error: ‘((<lambda(int, int)>*)this)-><lambda(int, int)>::sum’ cannot be used as a function

gcc version

gcc version 4.5.0 20091231 (experimental) (GCC)

But if I change the declaration of sum() as below, it works:

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

Could someone please throw light on this?

c++11 lambda c++
15 Answers

Here is a refined version of the Y-combinator solution based on one proposed by @Barry.

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };

To use this, one could do the following

auto fib = rec([&](auto&& fib, int i) {
// implementation detail omitted.
});

It is similar to the let rec keyword in OCaml, although not the same.

user_58730630

In C++23 deducing this (P0847) will be added:

auto f = [](this auto& self, int i) -> int
{
    return i > 0 ? self(i - 1) + i : 0;
}

For now its only available in EDG eccp and (partially) available in MSVC:

https://godbolt.org/z/f3E3xT3fY

user_19383480

You're trying to capture a variable (sum) you're in the middle of defining. That can't be good.

I don't think truely self-recursive C++0x lambdas are possible. You should be able to capture other lambdas, though.

user_2381280
Related