Hello, and welcome to C++ Weekly.
I'm your host, Jason Turner.
I'm available for code reviews, contracting,
and on-site training.
Now, in this episode, I would like
to discuss how one might go about making a recursive lambda
function.
And then, I will attempt to extend that example into one
that is mutually recursive.
So let's just go ahead and start out here,
and I'm just going to make these implicitly
static variables declared outside of any function.
So if I want to make, say, a Fibonacci function,
and I'm going to call it fib, but I
want to do it as a lambda.
And Fibonacci is this kind of just classical recursive thing.
And I have some integer value that I am working from,
so that's going to be my input.
Now, the classic Fibonacci is something
like return Fibonacci minus 1, input minus 1,
something like this.
And then we have to do a check up here.
If input is less than 2, then return input.
And there's a couple of different ways to do this,
whether or not you make the 0 and 1 cases, 0 or 0, 1,
whatever.
So in this particular case, the 0 case is going to be 1.
The 1 case will be 1.
Do that.
Now, we want to call this function.
So let's just say we want main to return
the value of Fibonacci of 3, something like that.
So this isn't compiling, and it's not compiling
for an obvious reason.
And the obvious reason is that we don't have
access to this name right here.
We've just declared a function Object, basically, our lambda
here.
And it doesn't have access to this name.
It has no way of calling itself, because this name hasn't
been created yet until after this function has been defined.
So we have no way to call it in a lambda.
So what we really need is a function called fib to call.
Well, let's just pretend like we have one of those available.
And we can do this.
We can say I want to call this function called fib
with the recursive inputs of these things.
And how do we get access to that function called fib?
Well, we can do it like this.
We just pass ourselves in.
Now we're going to get a different compile error,
because these two function calls to fib
are also looking for the thing called fib they need to call.
So that's all right.
We just pass it in one more level deep,
and we get the value that we expect.
So let's see if we did this right.
If we read x for 0, OK, we get 1.
If we ask for 1, we're going to get 1.
If we get 2, then we're going to get 2, and 3 should be 3,
and then 4 should be 5.
OK, very good.
That's doing what we want it to do.
It works as expected.
Now, this seems a little silly, perhaps,
that you have to pass this thing in here when we're actually
calling it right here.
So one option that we could do is
we want to create this thing called fib, but let's make
this one called fib underscore.
And then here, we can make the actual function called fib
for our Fibonacci that we want.
And have this return the function called
fib with the function called fib and then the input, and that
starts to look like this.
And now here, we have something that is callable
and makes at least some sense.
Now we also have this fib underscore
variable that seems a little unnecessary to have hanging out
here.
So what we could do is wrap this all up nice and cleanly
inside another lambda.
And we already know what this looks like.
It's going to accept an input.
We're going to call this fib.
We're going to create this inside of here.
This is our fib underscore that we will be calling in a moment.
And now we get this lambda called
fib that defines, inside of it, the actual implementation
that we need.
And then, from here, calls that implementation recursively
and gets what we want.
Now, we have the question of, well,
if we wanted to make these mutually recursive functions,
surely this is going to get a little silly.
And in fact, it will get a little silly,
but it is something that we still can do.
So I'm going to go back to some other function here.
I'm going to make something perhaps a little bit simpler.
So we're going to have this function called f1,
and if the value is less than 2, we're
going to leave that the same.
We'll just return 1.
Otherwise, we will return a function called f2
with its input minus 1.
So something that we know that we
want it to eventually converge.
That's kind of important here.
And since I am completely making this up on the fly right now,
I have no idea how it'll go, but we will see.
So we have two functions that at least
attempt to call each other.
And at the moment, this can't work for a couple of reasons.
We can't see the f1 and f2 that we need
from inside of these functions.
So we're going to go ahead and create parameters for those.
Now I am going to call the f2 function,
and that is something yet to be defined.
And down here, I am going to call the f1 function.
And I need to get that here.
And now we're starting to get something
that looks like it's going to compile,
but we need to actually call this.
So let's trigger this off with a call to f1,
and we need the functions f1 and f2 to pass into it.
So we can do that.
And then our input, I don't know,
we're just going to put something small in,
because I have no idea what the value of this is going to be.
And now we're going to get this compile time
error, because the function f2 needs the functions f1 and f2
passed into it.
So I can do that here.
And then f1 also needs the functions f1 and f2
passed into it.
And if I do that, then the code is now compiling.
And we are getting the value 11.
Whether or not that's the correct value,
I don't know, because we just made this whole thing up
in the first place.
But we can make mutually recursive functions.
And if we were to continue this way that we
had gone with the last example, then our auto f1
is going to be--
and now it becomes slightly less crazy
looking to call this again.
And we can make our mutually recursive functions.
And with a little bit of imagination,
we could continue to wrap these into things
that hide the implementation details from the user.
But yes, it is definitely possible to write
recursive functions with lambdas and possible to write
mutually recursive functions.
Although, I did some searching around Wikipedia and such
and didn't find very many great examples of mutually recursive
functions.
So certainly, if you have a great example of one,
leave a comment here in the notes,
and maybe it would be something fun for you
to play with and learn more about how you can use lambdas
in some of these cases.
Although, I am not suggesting this
is actually a good use of lambdas, just for the record.
Because it is quite easy, actually,
to just to define these as regular free functions.
That would be considerably less work.
This is just a "this is possible" kind of episode.
So thanks for watching, and I hope you enjoyed this episode
of C++ Weekly.