Can lambda functions be recursive?

Question

Possible Duplicate:
Recursive lambda functions in c++0x

Here is a plain old recursive function:

int fak(int n)
{
    return (n <= 1) ? 1 : n * fak(n - 1);
}

How would I write such a recursive function as a lambda function?

[](int n) { return (n <= 1) ? 1 : n * operator()(n - 1); }
// error: operator() not defined

[](int n) { return (n <= 1) ? 1 : n * (*this)(n - 1); }
// error: this wasn't captured for this lambda function

Is there any expression that denotes the current lambda so it can call itself recursively?

possible with huge std::function overhead or with polymorphic lambdas. — ipc, Jan 25 '13 at 23:36
Oops - I accidentally deleted my comment. here's the link back: http://blogs.msdn.com/b/vcblog/archive/2008/11/18/stupid-lambda-tricks.aspx — Michael Burr, Jan 25 '13 at 23:44
@MichaelBurr, It's funny. I find the notion that you accidentally deleted your comment laughable, but I can relate to how easy it is to do something like that :p — chris, Jan 25 '13 at 23:46
I'm just gonna leave this here http://www.slideshare.net/adankevich/c11-15621074 29 slide — innochenti, Jan 29 '13 at 19:06
Why not just Y-combinator? http://rosettacode.org/wiki/Y_combinator#C.2B.2B — kerzol, Jan 30 '15 at 23:38

score 121 · Accepted Answer · edited Jun 09 '22 at 09:25

121

Yes, they can. Starting with C++23 you can use the explicit this parameter:

auto factorial = [](this auto self, int i) 
{ 
    return (i == 1) ? 1 : i * self(i - 1); 
};

With previous C++ standards, you can store the lambda in a variable and reference that variable (although you cannot declare the type of that variable as auto, you would have to use an std::function object instead). For instance:

std::function<int (int)> factorial = [&] (int i) 
{ 
    return (i == 1) ? 1 : i * factorial(i - 1); 
};

edited Jun 09 '22 at 09:25

Benjamin Buch

4,752
7
28
51

answered Jan 25 '13 at 23:38

Andy Prowl

124,023
23
387
451

2

I _think_ `factorial` needs to be captured by reference, but I'm not 100% positive. – ildjarn Jan 25 '13 at 23:43
@ildjarn you're right, otherwise you get a segfault. – Seth Carnegie Jan 25 '13 at 23:44
31

Also note that such a function cannot be returned safely. – R. Martinho Fernandes Jan 25 '13 at 23:50
4

@R.MartinhoFernandes: Good point, it would capture by reference a local object that is gone out of scope. You could still use a `shared_ptr` I guess (?), but that would be probably kind of fetish. – Andy Prowl Jan 25 '13 at 23:56
Would this work if factorial has state? Wouldn't copies of the function break? – nishantjr Dec 12 '14 at 08:43
a slightly more performant call would be a method that delegates implementation to a lambda that call again that method, It will avoid the overhead of a `std::function` – CoffeDeveloper Oct 11 '15 at 11:49
@R.MartinhoFernandes, hi can you please explain why in not unsafely? – rikimaru2013 May 12 '16 at 12:34
1

@rikimaru2013 returning it destroys the local variable, and the function has a reference to that local variable. – R. Martinho Fernandes May 12 '16 at 14:45
@R.MartinhoFernandes my bad, i see it now, thank u! – rikimaru2013 May 12 '16 at 14:52
1

@rikimaru2013 also, just for completeness, note that the equivalent code using a dedicated struct type instead of a lambda would support that by the use of `this`. – R. Martinho Fernandes May 12 '16 at 15:43
3

Hmm, why can't `auto` be used for the lambda's type? I'd expect this to be possible as long as I specify return type for the lambda body. Silly C++ :( – Lightness Races in Orbit Aug 12 '16 at 14:24
This way you lose one of the features of lambdas: anonymity. You can't pass such an object inline like e.g. `applyMyLambda([](int x){__call_self(x-1);});` – Ruslan Feb 22 '20 at 12:27
in the std::function way I had thought you couldn't do this as a one-liner. Isn't the one-liner the equivalent of doing it with `auto` and a lambda? I thought you had to define the `std::function` variable first and let it be default initialized and then *assign* a lambda to it that captures the now fully defined variable by reference. – jwezorek Apr 15 '23 at 20:31

Can lambda functions be recursive?

1 Answers1

Linked

Related