Java Recursion

hi in this video I want to talk about a topic that has been proven the most confusing for newcomers in computer science and that's called recursion when you're first exposed to recursion as a new programmer you sort of kind of get the idea but you don't really know exactly how it works and it's hard to apply it to solve real problems and the reason why it's so tricky is that there is a lot going on behind the scenes when recursion is running so I'm going to present those details to you we're going to deconstruct and sort of demystify understand what's going on behind the scenes when recursion is taking place so stay tuned I'm going to see it right here on eliminate code fear recursion is a fundamental concept in computer science and all it is is a method that invokes itself so you're aware of how to define a method you give it the name of the method and in the definition you have instructions on how the method should perform the given task well one of those instructions are in bulk itself okay and this is what's confusing to a lot of people so I'll give you an example if we have a method called foo in the body of the method if it invokes itself that's referred to as a recursive method and this is what confused a lot of people it sort of seems like lifting your own self with your bootstraps right floating in the air and it's kind of magical isn't it well it's not that magical there are a lot of things that are happening behind the scenes in a java application and we reviewed we reviewed a topic on the stack a few lessons ago where the stack maintains method invocation so we're going to revisit that with respect to recursion and how it maintains method invocation when recursion is going on and that's going to make a lot of sense so let's give that let's draw that stack right here on the side here so again stack is a memory area reserved to maintain method invocations when your application starts up the first method that's invoked is the main method so that gets added to the stack right that's the starting point of every job application and methods are what do all of the work in Java so here in the main I can invoke some method called bar for example when the interpreter gets to here it's going to add that to the stack and in the body of this method wherever the definition is let's say in this definition of bar it invokes some method called do work when the interpreter gets here it goes into the body of this method it sees do work it invokes to work as well so it adds that to the stack and let's say and do work right it has some other method being invoked called do more once the interpreter identifies where do work is it starts executing the instructions in this method it sees do more it's going to add do more to the stack as well so this is how method invocations get piled up on the stack and do work is waiting for do more to complete all right and bar is waiting for do work to complete and main main would also like to proceed after bar whatever the instructions are in the main method so all these methods are waiting for the one that they called to complete so our the way I want you to think about it is bar invoked do work so it's waiting for new work to complete do work invoke do more so it's waiting for do more to complete do more could be waiting on other methods that it invoked to complete so once do more is complete it right and it moves to the next line do more is eliminated from the stack okay because we're done invoking do more and then finally when we exit to work and we move on to other things in the bar do work is eliminated from the stack and finally when we when the exit bar right and we move on to bigger and better things in the main bar is also eliminated from the stack okay so this is how method invocation works on the stack so let's take a look at what happens on the stack when we have a recursive method I'm going to define that right here let's say we have a method called foo and in the body of this method it's invoking itself and here in the main when I invoke fool this is the original invocation when the interpreter gets to here it's going to find where the foods definition is wherever it is in the project it's going to start executing the code that's in this method when it comes across foo first of all when when the interpreter see is foo it's going to add that to the stack that it's going to execute the instructions in foo it's going to see fool again it's going to add fool yet again all right and then it's going to execute foo yet again and it's going to call it again and again and again and again until we run out of stack space okay and that's the famous error that you may have heard of it's called a stack overflow error there's actually a website based off of stack over a little bit that's exactly what's going on here we run out of stack space right this method will continue to call itself indefinitely okay we until of course it the program crashes so we need a way to tell this method that hey stop calling yourself if this condition is satisfied in this case we didn't give it any conditions they'll just continue to call itself forever this Fuma invocation is waiting on this one this one is waiting on this one this one is waiting on this one they're all waiting for the one that they called to complete and they will never complete because they will continue to further call whatever is in their body right so we need a condition up here before we invoke foo inside of this method and I'll define a a correct method that actually has a proper closure so let's get rid of all these fool invocations let's create a method called reduced by one and let's say it accepts an argument of type int and in the body of this method it invokes itself and when it invokes itself in its definition it does n minus one and here in the main when I invoke reduce in the main method and I'm just going to shorthand it for reduce because I don't want to type write the whole thing out let's say we invoke it with the number three when the interpreter gets to this line it's going to add reduce to the stack with the number three it finds where that method is defined it's going to see it's going to see the definition it's going to execute the definition of this method it's going to come across this line it's going to say oh okay n minus one is a new argument for this method so it's going to call the deuce again this time with two and then it's going to call it again this time with one and it's going to continue to call reduce until we run out of stack space okay so three the reduced three is waiting on reduced two to finish reduced two is waiting on reduced one to finish reduce one is waiting on reduced zero and so on okay so this is also a stack overflow problem so I want to ask you a question what would you do in this case how would you make this method eventually your gracefully end right I wanted to stop calling itself indefinitely what would you change about this code so take a minute to figure out on your own how you do that so the way we would correct this and prevent the stack overflow error is we need a condition up here right before it invokes itself and that is for example we do something like this if n is greater than or equal to 0 only then execute what's within these brackets okay and what what is this what what is this going to do well we start with 3 3 is going to be checked against zero and it is greater than 3 so it's going to invoke with the parameter with the argument 2 and then it's going to do that again it's going to invoke with the argument 1 it's going to do it again it's going to invoke with the argument 0 and 0 is still equal to 0 so it's going to invoke this method one last time with negative 1 as the argument right that's going to be you don't see that here but that will in fact be the last invocation so reduced 0 is going to be waiting on its invocation of reduced negative 1 so it's going to once that is exited out negative 1 is going to be removed off the stack then reduce 0 is going to be removed up the stack reduced 2 is waiting on 1 once 1 is completed it's going to pop that off the stack this is also going to come off the stack and then finally our original invocation has been unlimited from the stack and we have moved on to bigger and better things so this is the whole point of recursion so let's go see this in the screencast okay so let's open up Eclipse and I created a package I'll go dot recursion and that's where we're going to implement this reduced by one method and we'll dig into what's going on so let's first create a I'm going to create a class called app and we'll just have the main method in there so we can test things directly and outside of this class I'll define the method it's going to be a public static void and it's called reduce by one and it's accepts an integer argument and here's the thing if I just call reduce by one and I do n minus one I just want to show you what the stack overflow looks like so if I hit the play button here well first I have to invoke this method right I have to invoke it in the main method so let's invoke it here and let's let's say I invoke it with the number and if I hit the play button now there we go we ran into an exception and if you scroll up you'll see that the exception is stack overflow error okay so we need a way to eventually make this end and the way you can do that is wrap this invocation this self invocation let's wrap it in an if statement that says if n is not equal to zero right n is not equal to zero then we wanted to continue to loop right you can either have n is not equal to zero or you can say n is greater than or equal to zero okay and we give a non negative number here for example 10 and if you have to play button notice that the there's no exception everything runs obviously it's not printing anything or doing anything but everything runs successfully when I hit the play button here okay and it's running successfully because it reduces and every iteration okay it subtracts one from it every call and then finally when it gets to when n is actually equal to zero that will be the last invocation now this condition where we're checking for n is greater than or equal to zero this is referred to as the base case this is a terminology that you might hear flying around in the recursive talks but every recursive program must have a condition that eventually causes the recursive call to stop okay and that's referred to as a base case that's what this condition is so now what I want to introduce here is a little statement down here inside of the body of reduced by one I want to print something out just so that we can see what's printed to the screen and what I'm going to say is completed call and with a plus sign I'm going to append the value of n okay now here is where I want you to take a pause and think about you know I really want you to think about what this is going to when I hit the run what will be printed on the screen okay and when you're first you know when you're new to recursion 9 out of 10 times people get this wrong okay so don't be surprised if you what you expect to be printed out is not the case okay you may get this wrong which is totally understandable you're new to this right so now pause the video think about it and I'm about to hit the play button and I'll show you what happens all right so when I hit the play button this is what gets returned okay and notice that the first thing that gets returned is a negative one and then a zero one two three four all the way down to ten now a lot of people think about the ten being printed out first but that's not the case right what happens is when we pass in a ten here that 10 is going to be you know checked whether it's greater than or equal to zero and in in this case of course it is so if this method is going to be executed and it's going to be 10 minus 1 then that invocation it starts a new invocation with the number 9 and 9 is still greater than or equal to 0 so 9 minus 1 is 8 8 minus 1 is 7 7 minus 1 is 6 6 minus 1 is 5 so we're still inside of this method invocation without ever having gone down to this print line statement we're caught up in here we haven't gone here yet so what happens is once this n is less than 0 once this n gets less than 0 then we stop invoking this OK it will basically come down to here and the value at 410 excuse me the value for n at that point all right when this condition is finally satisfied and we don't have to call ourselves anymore and we move to here the value of n at that point is going to be of course negative 1 and then since this call was waiting for negative 1 then this call is satisfied it's happy it's got a negative 1 this call was waiting for this 1 right 2 was waiting for 1 3 was waiting for - four was waiting for 3 5 was waiting for 4 6 was waiting for 5 7 was waiting for 6 so eventually it finally gets down to the first argument that we passed right this was the grandfather of all of these other calls and we may basically get this printed out at the end because this is you know this is the first method on the stack all the way on the bottom right above main this is the first invocation that was waiting for all of these other things on the stack to execute and then finally when it gets to here it prints n okay so this is a confusing concept for a lot of people to understand so I'd recommend that you review this code and understand what's really going on here and why instead of 10 being on top it's actually negative one this is referred to as back tracing all of these method calls are waiting for the ones that are ahead of it to be to be returned right so that's an important point to keep in mind 10 was waiting for nine nine was waiting for eight eight was waiting for seven seven was waiting for six so in this call we invoke two this one and this call we invoke two this one in this it called we invoke two this one right all the way up to the final call that satisfied this particular condition and we no longer we no longer have to invoke this and we are ready to print to the screen this right here okay now we're not through with recursion yet you need some practice just a few lessons ago you looked at linear search right and we had a basic algorithm for searching well linear search can be solved recursively as well and this is the pseudocode that you can follow follow these instructions and implement recursive linear search in java and then after that we'll look at the recursive solution for binary search and then you'll have a lot you'll be better prepared for future recursive algorithms so definitely do justice with this problem try this out work on it and then in the next lesson I'll show you in Java code how this is supposed to be coded actually let me get you started with the method definition we're back here in Eclipse right in our main class you can code this method up right in the I'll go dot recursion package and the method will be a static method and this time it's going to return it's supposed to return the index position of where it found the given x value that we're looking for so it's going to turn int and the method we can just call it recursive linear search and it accepts three arguments this time the first argument is an integer array and we'll just say the variable name is a I is going to be the index position within the array where we are currently at during the searching process and X is going to be the value that we're searching for and these are both of course integer data types so let's add the data type here and you can fill the body of this method I'm just going to leave it up to this point so give it a shot and I'll see you in the next lesson

Channel: Imtiaz Ahmad

Views: 99,870

Rating: 4.9053497 out of 5

Keywords: recursion, java, data structures, algorithms, Object-oriented Programming (Programming Language Paradigm), Java (Programming Language), Java Tutorial, Object Oriented Programming, Java SE 8 Programmer, 1Z0-808, java certification training, object oriented programming java, oop, object-oriented programming, object oriented programming

Id: ttTH_WX-Cbo

Length: 18min 48sec (1128 seconds)

Published: Fri Apr 22 2016