224

I am writing the following recursive lambda function:

#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;
}

...but it doesn't compile:

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

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 throw light on this?

gcc version 4.5.0 20091231 (experimental) (GCC)

6
  • Could this be static vs implicitly dynamic declarations? Commented Jan 14, 2010 at 22:32
  • 3
    What's the mutable keyword doing there? Commented Jul 22, 2016 at 0:45
  • Capturing of variables with non-automatic storage duration is not allowed. You should do it this way: chat.stackoverflow.com/transcript/message/39298544#39298544 Commented Sep 30, 2017 at 19:53
  • Just an FYI, in your second code snippet your lambda is too verbose, consider this change: std::function<int(int,int)> sum = [&](int a, int b) {
    – santahopar
    Commented Jul 22, 2020 at 3:08
  • If someone is able to answer whether tail-recursion optimisation works with any of the solutions, it would be welcome. Commented Dec 3, 2021 at 22:49

16 Answers 16

283

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.

3
  • 8
    I don't agree with this. The type of the lambda is well-known as soon as the function body is entered- there's no reason that it shouldn't be deduced by then.
    – Puppy
    Commented Jun 23, 2011 at 12:30
  • 25
    @DeadMG but the spec forbids referring to the auto variable in the initializer of it. the type of the auto variable is not known yet when the initializer is being processed. Commented Jun 23, 2011 at 17:33
  • 2
    @Puppy: In the case of an implicit capture, though, for efficiency only referenced variables are actually captured, so the body must be parsed.
    – kec
    Commented Dec 4, 2014 at 23:30
179

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.

Here's the full example at Godbolt.

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

5
  • 41
    this is way better than std::function for 3 reasons: it doesn't require type erasure or memory allocation, it can be constexpr and it works properly with auto (templated) parameters / return type Commented Sep 12, 2018 at 8:14
  • 3
    Presumably this solution also has the advantage of being copyable without the std::function reference going out of scope?
    – Uri Granta
    Commented Feb 11, 2019 at 11:41
  • 15
    Hm, when trying, GCC 8.1 (linux) complained: error: use of ‘[...]’ before deduction of ‘auto’ – needed to explicitly specify return type (on the other hand, didn't need mutable).
    – Aconcagua
    Commented Mar 23, 2019 at 15:40
  • 3
    @JohanLundberg It only works when there's another return in the function (so the return type can be deduced) -- in the example there's already a return 0 so the compiler can deduce that the return type is int -- in the general case specifying the return type is necessary.
    – user202729
    Commented Aug 5, 2020 at 16:33
  • 3
    For auto g=[&](auto g){ return g(g); }; g(g);, it's necessary to specify the return type.
    – user202729
    Commented Aug 5, 2020 at 16:34
82

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) -> int {
  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.


In C++23, with deducing this, you don't need a Y-combinator at all:

auto sum = [term,next](this auto const& sum, int a, int b) -> int {
  if (a>b) {
    return 0;
  }
  else {
    return term(a) + sum(next(a),b);
  }
}
15
  • 1
    The Y-combinator certainly is the way to go. But you really should add a non-const overload in case the provided function-object has a non-const call-operator. And use SFINAE and computed noexcept for both. Also, there's no need for the maker-function in C++17 anymore. Commented Aug 25, 2018 at 21:43
  • 3
    @minex Yes, auto sum copies... but it copies a reference_wrapper, which is the same thing as taking a reference. Doing it once in the implementation means none of the uses will ever accidentally copy.
    – Barry
    Commented Sep 22, 2019 at 1:00
  • 2
    I don't know why, but it looks like I have to add ->void return type information to my lambda, otherwise the compilation fails: godbolt.org/z/WWj14P
    – qbolec
    Commented Jan 2, 2021 at 8:51
  • 1
    @qbolec Compiler needs to know what it returns, and there's no return to clue it in, so sometimes you just need to provide it (even if in this case it should be "obviously" void)
    – Barry
    Commented Jan 2, 2021 at 15:41
  • 1
    @Barry, what you say might be part of the story, but there must be something more to it, as adding return 42; to the function seems not enough - it still needs -> int : live
    – qbolec
    Commented Jan 3, 2021 at 16:56
31

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

3
  • 3
    This should have better performance than std::function, so +1 for the alternative. But really, at this point I wonder if using lambdas is the best option ;)
    – Antoine
    Commented Feb 27, 2014 at 9:48
  • 2
    If you have a stateless lambda you may as well just make it a full function.
    – Timmmm
    Commented Jul 25, 2018 at 10:30
  • 2
    @Timmmm But then you leak part of implementation to outside word, usually lambdas are closely coupled with parent function (even when with out captures). If this was not case then you should not use lambdas in first place and use normal functions of functors.
    – Yankes
    Commented Jul 25, 2018 at 23:14
29

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.

2
  • 4
    The only answer here that actually looks useful.
    – Peter
    Commented Feb 9, 2021 at 13:09
  • 1
    This is actually identical with passing lambda itself as parameter. How can you not read post above @JohanLundberg 's post?
    – Nick Huang
    Commented Jan 27, 2022 at 11:16
14

In C++23, explicit object parameters (P0847: Deducing this) have been added:

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

For now, its only available in Clang and EDG eccp, and partially available in MSVC:

https://godbolt.org/z/f3E3xT3fY

0
13

You can make a lambda function call itself recursively. The only thing you need to do is to is to reference it through a function wrapper so that the compiler knows it's return and argument type (you can't capture a variable -- the lambda itself -- that hasn't been defined yet).

  function<int (int)> f;

  f = [&f](int x) {
    if (x == 0) return 0;
    return x + f(x-1);
  };

  printf("%d\n", f(10));

Be very careful not to run out of the scope of the wrapper f.

1
  • 3
    But, this is identical to the accepted answer, and may have a penalty for using std function. Commented Nov 29, 2016 at 18:43
7

I ran a benchmark comparing a recursive function vs a recursive lambda function using the std::function<> capture method. With full optimizations enabled on clang version 4.1, the lambda version ran significantly slower.

#include <iostream>
#include <functional>
#include <chrono>

uint64_t sum1(int n) {
  return (n <= 1) ? 1 : n + sum1(n - 1);
}

std::function<uint64_t(int)> sum2 = [&] (int n) {
  return (n <= 1) ? 1 : n + sum2(n - 1);
};

auto const ITERATIONS = 10000;
auto const DEPTH = 100000;

template <class Func, class Input>
void benchmark(Func&& func, Input&& input) {
  auto t1 = std::chrono::high_resolution_clock::now();
  for (auto i = 0; i != ITERATIONS; ++i) {
    func(input);
  }
  auto t2 = std::chrono::high_resolution_clock::now();
  auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count();
  std::cout << "Duration: " << duration << std::endl;
}

int main() {
  benchmark(sum1, DEPTH);
  benchmark(sum2, DEPTH);
}

Produces results:

Duration: 0 // regular function
Duration: 4027 // lambda function

(Note: I also confirmed with a version that took the inputs from cin, so as to eliminate compile time evaluation)

Clang also produces a compiler warning:

main.cc:10:29: warning: variable 'sum2' is uninitialized when used within its own initialization [-Wuninitialized]

Which is expected, and safe, but should be noted.

It's great to have a solution in our toolbelts, but I think the language will need a better way to handle this case if performance is to be comparable to current methods.

Note:

As a commenter pointed out, it seems latest version of VC++ has found a way to optimize this to the point of equal performance. Maybe we don't need a better way to handle this, after all (except for syntactic sugar).

Also, as some other SO posts have outlined in recent weeks, the performance of std::function<> itself may be the cause of slowdown vs calling function directly, at least when the lambda capture is too large to fit into some library-optimized space std::function uses for small-functors (I guess kinda like the various short string optimizations?).

5
  • 4
    -1. Notice that the only reason the "lambda" version takes longer is because you bind it to an std::function, which makes the operator() call a virtual call, and that would obviously take longer. On top of that, your code, in VS2012 release mode, took about the same amount of time in both cases. Commented Feb 27, 2013 at 16:52
  • @YamMarcovic What? That is currently the only known way to write a recursive lambda (that was the point of the example). I'm very pleased to know that VS2012 has found a way to optimize this use case (though there have been more developments on this topic recently, apparently if my lambda had captured more it would not have fit within the std::function small-memory functor optimizations or whatnot).
    – mmocny
    Commented Feb 27, 2013 at 18:46
  • 2
    Acknowledged. I misunderstood your post. +1 then. Gah, can only upvote if you edit this answer. So could you emphasize it a bit more, such as in the comment? Commented Feb 27, 2013 at 19:46
  • 1
    @YamMarcovic Done. I appreciate your willingness to provide feedback and refine it when needed. +1 to you, good sir.
    – mmocny
    Commented Feb 27, 2013 at 20:40
  • 0 time usually means "entire operation was optimized away". Taking input from cin does nothing if the compiler proves that you do nothing with the reslut of your computation. Commented Mar 15, 2017 at 17:39
4

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.

1
  • That answer needs C++17 at least. Otherwise I get: error: expected constructor, destructor, or type conversion before ‘;’ token in line template <class F> recursive(F) -> recursive<F>;.
    – bselu
    Commented Feb 22, 2022 at 11:12
1

Usually when I need to write a recursive lambda, I tend to go with something like this:

const auto s = [](auto s, int i) {
   if (5 < i) return i;
   return s(s, i + 1);
};
const int i = s(s, 0);

You don't need to rely on std::function or anything, and works with C++14. But it tends to be annoying when you have to invoke the lambda.
So a logical thing to do would be (https://godbolt.org/z/TrP9MWP9T):

template <typename Selfed>
constexpr auto selfed(Selfed &&s) noexcept {
    return [s = std::forward<Selfed>(s)](auto &&... args) -> decltype(auto) {
        return s(s, std::forward<decltype(args)>(args)...);
    };
}

int main() {
    const auto factorial = selfed([](auto self, int n, int s = 1) -> int {
        return 1 == n ? s : self(self, n - 1, s * n);
    });
    static_assert(1 == factorial(1));
    static_assert(2 == factorial(2));
    static_assert(6 == factorial(3));
    static_assert(24 == factorial(4));
    return 0;
}
0

This is a slightly simpler implementation of the fixpoint operator which makes it a little more obvious exactly what's going on.

#include <iostream>
#include <functional>

using namespace std;

template<typename T, typename... Args>
struct fixpoint
{
    typedef function<T(Args...)> effective_type;
    typedef function<T(const effective_type&, Args...)> function_type;

    function_type f_nonr;

    T operator()(Args... args) const
    {
        return f_nonr(*this, args...);
    }

    fixpoint(const function_type& p_f)
        : f_nonr(p_f)
    {
    }
};


int main()
{
    auto fib_nonr = [](const function<int(int)>& f, int n) -> int
    {
        return n < 2 ? n : f(n-1) + f(n-2);
    };

    auto fib = fixpoint<int,int>(fib_nonr);

    for (int i = 0; i < 6; ++i)
    {
        cout << fib(i) << '\n';
    }
}
1
  • I think you could improve your answer (performance wise) if you replace std::function with function pointer (of cores it will only work with normal function, and stateless lambdas). Btw fib_nonr should accept fixpoint<int,int>, if you use std::function its require crating new copy from *this.
    – Yankes
    Commented Mar 1, 2014 at 15:28
0

C++ 14: Here is a recursive anonymous stateless/no capture generic set of lambdas that outputs all numbers from 1, 20

([](auto f, auto n, auto m) {
    f(f, n, m);
})(
    [](auto f, auto n, auto m) -> void
{
    cout << typeid(n).name() << el;
    cout << n << el;
    if (n<m)
        f(f, ++n, m);
},
    1, 20);

If I understand correctly this is using the Y-combinator solution

And here is the sum(n, m) version

auto sum = [](auto n, auto m) {
    return ([](auto f, auto n, auto m) {
        int res = f(f, n, m);
        return res;
    })(
        [](auto f, auto n, auto m) -> int
        {
            if (n > m)
                return 0;
            else {
                int sum = n + f(f, n + 1, m);
                return sum;
            }
        },
        n, m); };

auto result = sum(1, 10); //result == 55
-2

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.

2
  • 3
    but it does work if declaration of sum is changed from 'auto' to std::function<int(int,int)> without changing the capture-list.
    – weima
    Commented Jan 14, 2010 at 22:38
  • 1
    Because it is no longer a lambda then, but a function which can be used in place of lambda? Commented Jan 14, 2010 at 22:45
-2

Here is the final answer for the OP. Anyway, Visual Studio 2010 does not support capturing global variables. And you do not need to capture them because global variable is accessable globally by define. The following answer uses local variable instead.

#include <functional>
#include <iostream>

template<typename T>
struct t2t
{
    typedef T t;
};

template<typename R, typename V1, typename V2>
struct fixpoint
{
    typedef std::function<R (V1, V2)> func_t;
    typedef std::function<func_t (func_t)> tfunc_t;
    typedef std::function<func_t (tfunc_t)> yfunc_t;

    class loopfunc_t {
    public:
        func_t operator()(loopfunc_t v)const {
            return func(v);
        }
        template<typename L>
        loopfunc_t(const L &l):func(l){}
        typedef V1 Parameter1_t;
        typedef V2 Parameter2_t;
    private:
        std::function<func_t (loopfunc_t)> func;
    };
    static yfunc_t fix;
};
template<typename R, typename V1, typename V2>
typename fixpoint<R, V1, V2>::yfunc_t fixpoint<R, V1, V2>::fix = [](tfunc_t f) -> func_t {
    return [f](fixpoint<R, V1, V2>::loopfunc_t x){  return f(x(x)); }
    ([f](fixpoint<R, V1, V2>::loopfunc_t x) -> fixpoint<R, V1, V2>::func_t{
        auto &ff = f;
        return [ff, x](t2t<decltype(x)>::t::Parameter1_t v1, 
            t2t<decltype(x)>::t::Parameter1_t v2){
            return ff(x(x))(v1, v2);
        }; 
    });
};

int _tmain(int argc, _TCHAR* argv[])
{
    auto term = [](int a)->int {
      return a*a;
    };

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

    auto sum = fixpoint<int, int, int>::fix(
    [term,next](std::function<int (int, int)> sum1) -> std::function<int (int, int)>{
        auto &term1 = term;
        auto &next1 = next;
        return [term1, next1, sum1](int a, int b)mutable ->int {
            if(a>b)
                return 0;
        else
            return term1(a) + sum1(next1(a),b);
        };
    });

    std::cout<<sum(1,10)<<std::endl; //385

    return 0;
}
1
  • Is it possible to make this answer compiler agnostic?
    – rayryeng
    Commented Apr 8, 2020 at 19:22
-2

This answer is inferior to Yankes' one, but still, here it goes:

using dp_type = void (*)();

using fp_type = void (*)(dp_type, unsigned, unsigned);

fp_type fp = [](dp_type dp, unsigned const a, unsigned const b) {
  ::std::cout << a << ::std::endl;
  return reinterpret_cast<fp_type>(dp)(dp, b, a + b);
};

fp(reinterpret_cast<dp_type>(fp), 0, 1);
8
  • I think you should avoid reinterpret_cast. Probably best way in your case is create some struct that replace dp_type. It should have field fp_type, can be constructed from fp_type and have operator () with arguments like fp_type. This will be close to std::function but will allow self referencing argument.
    – Yankes
    Commented Feb 27, 2014 at 15:28
  • I wanted to post a minimal example, without a struct, feel free to edit my answer and provide a more complete solution. A struct would also add an additional level of indirection. The example works and the cast is standard-compliant, I don't know what the -1 was for. Commented Feb 27, 2014 at 17:43
  • no, struct will work only as container for pointer and will be passed as value. This will be no more indirection or overhead than pointer. And about -1 I didnt know who give it to you, but I think its because reinterpret_cast should be used as a last resort.
    – Yankes
    Commented Feb 27, 2014 at 23:30
  • The cast is supposedly guaranteed to work by the c++11 standard. Using a struct, in my eyes, could defeat the the use of a lambda object. After all, the struct you propose is a functor, utilizing a lambda object. Commented Feb 28, 2014 at 8:42
  • Look at @Pseudonym solution, remove only std::function and you will have something close to that I had in mind. This probably will have similar performance to your solution.
    – Yankes
    Commented Mar 1, 2014 at 15:12
-5

You need a fixed point combinator. See this.

or look at the following code:

//As decltype(variable)::member_name is invalid currently, 
//the following template is a workaround.
//Usage: t2t<decltype(variable)>::t::member_name
template<typename T>
struct t2t
{
    typedef T t;
};

template<typename R, typename V>
struct fixpoint
{
    typedef std::function<R (V)> func_t;
    typedef std::function<func_t (func_t)> tfunc_t;
    typedef std::function<func_t (tfunc_t)> yfunc_t;

    class loopfunc_t {
    public:
        func_t operator()(loopfunc_t v)const {
            return func(v);
        }
        template<typename L>
        loopfunc_t(const L &l):func(l){}
        typedef V Parameter_t;
    private:
        std::function<func_t (loopfunc_t)> func;
    };
    static yfunc_t fix;
};
template<typename R, typename V>
typename fixpoint<R, V>::yfunc_t fixpoint<R, V>::fix = 
[](fixpoint<R, V>::tfunc_t f) -> fixpoint<R, V>::func_t {
    fixpoint<R, V>::loopfunc_t l = [f](fixpoint<R, V>::loopfunc_t x) ->
        fixpoint<R, V>::func_t{
            //f cannot be captured since it is not a local variable
            //of this scope. We need a new reference to it.
            auto &ff = f;
            //We need struct t2t because template parameter
            //V is not accessable in this level.
            return [ff, x](t2t<decltype(x)>::t::Parameter_t v){
                return ff(x(x))(v); 
            };
        }; 
        return l(l);
    };

int _tmain(int argc, _TCHAR* argv[])
{
    int v = 0;
    std::function<int (int)> fac = 
    fixpoint<int, int>::fix([](std::function<int (int)> f)
        -> std::function<int (int)>{
        return [f](int i) -> int{
            if(i==0) return 1;
            else return i * f(i-1);
        };
    });

    int i = fac(10);
    std::cout << i; //3628800
    return 0;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.