Mastering Recursion in Java Programming

Recursion is one of those things in Java that can just be tough to wrap your head around. And even if you kind of understand it, you can easily run into errors if you don't know how to implement recursive algorithms properly. In this video, we'll go over exactly what recursion is, how to use it, and what kind of structure you need to put into your recursive algorithms to avoid getting yourself into trouble. My name's John, I'm a lead Java software engineer, and I love sharing what I've learned with you in a clear and understandable way. I also have a full Java course available and a link down in the description if you're interested. Let's get right to it. So first of all, just what exactly is recursion? All recursion is, is when you have a method that calls itself. That's it. Let's start with an example. Let's say we had a method, private, static, void, sayHi. And all it does is just print out, hi. Now, of course, if we call this sayHi method from our main method and run our program, we just get a printout that says, hi. But now what if we introduced some recursion? Remember, all recursion is is when a method calls itself. So all we have to do to make this method recursive is call sayHi from within this method. Okay, so it looks like it printed out hi a zillion times before eventually blowing up with a stack overflow error. So what exactly happened there? Well, when we first call sayHi from our main method, it jumps into the sayHi method and prints out hi. But then it makes a recursive call to itself. The sayHi method calls the sayHi method. And then that run of the method starts, it prints out hi, and then it recursively calls sayHi again. So it kind of looks like this would just keep going on and on forever, right? Kind of like if your program was stuck in an infinite loop, which you've probably run into before, where your program just keeps doing the same thing over and over again and never stops. But in this case, our program does stop when it runs into a stack overflow error. Why do we get this error? So here's what's happening. While your Java program is executing, every time it enters a new method, it puts the information for that method on something called the call stack. So at the beginning of your program, when your main method starts, Java puts all the information for the main method onto the call stack. That information includes things like the name of the method, references to any variables that were passed in, things like that. Once that method finishes and your program leaves the method, Java... takes the information for that method off of the call stack because it doesn't need it anymore. And if that method was the main method at the bottom of the call stack, then your program exits and finishes. But if Java is running your main method and it has that information for that method on the call stack, if inside that method it has to call another method, Java adds the information for that method onto the call stack too. And if that method calls another method inside of it, Java has to add that method that it calls onto the call stack too. And this keeps going and keeps happening the deeper that the method calls go. Now when any of these inner methods complete, Java takes the information for that method off the call stack because it's done with it. And while your program is running, Java keeps doing this, adding things and removing things from the call stack as methods get called from inside of other methods and as methods get completed and things get removed from the call stack. And it keeps doing that until it finally gets back to your main method and your main method eventually completes ending your program. But here's what happens with our recursion situation. First the main method is called and that info goes on the stack. Then the main method calls the sayHi method and the information for that method call goes on the stack. But before this sayHi method finishes, it actually calls the sayHi method again from within it. And the information for that call to sayHi gets added to the stack. You get the picture. The same method gets called recursively over and over and over again. And the call stack just keeps getting deeper and deeper and deeper. And there's nothing in the program that will stop it from just continuing to grow. So it just keeps growing and growing. But the thing is, Java only has so much memory allocated to this call stack. So if you just keep adding method call information over and over and over again to the call stack, eventually that stack just gets so huge that it... overflows and you get a stack overflow error. Makes sense? So does that just mean that recursion is terrible and every single time we try to use it our program is going to blow up with a stack overflow error? Well yes, unless you know how to code your recursive programs right so that that doesn't happen. The problem of course is that it just keeps calling this method over and over again recursively right? And right now in the program there's nothing that would ever stop it from making that recursive call over and over again. So what we need to do is have something so that this method stops calling itself recursively at some point. Basically you need an exit strategy right? Here's a simple way we can add something like that to our program here. Let's add a parameter to our method. We'll make it an int and we'll just call it count. Next let's add a condition in our method after we've already printed high. so that if that count is less than or equal to 1 we just return. So if the count is less than or equal to 1 it will just return and exit the method and not recursively call sayHi. But otherwise if the count is greater than 1 it will recursively call the sayHi method. But when we call this method recursively instead of just passing in the count that we received let's pass in count minus 1. And then up here where we're first calling the sayHi method from our main method, let's just pass in 3 for the count. So now if we run our program, we can see that it just prints out hi three times and completes successfully. So let's walk through what happened there. So the first time that this sayHi method is called, it gets passed in a 3 for the count. It prints out hi. The count is 3, which is not less than or equal to 1. So it skips this condition and calls the sayHi method recursively. But it calls it. with a count parameter of 2. That run of the method received 3 for the count and 3 minus 1 is 2. So this method is recursively called with a count of 2. It prints out high again. 2 is still not less than or equal to 1. So it skips this condition and recursively calls the sayHigh method again but 2 minus 1 is 1 and it recursively calls the sayHigh method with a count of 1. Then that run of the method prints out high again but this time the count that it received is 1 which is less than or equal to 1. And so instead of calling the sayHi method recursively it just returns and exits that run of the method. So that run of the method returns back to the run of the method that called it recursively and since the recursive method call that that run made completed successfully it will return as well up to the run of the sayHi method that called it. And those method run completions keep bubbling all the way back up to the original call to the sayHi method that was made from our main method. And then finally this original method call is complete which ends our main method and ends our program. So a recursive program doesn't have to die with a stack overflow error if you have an exit strategy like this. There are a couple of parts of that exit strategy that we've implemented here. The first thing is called a base case. A base case is a condition inside your method where it can return without making another recursive call. That's the condition that your recursive calls eventually need to hit so it can return without going deeper and deeper into recursion forever. You need a base case in your recursive method otherwise you will always go into infinite recursion and your program will eventually blow up with a stack overflow error. In this program our base case is here where if the condition is reached where count is less than or equal to one it just returns out of that method without making the recursive call to say hi. But the second thing you need is that in your method you need something that allows it to work toward that base case every time it recurses. So even if you have a base case like this it doesn't matter if your program never actually runs into this base case. Your code needs to eventually get to this base case or you're going to get infinite recursion. Now in our program that was done by adding this count parameter and by using count minus one as that parameter each time we call the sayHi method recursively. So each time this method is called recursively it reduces this count by one. So no matter what number is passed into the initial sayHi call each time the recursive call is made it gets reduced by one. So eventually it will reach the base case where the count is less than or equal to one. And when it finally does hit our base case it returns without making the recursive call which finally ends the cycle of recursion. So together having a base case where we don't call the method recursively and having code that allows the program to work toward that base case make it so we don't get infinite recursion so every recursive algorithm has to have those two elements in order to not get a stack overflow however i will note even having those two elements doesn't absolutely guarantee that your program will always finish before it gets a stack overflow if it has to recursively call itself tons and tons and tons of times before it actually reaches that base case you could still run into problems. For example, we could call our initial sayHi method with 1,000 for the count. And if we run our program, it just finishes successfully. It prints out hi 1,000 times and doesn't get into any stack overflow errors or anything like that. But if we change that to 100,000 for the count and run it, Unfortunately we do run into a stack overflow error. So even though if it could keep going over and over again with those recursive calls it would eventually get to one for the count and hit our base case and bubble all the way back up to the call in our main method. But Java's call stack memory just wasn't large enough to hold a hundred thousand method calls on that stack. So it ended up ending with this error anyway. In this case just using regular iteration with a for loop or something is probably a better way to just print out the word high a zillion times. But I think this is a great way to talk about the idea of recursion and how to use it. If you'd like to dive deeper into using recursion to solve some more complex, real-world kind of problems, check out my Sudoku solver video or my video on implementing the merge sort algorithm. Both of those use recursion for their solutions, but in a much more advanced way than we did here, and they're really cool examples of how recursion can be used to solve problems. So don't stop now, keep up the momentum by checking out one of those other videos using recursion, or another tutorial video like one of these below. And check out the link down in the description if you're interested in my full Java course. Really thank you so much for watching and being here with me, I'll see you next time.

