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?

the variable is not initialized yet when it is captured by copy — Sopel, Jul 13 '17 at 21:31
In the second case the warning from clang is quite telling `warning: variable 'fibonacci' is uninitialized when used within its own initialization [-Wuninitialized]. — Paul Rooney, Jul 13 '17 at 21:32

Curious · Accepted Answer · 2017-07-14T19:26:42.230

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.

edited Jul 14 '17 at 19:26

answered Jul 13 '17 at 21:32

Curious

20,870
8
61
146

Is it possible to return a lambda that does not need to be passed into itself at call sites? – jcarpenter2 Jul 13 '17 at 21:35
@jcarpenter I had just edited my answer to address that :) take a look at the edited code! – Curious Jul 13 '17 at 21:36
I'm not sure whether `auto` as return type is standard. It should probably be `decltype(auto)`. – Henri Menke Jul 13 '17 at 21:42
@HenriMenke it is, take a look at bullet (3) here http://en.cppreference.com/w/cpp/language/auto – Curious Jul 13 '17 at 21:43
How would you write the type of `fib` without using `auto`? I can't write the infinite string `std::function)>)>)>`. – jcarpenter2 Jul 13 '17 at 21:43
1

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? – Marek Vitek Jul 13 '17 at 21:46
@jcarpenter You need to deduce the type of a lambda. Why would you need to write out the infinite string? I don't think I follow – Curious Jul 13 '17 at 21:46
@Curious You can usually write the type of a lambda using `std::function`, but not a recursive one, because the type of one of the function's parameters (a substring of the function's type) must be the function's type itself. – jcarpenter2 Jul 13 '17 at 21:49
@jcarpenter You can never write out a lambda's type because it is internal to the compiler. What you are doing by assigning it to a `std::function` is you are decaying the lambda to a function pointer. – Henri Menke Jul 13 '17 at 21:50
1

@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](https://stackoverflow.com/a/9088690/5501675) – Curious Jul 13 '17 at 21:50
2

@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. – Rakete1111 Jul 14 '17 at 03:38

Angew is no longer proud of SO · Answer 2 · 2017-07-13T21:47:01.357

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.

Yakk - Adam Nevraumont · Answer 3 · 2017-07-14T01:30:58.670

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.

edited Jul 14 '17 at 01:30

answered Jul 14 '17 at 00:45

Yakk - Adam Nevraumont

262,606
27
330
524

Just curious, what is the point of the `self` being a forwarding reference parameter? – Curious Jul 14 '17 at 01:07
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 Jul 14 '17 at 01:14
@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. – Yakk - Adam Nevraumont Jul 14 '17 at 03:16
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. – Curious Jul 14 '17 at 03:19

score 0 · Answer 4 · answered Oct 15 '19 at 21:53

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.

Return recursive lambda from function in C++

4 Answers4