‫So now we're going to do our introduction to recursion.
‫And my favorite definition of recursion is that it is a function that calls itself until it doesn't.
‫So to explain this, I'm going to bring up a gift box and we need to open the gift box.
‫So how do we open gift boxes?
‫We open gift boxes by calling the open gift box function.
‫And when we open the gift box, we could get a gift, in this case, a ball, or we could get a smaller
‫gift box.
‫And the way that we open gift boxes is with the open gift box functions we're calling the same function
‫again.
‫And when we call this function on this gift box, we can get a gift, a ball or a smaller gift box.
‫Once again, we call the open gift box function.
‫And in this case, we'll say that this box contains the ball.
‫So now let's put this back and we're going to write some pseudo code.
‫So don't try to write this code because it won't work.
‫It's just pseudocode.
‫So we'll have a function called Open Gift Box.
‫It returns a pointer to an object that is a ball.
‫So when we run this function, we'll either get a ball or a gift box.
‫We need to test for that.
‫We'll say if is ball.
‫In other words, if what's inside of the box is a ball, we're going to return the ball.
‫Now, if we were writing real code, we would probably have a line that looks like this that actually
‫creates the ball.
‫But I want to keep this simple, so I'm going to remove this line and just keep the if statement.
‫So if the conditional in this if statement is false, that means we have a gift box.
‫And if we have a gift box, we need to run open gift box.
‫And this is where the function calls itself.
‫So in recursion, there are a couple of rules.
‫First, the process of opening each new box is the same or the process of doing whatever it is that
‫you're doing has to be the same.
‫The other rule is that each time we open a box, we make the problem smaller or whatever it is that
‫you're doing with recursion, each step has to be smaller than the step before.
‫So that's why I show the gift box is getting smaller and smaller.
‫So let's remove these and then we'll walk through this code and show how it would work.
‫First, you call the open gift box function.
‫We're going to check to see, is this a ball?
‫And in this case, it is not.
‫It is a gift box.
‫So we're going to need to run the open gift box function.
‫And this adds another instance of open gift box to the call stack.
‫And we'll talk about the call stack in more detail in the next video.
‫So now with this gift box, we're going to say, is this a ball?
‫And in this case, it is not.
‫It is another gift box, which means we need to run open gift box again, which adds another instance
‫of the open gift box function to the call stack.
‫Now, we'll check to see, is this a ball?
‫In this case, it is.
‫So we will return the ball.
‫And because we ran this return statement, we are not going to run this line of code.
‫We're just going to return the ball.
‫So now let's put this back and talk a little bit about terminology.
‫If this box contains the ball, this is what is called a base case.
‫Once we get to the base case, we don't want to keep calling new instances of the function.
‫If this is a gift box, this is what is called a recursive case.
‫This is where we need to call another instance of the open gift box function.
‫And this is also a recursive case, and this is our base case.
‫So let's bring back our code.
‫So this if statement is what we do when we reach our base case, if we don't have a base case and we
‫remove this, you run an instance of the function and then it runs this line, which creates another
‫instance of the function, which runs this line, which creates another instance of the function.
‫And we end up in an infinite loop of adding new instances of the function to the call stack.
‫And if that happens, you get what is called a Stack Overflow.
‫So you have to have something like this which will break us out of that loop of adding new instances
‫to the call stack.
‫So there are two essential parts in this if statement.
‫First, this conditional has to be true at some point.
‫So if you have something like this, if one is greater than two, well, that can never be true.
‫Which means we will end up in that infinite loop of creating new instances.
‫So you might look at that and say, Well, that is obvious that one is not greater than two, but you
‫could have something more complex than this in your conditional.
‫So if you're getting a Stack Overflow, this is one of the places to troubleshoot.
‫So I'm going to bring this back.
‫And the other thing is you need to have a return statement.
‫So let's take this out and replace it with see out.
‫Hello.
‫In this situation, once this conditional becomes true, all we're doing is outputting the word hello.
‫And because it is not a return statement.
‫Once you run this line of code, you're just going to come right down here and go back into that loop
‫of adding instances to the call stack.
‫So it is very important that you have this return statement, and that is our introduction to recursion.