My name's John, I'm a lead Java software engineer, and I love sharing what I've learned with you in a clear and understandable way. I also have a full Java course available and a link down in the description if you're interested. Let's get right to it.

So first of all, just what exactly is recursion? All recursion is, is when you have a method that calls itself. That's it.

Let's start with an example. Let's say we had a method, private, static, void, sayHi. And all it does is just print out, hi.

Now, of course, if we call this sayHi method from our main method and run our program, we just get a printout that says, hi. But now what if we introduced some recursion? Remember, all recursion is is when a method calls itself. So all we have to do to make this method recursive is call sayHi from within this method. Okay, so it looks like it printed out hi a zillion times before eventually blowing up with a stack overflow error.

So what exactly happened there? Well, when we first call sayHi from our main method, it jumps into the sayHi method and prints out hi. But then it makes a recursive call to itself. The sayHi method calls the sayHi method. And then that run of the method starts, it prints out hi, and then it recursively calls sayHi again.

So it kind of looks like this would just keep going on and on forever, right? Kind of like if your program was stuck in an infinite loop, which you've probably run into before, where your program just keeps doing the same thing over and over again and never stops. But in this case, our program does stop when it runs into a stack overflow error. Why do we get this error? So here's what's happening.

While your Java program is executing, every time it enters a new method, it puts the information for that method on something called the call stack. So at the beginning of your program, when your main method starts, Java puts all the information for the main method onto the call stack. That information includes things like the name of the method, references to any variables that were passed in, things like that. Once that method finishes and your program leaves the method, Java...

