9

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?

Improve this question
2
  • the variable is not initialized yet when it is captured by copy Commented Jul 13, 2017 at 21:31
  • 2
    In the second case the warning from clang is quite telling `warning: variable 'fibonacci' is uninitialized when used within its own initialization [-Wuninitialized]. Commented Jul 13, 2017 at 21:32

4 Answers 4

Reset to default
12

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

Is it possible to return a lambda that does not need to be passed into itself at call sites?
@jcarpenter I had just edited my answer to address that :) take a look at the edited code!
This is one terrible way how to calculate Fibonnacci numbers. Yes, I know it was homework that asked for recursive lambda. But still. How about to return tuple containing last two numbers?
@jcarpenter the usual way you should be writing the type of a lambda is with auto. Remember that std::function has a lot of overhead
@Henri Actually, no. The lambda is stored directly as function object, it does not need to decay to a function pointer, which is not possible when the lambda captures for example.
|
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.

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.

Improve this answer

Comments

0 
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.

Improve this answer

4 Comments

Just curious, what is the point of the self being a forwarding reference parameter?
What I mean is, since you are not using std::forward what is the point of having the self parameter be a forwarding reference? Is there a situation where it generalizes better?
@curious I see no reason to ban rvalues, so I take by universal reference. Say, you can pass a non-identity self to a ycombinable function (say for unit testing), and that might involve a temprary. Or whatever other reason.
right of course. I thought const auto would have taken care of that but why impose a non mutable requirement on the functor. Of course.
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.