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

While it is not efficient as other methods, std::function can be used to return 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 it is implementable in C++11 and it doesn't require to change the underlying code.

Answer 2

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.

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 bonus memoization.

Answer 4

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.

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.

---

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.