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

Andy Prowl · Accepted Answer · 2013-01-25T23:43:54.923

116

Yes, they can. You can store it 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); 
};

Otherwise, no, you cannot refer the this pointer from inside the body of the lambda.

edited Jan 25 '13 at 23:43

answered Jan 25 '13 at 23:38

Andy Prowl

119,862
22
374
446

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
@ildjarn: correct, thank you for pointing that out. – Andy Prowl Jan 25 '13 at 23:45
29

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

Can lambda functions be recursive?

1 Answers1

Linked