OK, so our next topic is one that many students find quite difficult to wrap their head around despite
its simplicity.
That topic is recursion.
And in this lecture, we will hopefully demystify some of the confusion surrounding it, so let's go
ahead and get started.
So what is recursion?
For those of you that haven't yet heard of it, a simple explanation is that it is a problem-solving
technique and it is the technique that uses function calls instead of loops for solving problems that
require repetition.
So while loops are considered iterative solutions, when we talk about recursion, we are talking about
a function calling itself somehow, whether that be a direct call kind of like how you see in the picture
here on the slide that's inside the function implementation itself.
Or maybe it is indirect where this recursion function calls another function that in turn calls this
recursion function again.
This function that you see here, recursion would be considered a recursive function, although it is
not very useful.
So let's take a closer look at this function.
In fact, you should go ahead and just pause the video and write a C++ program, probably in a text
editor, so it's more simple write a program that implements this function and calls it.
So go ahead and do that.
OK, so if you went ahead and did that, you might have noticed something weird.
It most likely gave you a segmentation fault.
And the reason for this is something that we call Stack Overflow.
So let's go ahead and go over that term.
What is a stack and what a stack overflow mean?
So technically, a stack is just a data structure.
You can imagine it like a stack of something, you know, have some kind of analogy that works best
for you.
You can think of it like plates, pancakes, any things you could stack on top of each other.
But it's just a data structure where things are piled on top of each other.
We are going to look at using this data structure in our code later to help us with our programs.
But that is something different than what we're talking about today, which is a region of the computer's
memory that is called the stack and functions like that stack data structure.
So basically, each time a function is called another, what we call a stack frame is added to the stack,
and we refer to this as pushing a new frame to the stack.
So this frame that's pushed to the stack, it contains information about the current function, it's
a function call and it'll have the things like the local variables and stuff like that in it, for example.
OK, so what is Stack Overflow?
Well, the problem with this function that we were looking at is that it just calls itself and has no
nothing really stopping it, no mechanism to stop it.
So it would most likely just infinitely call itself if something didn't intervene, although the program
did stop and you got a segfault.
That is because the stacked section of the computer's memory eventually runs out of space when we're
pushing those frames to it, those frames and all that information actually overflows into another segment
of memory.
And that's what causes the Stack Overflow and is what led to you seeing that segfault air.
So let's look in a more useful example, recursion that does something besides just having a function
call itself.
So this function here returns the sum of all numbers up to the number in that it's being passed in the
function as an argument.
And so what we are doing here is basically solving this same problem backwards, so we're starting with
the number that we want to go up to and including for our some.
Rather than doing it forwards and you can see that is happening here in this return statement.
Where let's say we start out with a four.
What we're doing is we would return for plus the sum of three because we have four minus one and it
would go back here and do the same thing for three, it would be three plus the sum of two.
And it just works kind of in reverse like that.
But you notice that we still don't really have a stopping mechanism.
So how would we set that up to prevent it from going on infinitely or until we get a Stack Overflow?
So the way we're going to do this is use something called a base case.
So as we work backwards to solve this problem, we're going to go and tell in is zero.
And that will be our stopping condition, which is our base case, and once in is zero, we're just
going to return zero and this is where the magic happens because this is where we will do our actual
addition that creates the some.
It's kind of like we're putting off the work as we keep bouncing back and forth between this return
and the top of the function.
We're kind of saying like, OK, you want me to do four, I'm going to go ahead and do three and try
and figure that out, OK, you want me to do three and we'll go ahead and do two and figure that out.
And I recognize that you're asking me each time to add the current in that I'm on and the previous one.
And it'll get all the way to zero and we'll return zero.
And then it will go back through all that work that it put aside and add up all of these different ends.
The state, you know that endless end so we can get our summit.
So let's go ahead and work through this example to see how how it actually works.
So.
We start out with N equals four.
Then we're going to have an equals three, as we saw.
So we have any goals for it, go down here for IS was not equal to zero, so we didn't return.
We returned this line here, which is four plus the sum of four minus one, which is three, so we went
back to the top.
So now we're on this call.
Same thing.
You know, three minus one is to go back up here.
Two win, one is one.
And of course, one minus one is zero now and is zero.
And we're saying if N equals zero.
Yes, it does.
Let's go ahead and return zero.
And this is where the magic of recursion happens.
So what we're going to do is we're returning zero from this function, call this stack frame back to
this one.
And then we're basically adding, as you see, we return to zero.
And we're adding that to one, so in this room right here in was one.
Since we returned zero from this frame and it came back here, we're looking at this line right here
to do this edition right here.
So return when in is one, we returning one plus what was returned from here, which is zero.
So you notice there was this function call here.
When we're talking about zero or thinking about this, this specific function call this stack frame
that returns zero, so you basically can take that and put it right here and now in the function call
in which in was one.
We're having this line right here is looking like this.
We're going to return one plus that zero that was returned.
So let's continue this pattern.
We have when Annie goes to win, you win to plus the one that was returned, that's three.
We have an equals three.
We're doing three plus the three that was returned from this frame.
And when it equals four, we're doing this four plus six, which was the sum of this previous result
there.
So we end up with 10.
So four plus three plus two plus one.
That was our sum, plus zero, of course, that was our son there, so we ended up with 10.
So hopefully that makes sense.
I went ahead and just tried to start out with a basic example, so you could kind of just see what the
recursion itself is actually doing.
Like this is where in this specific example of recursion, the interesting stuff is happening in the
recursive process when we go back down the stack here.
OK, so let's continue.
Let's look at a slightly less trivial example, something a little more complex.
I'm not sure if you have heard of the Fibonacci sequence, but this is it right here.
And it is obtained by adding the previous to Fibonacci numbers, so whatever number you're talking about
in the Fibonacci sequence.
Like, for example, to.
Right here.
So this would be one to sorry.
Well, yeah, the.
It would be the sea.
0tH, 1st, 2nd, 3rd.
So this third Fibonacci number is going to be the result of something the previous two right here,
so one plus one is two.
So that's kind of how the feminazi sequence works, and we are writing a recursive function to calculate
the end Fibonacci numbers.
So just some Fibonacci number.
And you see here, I've already started with an example where we are looking at the.
Six Fibonacci number, so we have zero one two three four five six.
So the index of six in this, that's what we're talking about in this example.
So calculate the Fibonacci numbers.
So this is a function, a recursive function that would do that.
We're passing in as the feminazi number we want.
And then what we are doing is setting up our base case here where we say, if in is less than or equal
to one return in and you'll see why we're doing that in a moment, it's because just a quick explanation
is that.
This tree here that I'm about to explain is what's representing the recursive calls and these stack
frames here.
Each one of these nodes, these dots here, and you notice that at the bottom, these are base cases
and you can see that some of them are one in, some of them are zero.
So that's why we're putting less than or equal to one here.
And then just like I said, you add the previous two numbers, so what we're doing is calling the function
again with our, you know, one less than in and then adding to less than in.
So these are represent our two previous numbers that we're summing up to get the Fibonacci number.
And just kind of taking a look again at recursion in general and the purpose and how it works.
We want to know, let's say, this six Fibonacci number, but to know that to solve that by using recursion.
We're going to need to figure out these smaller sub problems.
And when I talk about smaller sub problems, it's kind of a precursor to what we're going to speak more
about in the future and learn more about when we talk about divide and conquer algorithms and things
like that.
A lot of times it's.
A good way to solve problems is to break the problem into smaller sub problems and solve those by breaking
that into smaller sub problems until you reach a point where it's quite simple to solve.
And then you can kind of in this example with recursion.
Then once we have that base case, we can solve all of these other sub problems that we had back up
to our original problem.
So that's just kind of a general explanation of what's happening here with this.
We have two recursive calls, so it's slightly more complex than that previous example where we only
had one recursive call.
So let me get into explaining what this is right here.
This tree structure, it is in fact called a tree is a recursive tree.
And.
Like I said, what this represents is each one of these gray dots or nodes or whatever you'd like to
use to represent that.
These are each stack frames or actual function calls.
And the number inside here is in at that specific function call what in is what state and has there.
So we start out as six in this example.
So we want to find the six Fibonacci number.
The arrows to the left are pointing to this function, call the N minus one so one before you know,
the like one less than the N that we are talking about the Fibonacci number.
The right call function call.
Is this one right here?
So it is the, you know, two before the end Fibonacci number that we are at on any given function call,
and you see that this pattern continues, we have two children breaking off here because we have to
function calls, so.
I'm also going to refer to things like that, like this node and this node are child nodes of this node
right here.
So you could consider this node with the six, the parent node of these two child nodes.
And so just to kind of do a quick recap on that.
These this sub tree over here in this sub over here and so on and so forth.
The left is represented by this function call and the right is represented by this function call here.
OK, so let's take a little bit deeper, look at the tree then.
So we start out with six here.
We originally start with our function and we pass six to our function, six is not less than or equal
to one, so we go down here and we say, Hey, return fib of six minus one plus five oh six minus two,
but right when you hit this, it's going to jump back up here to this function, call again with five.
And so that's what this is right here.
And so if we just keep traversing it in that fashion, this tree right here and we're just like, OK,
it's making us jump back up, jump back up here, and it's kind of setting this aside that we need to
add this function, call to it each time.
If you're just taking left turns, it kind of goes like this like six two five five two four four two
three three two two two two one.
And we stop here because this goes with our base case here.
When MN is one in is equal to one.
We said less than or equal to.
And so it's just going to return in and since in is one.
We're just returning this right here and that's going to return back up to here.
So if we look at the right call and let's go back down to this bottom part right here.
We have two and two minus two is zero, so we would go back up to the top for this function call in
would be zero zero is less than one.
So we're going to return it in is zero.
So this is going to get added to this.
And you know, this is what's going to get returns.
So when I was saying, we're going to turn that back up here from this one, what we're actually doing
this, we're returning this some of these to back up to this node.
So it would be one plus zero.
So now that you kind of have a general understanding of what these areas are for, how we're representing
these recursive calls and the whole idea of this tree, you know, these are base cases down here like
this, this this, this this all these are base cases.
Let's go ahead and walk through this example here.
I'm going to start down at the base cases and work our way back up to show how the recursion actually
solve this.
So let's go ahead and do that.
So we start down at this left most portion of the tree where we had in is to.
And then we did this recursive call to minus one, which was one.
And then we had two minus two, which is zero.
So we ended up.
You notice the one, just like I talked about that recursive call where it was one, it returned one.
And so that one can basically be put right here and remember this right here.
Represents this right here, and then you can imagine a plus sign right here, and then we had two months
to is zero zero was less than one, so we return zero.
And imagine that that can be taken and put, you know, right here.
And so basically like this is representing this really what these are representing are these returned
values.
But to help us understand it, this function call is going to be added to this function call.
And what we want to do is add this one plus this zero.
So the one that was returned and this zero that was returned, we're putting them back into the function
calls right here.
So that equals one.
And so that's going to go the answer of one is going to go back up to this recursive function call.
OK, so we're going to move on to this next portion then.
I'm color coding these, so it's a little easier to understand.
The green is going to be our base cases, you know, we had this one in the zero where our base case
returned values.
We returned one up to here up into this node.
So that is the yellow right here.
And then we have another base case right here, which is one because when we have an equal three.
You notice that we did three minus one for this call and we had two right here, and that's what led
us to this whole sub here.
But then when we did three minus two, that was this right here and we came back up here, three minus
two is one.
And one suffices for our base case here.
So that's why we have this one right here.
It has no children.
It's a base case and that's represented by this green right here.
So we have the one that was returned back up here, plus this base case one right here, which is to.
So hopefully you're following along with me, let's keep going.
I'm going to jump over here to solve this little problem.
So we have another base case we have one plus zero is one.
We get this blue one here, and, you know, as we took our answer here and our answer here, you can
now see this whole green box as like one of these.
And this whole game box as one of these here, some members of problems, these are two such problems.
Imagine a plus sign right here.
So we have our one that was passed back up to here or sorry, not that we have our two.
We added these two to get two, and then we added these base cases to get this blue one here.
And so the one comes back up to here, the blue one kind of back up to here.
And this red too comes back up to here and we have two plus one is three.
So I'm going to do these here real quick.
And we have a one plus zero is one that one comes back up here.
We have the blue one plus our green base case one equals two.
Let's go back up here.
We take this three that gets returned up to this function call and we have our three plus hour orange
too, which just goes right here.
So two to hear this three two here, we're adding them together.
You mentioned that plus sign at five.
Let's go over and solve this over here now.
We have our base cases.
One goes up to here.
That's to.
We have one right here.
This two plus this one is three.
Now we go up to here and we add our five plus three, so we had this five from here.
This three first year, we added them and we get eight.
And that is what is returning for our final answer here.
So the six Fibonacci zero one two three four five six is eight.
And so you can now see how that was solved.
It looks a little complex, but if you walk through these recursive three examples, they can kind of
explain it in greater detail and make it a little more obvious.
So you might notice that this has a pretty poor time complexity.
You notice that there are some repetition, so you can see this whole sub tree here is pretty much,
you know, it's reflected over here.
So I had to calculate this same thing multiple times.
These trees can get pretty big.
You should go ahead and.
Put this in a program, this function here.
Make a C++ program, write this function and then go ahead and pass 50 as end to the initial call there
and see like how long your computer takes to solve that problem.
This tree is going to be really big, and you'll notice that the program should hang up quite a bit
or take a really long time to solve it, at which point you might just want to exit out.
So, yeah, that'll make you realize that it does have a pretty poor time complexity.
And later on, we're going to optimize this with another programming strategy.
So since it's pretty slow, don't worry about that.
We're just going over recursion and kind of some more naive solutions that can be further optimized
later on.
Another thing to look at that we haven't talked about yet of something that goes way we go is that each
one of the nodes on this tree.
These gray nodes here.
They represent a stacked frame like we talked about, but you can also think of that as memory space
being taken up.
So we talked about how the stack frames pile up in the stack, which is a region of memory.
Something we haven't really talked about yet is space complexity.
We've talked a little bit about time complexity, but later on we're going to also talk about taking
space in an account to how efficient an algorithm is.
It's not just about how fast it is.
It's also about how much space it takes up.
So just wanted to add that in here right now, just so you kind of plant a seed about this idea of space
complexity as well.
You know, if you have a huge tree with recursion here, you should definitely consider when you're
writing a recursive algorithm, consider the fact that these stack frames are what are going to be used
for our idea of how much space the algorithm takes up.
So keep that in mind.
One last thing I just want to point out that we can also use recursion to traverse data structures.
So this is a simple example with just a vector.
But I'm going to go ahead and provide some problems for you to solve to kind of test yourself out like
with how well, you know, recursion after this lecture and to help you push yourself a little bit and
learn to solve recursive problems on your own.
And we will be doing some problems with traversing data structures like a vector, so I wanted to introduce
that.
This is an entire program here if you want to type that into a text editor and run it.
What we're doing is just declaring a vector right here and we are passing the vector itself and the
last element of the vector by doing my vector size minus one up to our recursive function here.
So this is the last element of the vector and the vector itself passed by reference, and we're just
printing out the vector in reverse order, starting at the end and doing that in minus one thing that
we've already seen with recursion.
Here's our recursive call, and then our base case is, of course, when it is zero and you know this
here is the first element of the vector so we can stop.
It's just a void function.
So we're just returning when in is at the first element of the vector.
So you can just go ahead and test this out.
It should print out five four three two one.
Of course, on new lines because we have an in line.
But I wanted to mention this as well.
Just so you know you have.
The knowledge that recursion is also used for traversing data structures and as we'll see later on,
it is not just used two to first steal things like this, but we can also traverse things like link
lists and another topic we'll get into, which is trees.
So hopefully that explained everything, and I will go ahead and provide some problems that you can
use to practice this.
But of course, with the recursion and most other things as well, practice makes perfect.
So go ahead and come up with some recursive functions that are kind of another way to solve things that
you've done with loops.
So think of something that you problem you solve by using while loops or for loops and see if you can
transform that into a recursive solution.
So something that requires repetition.
Just some simple things.
See if you can instead have a function, call itself and implement a recursive solution to it just so
you can get some extra practice.
All right.
And with that, I will see you in the next lecture.