在C++中从函数返回递归lambda表达式

Question

请看下面的代码：

std::function<int(int)> makeFibonacci() {
    std::function<int(int)> fibonacci = [&fibonacci](int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }
        return fibonacci(n-1) + fibonacci(n-2);
    };
    return fibonacci;
};

int main() {
    std::function<int(int)> fibonacci = makeFibonacci();
    std::cout << fibonacci(6) << std::endl;
    return 0;
}

当我运行这段代码时，预期输出数字 8。但是，当我将捕获的 &fibonacci 改为只是 fibonacci 进行按值捕获时，程序实际上在运行 makeFibonacci 的第一行就崩溃了。

如果 fibonacci（第二行）是 makeFibonacci 函数的本地变量，并且因此在函数退出时超出范围，那么它如何被引用并递归使用呢？另外，为什么当我按值捕获 lambda 时，程序会崩溃？

- jcarpenter2

---

当变量被复制捕获时，它尚未初始化。 - Sopel

在第二种情况下，clang的警告非常明显：“警告：在其自身初始化中使用未初始化的变量'fibonacci' [-Wuninitialized]”。 - Paul Rooney

Answer 1

如果 fibonacci（第2行）是 makeFibonacci() 函数的本地变量，因此在函数退出时超出范围，那么它如何被引用并递归使用？这只是函数按预期工作的机会。您正在引用在函数中超出范围的对象，这是未定义的行为。

另外，为什么我通过复制来捕获 lambda 时程序会段错误？这是由于 std::function 的初始化方式。lambda 首先被初始化，然后 std::function 在之后用 lambda 初始化。这意味着您正在复制一个未初始化的 std::function 实例，因此它可能处于无法允许良好复制的状态。内部的不变量被打破了，这可能导致分段错误。

---

您可以通过使用多态 lambda 来更有效地创建递归 lambda 函数，而不需要 std::function。具体操作如下：

auto makeFibonacci() {
    auto fib = [](int n, auto& self) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }
        return self(n - 1, self) + self(n - 2, self);
    };
    return [fib](int n) {
        return fib(n, fib);
    };
};

这里的lambda函数拥有它所需的所有状态。然后你可以像这样使用它

auto fibonacci = makeFibonacci();
cout << fibonacci(6) << endl;

---

需要注意的是，这种方法可能是计算斐波那契数列最糟糕的方式。

- Curious

---

@HenriMenke 是的，请看这里( http://en.cppreference.com/w/cpp/language/auto )的第三条。 - Curious

这是一种可怕的计算斐波那契数列的方法。是的，我知道这是要求使用递归lambda的作业。但是，如何返回包含最后两个数字的元组呢？ - Marek Vitek

@Curious 通常可以使用 std::function 来编写 lambda 的类型，但不能编写递归 lambda 的类型，因为函数的一个参数类型（函数类型的子字符串）必须是函数类型本身。 - jcarpenter2

@jcarpenter，你应该使用“auto”来编写lambda的类型。请记住，std::function 有很多开销。 - Curious

@Henri 实际上不需要。Lambda表达式直接存储为函数对象，不需要衰减为函数指针，当Lambda表达式捕获变量时，这是不可能的。 - Rakete1111

Answer 2

当你通过引用捕获时，你的程序会出现未定义行为，因为引用变成了悬空引用。在你的情况下它能按预期工作，但这纯粹是偶然发生的。

当你改为通过复制进行捕获时，它会崩溃，因为在捕获时，fibonacci还没有被构造，所以在捕获期间调用的复制构造函数试图从未初始化的对象中复制：再次出现了未定义行为。

我认为没有办法从一个函数中返回一个递归lambda（这样它不需要额外的参数）。答案由@Curious提供展示了如何使用C++14或更新版本返回递归lambda。在C++1中，如果你真的需要一个递归函数对象，你可以为其编写一个专门的类。

---

附注：使用递归计算斐波那契数列在任何实际情况下几乎是不可能的，因为二次递归树增长得非常快。我理解这可能只是一个例子，但仍然如此。

- Angew is no longer proud of SO

Answer 3

auto y_combinator=[](auto&&f){
  return [f=decltype(f)(f)](auto&&...args)->decltype(auto){
    return f(f,decltype(args)(args)...);
  };
};

std::function<int(int)> makeFibonacci() {
    auto fibonacci = [memo=std::map<int,int>{}](auto&& self, int n)mutable {
      if (n<3)
        return 1;
     auto it = memo.find(n);
     if (it != memo.end()) return *it;
     return memo[n]=(self(self,n-1)+self(self,n-2));
   };
  return y_combinator(fibonacci);
}

带有奖励记忆化的。

- Yakk - Adam Nevraumont

---

只是好奇，self 作为转发引用参数的目的是什么？ - Curious

我的意思是，既然你没有使用std::forward，那么将self参数设置为转发引用有什么意义呢？是否存在一种情况使其更加通用？ - Curious

@curious 我看不出禁止 rvalue 的理由，所以我采用通用引用方式。比如说，你可以将非标识 self 传递给 ycombinable 函数（例如用于单元测试），这可能涉及到临时变量。或者其他任何原因。 - Yakk - Adam Nevraumont

当然。我以为const auto会处理这个问题，但为什么要对函数对象施加不可变要求呢？当然。 - Curious

Answer 4

虽然不如其他方法高效，但std::function可用于返回递归lambda：

std::function<int(int)> makeFibonacci() {
    std::function<int(int)> fibonacci;
    return [fibonacci](int n) mutable {
        fibonacci = [&](int n) {
            if (n == 1) {
                return 1;
            }
            if (n == 2) {
                return 1;
            }
            return fibonacci(n-1) + fibonacci(n-2);
        };
        return fibonacci(n);
    };
};

然而，它可在C++11中实现，且不需要更改底层代码。

- rahnema1