Return recursive lambda from 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 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.

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?

Answer 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?

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?

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.

---

You can make a recursive lambda function more efficiently without std::function by 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 the lambda owns all the state it needs. You can then use it like this

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

---

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