Returns a recursive lambda from a function in C ++

Question

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 ran this, the number 8 is output as expected. However, when I change the captured &fibonacci to fibonacci only to fibonacci to capture copies, the program actually executes segfault in the first line of main , where it runs makeFibonacci .

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

Answer 1

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

Just the likelihood that the function is working properly. You have undefined behavior. You are referencing an object that is outside the scope.

Also, why the segfault program when capturing a lambda copy?

This is due to the initialization of std::function . First lambda is initialized, then std::function initialized by lambda. This means that you are copying an instance of std::function that is not initialized, and therefore it is probably not in a state that can allow good copies. The invariants are broken inside, which probably causes a segmentation error.

---

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

 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 lambda owns all the state it needs. Then you can use it as

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

---

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

Answer 2

When you record by reference, your program has an Undefined Behavior, as the link becomes drooping. This happens as expected in your case, but it is just random.

When you switch to capture using a copy, it is segfaults because fibonacci is not yet constructed during capture, so the copy constructor called during capture tries to copy from an uninitialized object: Undefined Behavior again.

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

---

Side note: calculating Fibonacci numbers using recursion is almost impossible in any practical scenario, since the quadratic recursion tree grows extremely fast. I understand that this was just an example, but still.

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

with a bonus entry.

Answer 4

Although not as efficient as other methods, std::function can be used to return a recursive 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); }; }; 

However, this is implemented in C ++ 11 and does not require changing the base code.