takes the information for that method off of the call stack because it doesn't need it anymore. And if that method was the main method at the bottom of the call stack, then your program exits and finishes. But if Java is running your main method and it has that information for that method on the call stack, if inside that method it has to call another method, Java adds the information for that method onto the call stack too.

And if that method calls another method inside of it, Java has to add that method that it calls onto the call stack too. And this keeps going and keeps happening the deeper that the method calls go. Now when any of these inner methods complete, Java takes the information for that method off the call stack because it's done with it.

And while your program is running, Java keeps doing this, adding things and removing things from the call stack as methods get called from inside of other methods and as methods get completed and things get removed from the call stack. And it keeps doing that until it finally gets back to your main method and your main method eventually completes ending your program. But here's what happens with our recursion situation.

First the main method is called and that info goes on the stack. Then the main method calls the sayHi method and the information for that method call goes on the stack. But before this sayHi method finishes, it actually calls the sayHi method again from within it.

And the information for that call to sayHi gets added to the stack. You get the picture. The same method gets called recursively over and over and over again. And the call stack just keeps getting deeper and deeper and deeper.

And there's nothing in the program that will stop it from just continuing to grow. So it just keeps growing and growing. But the thing is, Java only has so much memory allocated to this call stack.

So if you just keep adding method call information over and over and over again to the call stack, eventually that stack just gets so huge that it... overflows and you get a stack overflow error. Makes sense? So does that just mean that recursion is terrible and every single time we try to use it our program is going to blow up with a stack overflow error?

Well yes, unless you know how to code your recursive programs right so that that doesn't happen. The problem of course is that it just keeps calling this method over and over again recursively right? And right now in the program there's nothing that would ever stop it from making that recursive call over and over again. So what we need to do is have something so that this method stops calling itself recursively at some point.

Basically you need an exit strategy right? Here's a simple way we can add something like that to our program here. Let's add a parameter to our method. We'll make it an int and we'll just call it count. Next let's add a condition in our method after we've already printed high.

so that if that count is less than or equal to 1 we just return. So if the count is less than or equal to 1 it will just return and exit the method and not recursively call sayHi. But otherwise if the count is greater than 1 it will recursively call the sayHi method.

But when we call this method recursively instead of just passing in the count that we received let's pass in count minus 1. And then up here where we're first calling the sayHi method from our main method, let's just pass in 3 for the count. So now if we run our program, we can see that it just prints out hi three times and completes successfully. So let's walk through what happened there.

