从c++函数返回递归的lambda函数

See the following code:

看下面的代码:

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

When I run this, the number 8 is output as expected. However when I change the captured &fibonacci to just fibonacci for a by-copy capture, the program actually segfaults on the first line of main where it runs makeFibonacci.

当我运行这个时，数字8是预期的输出。然而，当我将捕获的&fibonacci更改为一个副拷贝捕获时，程序实际上是在它运行makeFibonacci的main的第一行上分段错误。

If fibonacci (line 2) is a local of the makeFibonacci function, and therefore goes out of scope when the function exits, how can it be captured by reference and used recursively? Also, why does the program segfault when I capture the lambda by copy?

如果fibonacci(第2行)是makeFibonacci函数的局部，因此在函数退出时超出了范围，那么如何通过引用捕获它并递归地使用它呢?另外，为什么当我复制捕获lambda时，程序segfault ?

3 个解决方案

#1

If fibonacci (line 2) is a local of the makeFibonacci() function, and therefore goes out of scope when the function exits, how can it be captured by reference and used recursively?

如果fibonacci(第2行)是makeFibonacci()函数的局部，因此在函数退出时超出了范围，那么如何通过引用捕获它并递归地使用它呢?

It's just chance that the function is working as expected. What you have is undefined behavior. You are referencing an object that goes out of scope in the function.

只是碰巧函数像预期的那样工作。你拥有的是未定义的行为。您正在引用一个超出函数范围的对象。

Also, why does the program segfault when I capture the lambda by copy?

另外，为什么当我复制捕获lambda时，程序segfault ?

This happens because of how the std::function is initialized. The lambda is initialized first, the std::function is initialized with the lambda afterwards. Which means that you are copying an instance of std::function that is not initialized, and therefore it is probably not in a state which can allow good copies. Invariants are broken inside, which are likely causing the segmentation fault.

这是因为std::函数初始化。先初始化lambda，然后用lambda初始化std::函数。这意味着您正在复制一个std:::函数的实例，该函数没有初始化，因此它可能处于允许良好拷贝的状态。不变量内部被破坏，这很可能导致分割错误。

You can make a recursive lambda function more efficiently without std::function by using a polymorphic lambda as follows

通过使用如下所示的多态lambda，您可以更有效地创建递归lambda函数，而无需std:::函数

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

Here the lambda owns all the state it needs. You can then use it like this

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

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

Also note that this is probably the worst way to calculate fibonacci numbers.

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

#2

When you capture by reference, your program has Undefined Behaviour, as the reference becomes dangling. It happens to work as expected in your case, but that's purely by accident.

当您通过引用捕获时，您的程序具有未定义的行为，因为引用变成悬浮的。在你的例子中，它碰巧像预期的那样工作，但那纯粹是偶然的。

When you change to capture by copy, it segfaults because at the time of capture, fibonacci is not yet constructed, so the copy constructor called during the capture is attempting to copy from an uninitialised object: Undefined Behaviour again.

当您更改为按copy捕获时，它会分段错误，因为在捕获时，还没有构造fibonacci，因此捕获期间调用的复制构造函数正在尝试从未初始化的对象中复制:未定义行为。

~~I don't think there is a way to return a recursive lambda from a function (such that it would not require additional parameters).~~ The answer by @Curious shows how you can return a recursive lambda, using C++14 or newer. In C++1, if you really need a recursive functor, you can write a dedicated class for it.

我认为没有一种方法可以从函数中返回递归的lambda(这样就不需要额外的参数)。@好奇的答案显示了如何使用c++ 14或更新来返回递归lambda。在c++ 1中，如果您真的需要一个递归函数，您可以为它编写一个专门的类。

Side note: computing Fibonacci numbers using recursion is pretty much impossible in any practical scenario, since the quadratic recursion tree grows extremely quickly. I understand this was probably just an example, but still.

附注:使用递归计算斐波那契数在任何实际场景中都几乎是不可能的，因为二次递归树增长得非常快。我知道这可能只是一个例子，但仍然。

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

with bonus memoization.

与奖金记忆。

#1