c++ 11中的递归lambda函数

我是c++ 11的新手。我正在写下面的递归lambda函数，但它不能编译。

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

编译错误:

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

sum.cpp:在lambda函数中 sum.cpp:18:36:错误:' ((<lambda(int, int)>*)this)-><lambda(int, int)>::sum '不能用作函数

gcc版本

gcc版本4.5.0 20091231(实验性)(gcc)

但如果我改变sum()的声明如下所示，它可以工作:

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

有人能解释一下吗?

当前回答

您正在尝试捕获正在定义的变量(sum)。那可不太好。

我不认为真正的自递归c++ 0x是可能的。不过，您应该能够捕获其他lambda。

2010-01-14 22:32:08

其他回答

这是一个稍微简单的固定点操作符的实现，这使得它更明显地发生了什么。

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

2013-01-29 01:22:22

您正在尝试捕获正在定义的变量(sum)。那可不太好。

我不认为真正的自递归c++ 0x是可能的。不过，您应该能够捕获其他lambda。

2010-01-14 22:32:08

诀窍是将lambda实现作为参数提供给自身，而不是通过捕获。

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

计算机科学中的所有问题都可以通过另一种间接方式来解决。我第一次发现这个简单的技巧是在http://pedromelendez.com/blog/2015/07/16/recursive-lambdas-in-c14/

它确实需要c++ 14，而问题是c++ 11，但对大多数人来说可能很有趣。

这是戈德波特大学的完整例子。

使用std::function也是可能的，但会导致代码变慢。但并非总是如此。看看std::function vs template的答案

这不仅仅是c++的特性，它直接映射到微积分的数学中。从维基百科:

Lambda微积分不能像其他表达式那样直接表示这个符号: 所有的函数在微积分中都是匿名的，所以我们不能引用a 还没有定义的值，在定义它的lambda项中相同的值。但是，递归仍然可以通过排列 Lambda表达式接收自身作为参数值

2016-11-29 18:47:59

我有另一个解决方案，但只与无状态lambdas工作:

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

这里的技巧是lambdas可以访问静态变量，并且可以将无状态变量转换为函数指针。

你可以在标准的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);
    };
}

它在GCC 4.7中的工作

2012-12-30 18:45:26

要使lambda递归而不使用外部类和函数(如std::function或定点组合子)，可以在c++ 14中使用以下结构(现场示例):

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

打印:

注意，lambda的结果类型应该显式指定。

2017-08-22 18:41:55

c++ 11中的递归lambda函数

推荐文章

最新文章

标签