So the first time that this sayHi method is called, it gets passed in a 3 for the count. It prints out hi. The count is 3, which is not less than or equal to 1. So it skips this condition and calls the sayHi method recursively. But it calls it. with a count parameter of 2. That run of the method received 3 for the count and 3 minus 1 is 2. So this method is recursively called with a count of 2. It prints out high again.

2 is still not less than or equal to 1. So it skips this condition and recursively calls the sayHigh method again but 2 minus 1 is 1 and it recursively calls the sayHigh method with a count of 1. Then that run of the method prints out high again but this time the count that it received is 1 which is less than or equal to 1. And so instead of calling the sayHi method recursively it just returns and exits that run of the method. So that run of the method returns back to the run of the method that called it recursively and since the recursive method call that that run made completed successfully it will return as well up to the run of the sayHi method that called it. And those method run completions keep bubbling all the way back up to the original call to the sayHi method that was made from our main method.

And then finally this original method call is complete which ends our main method and ends our program. So a recursive program doesn't have to die with a stack overflow error if you have an exit strategy like this. There are a couple of parts of that exit strategy that we've implemented here.

The first thing is called a base case. A base case is a condition inside your method where it can return without making another recursive call. That's the condition that your recursive calls eventually need to hit so it can return without going deeper and deeper into recursion forever.

You need a base case in your recursive method otherwise you will always go into infinite recursion and your program will eventually blow up with a stack overflow error. In this program our base case is here where if the condition is reached where count is less than or equal to one it just returns out of that method without making the recursive call to say hi. But the second thing you need is that in your method you need something that allows it to work toward that base case every time it recurses.

So even if you have a base case like this it doesn't matter if your program never actually runs into this base case. Your code needs to eventually get to this base case or you're going to get infinite recursion. Now in our program that was done by adding this count parameter and by using count minus one as that parameter each time we call the sayHi method recursively.

So each time this method is called recursively it reduces this count by one. So no matter what number is passed into the initial sayHi call each time the recursive call is made it gets reduced by one. So eventually it will reach the base case where the count is less than or equal to one. And when it finally does hit our base case it returns without making the recursive call which finally ends the cycle of recursion.

So together having a base case where we don't call the method recursively and having code that allows the program to work toward that base case make it so we don't get infinite recursion so every recursive algorithm has to have those two elements in order to not get a stack overflow however i will note even having those two elements doesn't absolutely guarantee that your program will always finish before it gets a stack overflow if it has to recursively call itself tons and tons and tons of times before it actually reaches that base case you could still run into problems. For example, we could call our initial sayHi method with 1,000 for the count. And if we run our program, it just finishes successfully. It prints out hi 1,000 times and doesn't get into any stack overflow errors or anything like that. But if we change that to 100,000 for the count and run it, Unfortunately we do run into a stack overflow error.

So even though if it could keep going over and over again with those recursive calls it would eventually get to one for the count and hit our base case and bubble all the way back up to the call in our main method. But Java's call stack memory just wasn't large enough to hold a hundred thousand method calls on that stack. So it ended up ending with this error anyway. In this case just using regular iteration with a for loop or something is probably a better way to just print out the word high a zillion times. But I think this is a great way to talk about the idea of recursion and how to use it.

If you'd like to dive deeper into using recursion to solve some more complex, real-world kind of problems, check out my Sudoku solver video or my video on implementing the merge sort algorithm. Both of those use recursion for their solutions, but in a much more advanced way than we did here, and they're really cool examples of how recursion can be used to solve problems. So don't stop now, keep up the momentum by checking out one of those other videos using recursion, or another tutorial video like one of these below.

And check out the link down in the description if you're interested in my full Java course. Really thank you so much for watching and being here with me, I'll see you next time.

Transcript for:Mastering Recursion in Java Programming

Transcript for:
Mastering Recursion in Java Programming