Introduction to Recursion - Learn In The Best Way

hey everyone welcome back to another video and please listen to me carefully this is the most important video in the entire course period so if you're not aware we are doing an entire data structures algorithms plus interview preparation boot camp and this is the most important video the most important why because here we are starting with recursion so please listen carefully don't skip this part but i'm when i'm when i'm speaking like this one please listen carefully if you skip this video if you skip recursion in general okay if you let's say don't have a clear understanding of recursion and you directly so basically you will not be able to solve you will not understand binary tree you will not be able to solve questions of like let's say linked list you will definitely not understand things like you know like binary search trees and stuff and uh um the the most important part in coding interviews which is dynamic programming you will never in your life understand dynamic programming if you skip recursion you will also not understand how heaps will be working because we will be creating internal implementations of everything so up here down here whatever we'll be doing using the recursion you will not understand graphs you will not understand traversals 90 of the course in the future which is the main part the heart of this course and not just this course not just me if you do data structures algorithms from somewhere else if you're doing some other course or whatever over there also if you skip recursion you will not understand anything in the future i'm telling you openly this is the most important topic this is the base of all the other sections we'll be doing in the future okay please work hard on recursion point number one very important point number two which is also very important open your ears and listen carefully point number two you will face difficulties when learning recursion if you are not facing difficulties when learning recursion it means you are doing something wrong because for beginners it's a little bit complex topic topic okay the recursion is the point where many people give up you don't have to be that person don't be that person you will find yourself in a place after you're watching this video like oh this is so confusing even though i will try my best you know to simplify things internally you will have this feeling here i am not getting any feeling of recursion right now and that is a good thing why because recursion is a topic like this only you will get that feeling after watching when you are starting out but the good thing is once you understand it it will be very easy for you for example recursion for me is very easy now i can teach you all the complex algorithms i can teach you dynamic programming such a great way why can i do it because i practiced and i followed a few steps which those steps this point number three i will tell you how to learn recursion so i will teach you recursion but i will also tell you how to actually learn recursion how to understand recursion how to code in recursion or whatever code recursion pro recursive programs or whatever how to actually practice recursive problems i will tell you that how to understand what is the step to understand even though i will be making sure you are understanding my other tutorial but i will also mention how to understand it if you follow these steps it will take you like one week or let's say two weeks to you know get a hang of recursion then you can do questions and you'll be set so please i'm saying it again and again it may seem a little annoying because i'm repeating things but i'm only repeating it because it's very important you will face difficulties when starting with recursion but only in the start and i will make sure that you are true please don't be that person that quits a course when learning recursion this is what many people do they buy a course or they enroll in a boot camp or whatever they do free course or some playlist or they are even doing let's say my playlist when recursion comes they will be like oh this course is not good because i am not able to understand recursion that is not the problem of the course recursion itself is a topic which is made to be confusing it's not a problem of the course take any course you will find problem in recursion when you're first starting out any course but i will try my best uh by the way if you understand recursion after this video make sure you comment in the uh make sure you leave a comment okay uh because i will try my best to explain it in a very very simple way very simple way if you don't understand that's okay i will also explain how to understand recursive problems after this lecture okay please don't break your streak please don't break your consistency of this boot camp at recursion because recursion is a topic where this happens and you will lose if you do it because if i cannot teach you in such a way i'm not sure if there's any other tutorial that will be able to teach you recursion in a simpler way because i am pretty confident in myself and my teachings and what students have told me so if you face difficulties keep going follow the things that i will mention which brings me to my next point okay don't break this bootcamp streak you will face difficulties i will keep you through it and it will be very easy for you don't worry i will explain everything in detail to be quite frank with you recursion is not a difficult topic to be quite frank with you it is not a difficult topic it is not it's very easy it's very easy to be quite frank with you so another question is should be scared of recursion if you're getting suck no it's only a struggle of one week or something or even two days three days once you understand how things are working it will you will never forget and i will make sure that happens with you this is first part of recursion we will be doing many many other videos so please make sure you watch it okay so don't leave the course in between it's very important and this is by far i can say this and the dynamic programming playlist it will be the best on youtube i can guarantee you that okay so now the next point is point number four kunal how do we actually study recursion we'll talk more about what is recursion and however that is um so let's talk about that first so the point that i have missed right now is how to actually learn recursion okay so so let's take a simple question let's say write a function by the way the prerequisites for recursion is functions two things are required to understand recursion functions already covered memory management already covered you know stack memory heap memory whatever things that is something we have done a lot so please uh check out the link in the description entire playlist is given if you don't know about functions we don't about don't know about memory management link is in the description for that okay so let's say we say write a function very simple program write a function that you know prints hello world i can just say static void message or something okay it just says print hello world that is it if i call this it will be like message that's it hello world now it might be possible that a particular task would be required for you to do multiple times so someone says that okay you are printing hello world right print hello world five times print hello world five times do it five times you can do something like okay kunal we can do something like this what is the problem we can do something like this or we can do something like this make sense okay but i don't want to modify this function i do not want to modify this function in that case what can i do so i can't modify this function i have to print hello world five times what can we do can you think about it pause this video okay so in such problems what you can do is you can create similar functions like this new new functions message 1 message 2 message 3 message poor something like this so now you can call let's say message one but no i don't want to call it again and again the question is let's say saying only one function you have to call and that should print hello world five times that is the question you have to only call one function this function but you cannot add like uh if you're saying five times you cannot add like this five times that is cheating you don't you can't do that so i'm like okay i created other other another functions okay with the same body just different name and here i will just call those functions also so i will here call message1 so basically what will happen is message function will execute this function will execute it will print hello world then it will call message1 message1 will execute it will call hello it will print hello world then it's going to call message number two message number two will execute it will print hello world it will call message number three message number three will execute it will print hello world it will call message number four message number 4 will execute it will print hello world and then it will not call anything let's try to run this program hello world hello world hello world hello world hello world make sense what is happening over here a function is calling another function isn't that what is happening i hope you are all able to understand this so if i just put a debug pointer here and debug it let's see what is happening very simple this is nothing so message will be called okay message function will be called no problem oh sorry i have to debug it into internally so i go inside this yeah hello world message one will be called messen message one is called it will be like okay print hello world now message two will be called print hello world message three will be called message four will be called and now message four is not going to call anything now when it comes out okay so basically what i'm trying to say is in function calls one more thing you have to understand is when a function is called so when this message4 function has phoenix finished executing it will come out of this line so this is now finished executing it will come out when this message for function is finished executing it will come out of the line from where it from where it was called that is something we've been doing so far in the previous lectures also okay message four was called ok it's calling message 4 printing hello world nothing new to be done function over it will come out of here when it comes out of here can you see that message 3 is also getting over now this message 3 was also called somewhere yeah it was called over here so when this message 3 is finished executing it will come out from here now similarly message 2 is also finished it will come out from where message 2 was called from here now message 2 is finished exit message 1 is finished executing it will come out from where it was called it was in the body of the original message so from this line it will come out message itself is finished executing so it will also come out from where it was called from here now main function has finished executing so program will be over finished very simple stuff don't worry about what is recursion try to understand what we are achieving over here okay let's try is to say we do something else okay let's say we do something else let's say we did say something like something like let's say we say something like a new file okay let me rename this to message i am trying to make you understand what the problem we are trying to solve and this flow of program and everything that happened i will explain in detail please stay with me this is a very good example the next one that we are doing very good example numbers example very great example please look at it question is print numbers write a function that takes in a number and prints it print first five numbers that is one two three four five that is what you want to print okay let me create a function that takes a number i can say static void print one it takes a number n and it's just going to say print and okay and here i can just say print one question is print numbers from one to five okay you can call this function again and again you can say okay like this you can call it again and again you can put 2 over here 3 over here 4 over here and 5 over here that is not what we want to do we only want to call this function once and the output it should give us the first 5 numbers we cannot also add new print statements over here we cannot add new print statements similarly what we can do is create new functions this is a very great example please bear with me create new functions okay so print one print two print three print four and print five so here what is going to happen it will say print one n is passed as one one will be over here it will print one after that it is going to call print two okay let's call print two what do we want to print two no problem so it will call print two it will go into the print 2 function and it will print 2 because 2 is passed in the parameter now after this we want to print 3 no problem i will call print 3 and i will pass 3 over here it will call print 3 print 3 is like this 3 will be passed over here it will print three now it will call print four it will pass four over here it is going to call print four print four will be called a print four is printing uh four then it's going to call print five print five is called it will pass 5 over here and then it will is going to be like okay you're printing 5 no problem print 5 print 5 is not going to call anything print 5 is not going to call anything let's try to run this one two three four five one two three four five what is happening over here what is happening over here the most important point i want you to notice right now the most important point i want you to listen very carefully what recursion is this is a function calling another function point number one point number two all these functions have one thing in common and what is that the body and the definition of these functions is same you can see taking one parameter and doing the same thing taking one parameter doing the same thing can you all see this all the function like have same bodies and everything exactly doing the same thing just the name is different just the name is different exactly it's doing the same thing so can we not do it something like this instead of creating another new function can i not just call something like you know if i'm saying print one or first uh i don't want you to get confused so i'll try my best to explain it in a simple way as possible that's why i'm not rushing into the explanation let me first explain to you how this thing is working internally okay uh then we will go into recursion for now let's see how this call stack is working internally okay let's see that so let's see how this call stack is working internally so here we can see first first it's calling which function main function main function is the first function that call that gets called so in java we learned about stack memory already okay all the function calls that happen in a programming language they go into the stack memory okay this is a very important section please this this particular point that i'm mentioning right now it is basically in short explaining how function calls work internally okay so in this line in this section i will explain how function calls work internally how function values are returned and from where the function values are returned how the stack memory gets cleared how the stack memory is filled on top of like all the function calls and everything everything i'll explain in this section very important okay so let's pay attention to this first main is called no problem no problem main is called so i will have my stack memory over here i am not talking about recursion i am talking about normal stuff main function is called it will be called over here okay so basically how function calls work in languages we are learning about that how function calls work in languages forget about recursion we are not talking about recursion we are talking about how function calls work in languages when a function is called how does it work internally that is what we are looking at main function is called okay main function is called points i am going to write over here those are important points very very important points okay point number one while the function is not finished executing while the function is not finished executing it will remain in stack which is the first function that is called in programming language in java or c plus which one main function so can we say that main function is the first function that will go in the stack and the last function that will come out of the stack when a function is staying inside the stack it basically means that function call is currently going on okay what is happening over here main function is called main function itself calls the print one function so print one function is called and main function is currently in progress it's saying hey brother print one please give me the answer or whatever task that i have asked you to do after print one function is finished executing i will end but i will currently rest in the stack memory and you do your work print one is going to be like okay i am going to do my work so print one is going to get called now print one is called hence print valid will also go in the stack memory now print one will go over here print one function will go over here and it is going to have a primitive primitives by the way are also stored in the stack memory we have discussed it already in data types so it will have primary a print memory uh stack memory in the stack memory only there will be a variable primitive one because you have passed that now print function is called what does print function do when it is called print function actually what does it do see it's actually printing whatever was passed to it so it's going to print one okay no problem no problem it's going to let me start to debug it okay let's debug it and then run one by one it's very important don't skip this so let's debug it so we were saying um print one and we are inside it you might be able to see some uh you know stacks here as well yeah you can see stack over here as well so now main function is in the stack below then you have print one it is actually going to print one that's true print one function is called it's going to print one okay no problem so one is printed in the console you can see one is printed in the console then it's calling print two print one is going to be like hey i am not done yet print one is going to say hey print two main actually wants us to you know print all the numbers from one two three four five i have printed one print two can you please print two and ask the other functions to print the rest of the numbers print two is going to be like okay hold on you you you stay in the stack i will take care of the rest of the numbers now print two is inside the stack can you see print two is now on top of stack let's see what is happening now print 2 is in the stack print 2 function what is print 2 doing when print 2 is called print 2 is actually printing 2 that's ok it is printing 2 pen 2 has printed two now print two is like hey print three i have not finished executing print number one and print number two and the main sorry print number one and the main function they are actually waiting on me they are actually waiting on me to print two three and four and five i have printed two print number three can you please make sure that numbers three four and five are also printed while you are doing that i will relax in the memory in the start memory print three is going to be like okay you relax in the stack memory i will take care of the numbers three four and five no problem okay as you can see in the console one and two are printed up print two is going to call print three function print the function is called it will go inside the stack memory every function that is in the stack memory that is currently that is ongoing currently that is ongoing so print three is going to be like okay print two hold on i am going to print three okay it's going to print three it printed three now it's going to call print four it's going to say hit print four function uh can you please uh print uh four and five numbers for me because uh i have been requested you know print two and print one and the main function they are currently waiting in the stack memory you know in hindi if i say this is not important for whale nikon you know gold movie so that is what is happening over here so it's asking print 4 hey print 4 can you please print the rest of the numbers we have all the v all the functions that are in the stack memory we have printed one two and three now it's your role to print four and five till then we will relax and wait in the stack memory you do your work it's going to be like okay let me let me bring my whiteboard so print 3 is now over here waiting print 3 is waiting and it has called print 4 with parameter 4 print 4 is going to do what let's see it's obviously going to print 4 then it's going to call print 5 4 is printed print four is obviously in the stack memory over here you can see and saying hey print five we have printed you know uh number one two three and four and all of the you know function calls like print one print two print three and myself print four and main also we are resting in the stack memory waiting for you to print the last number so print five is going to be like okay i'll print the last number no problem and it's also going to say do you want me to call print six or something else or am i the last number print four is going to be like hey you are the last number don't need to call anyone else okay 0.5 is going to be like ok now print 5 will be called it will go in the stack memory because any function that is currently running will go in the stack memory print 5 is in the stack memory it will print five let's try to see print five will now in the stack memory it will print five so one two three four five has been printed output okay now basically what is happening is it's going to be like okay my work is done.5 is going to be like i don't need to call anyone else my work is done so my function call will be over point to be noted point to be noted i'm going to double clap so you get my attention point to be noted very important point when a function this is not recursion not for recursion for every function when a function finishes executing it is removed from the stack it is removed from stack and the flow of program is restored to where that function was called this is very simple stuff because we have covered functions already you know we were returning values storing it in a variable that is exactly what was happening int a is equal to sum of b plus c so that sum function it was calling the sum function and that sum function was returning the value and where it was written in the value from where it was called please it's very simple i am clapping again this return value this point that uh the flow of program this point the flow of program is restored to where the function was called this is the most simple stuff don't confuse in this this is something we were doing for so long okay we we all have done this written values of functions and everything we have all done this thing okay so this is the second point so print five has finished executing print five has finished executing so it will the program flow this blue line that you see is actually the program flow where will the flow be restored right now where will our flow bill will be right now where will be our program executing right now which line will be executing right now from where this function was called because this function has finished executing it will come out from where it was called for where was it called in line number 28 it was called so it will come out over here and you can also see print 5 will be removed from this stack is it removed from the stack yes it is and it has now come over here outside print 5 is going to finish executing it's going to say to print 4 hey print 4 i am finished executing and i don't see that you are doing anything else so you can also finish executing that is what is happening over here print 5 finished executing it will come out of the stack it will come out of the stack print 4 is going to be like then um print 4 is going to be like ok print 5 did its work nothing new needs to be done i will also finish executing and i will also leave the stack it's going to be like okay nothing needs to be done and where where the program flow is going to go to where it was called so in simple language when you're let's say when your mom asks you to get some groceries so your mom is calling you you are a function you are a grocery function your mom is calling you hey grocery function canal go get some groceries i'm gonna be like okay so while i am getting groceries i am doing the work so i am actually in the function call okay and when i come back home i'm gonna be like okay mom here are the groceries and my job is done i will now be removed from the stack and my flow i will be passing it to another function which is my mom mom function now mom function can do anything with it similarly that is what is happening over here print four you can see now directly you can see all the lines have executed of print four nothing needs to be done function call over it will come out of the loop and it's gonna be like hey who called me print four is going to be like print three called you okay give the flow of the program all the you know life and everything to print three print three i am done with my work now rest is up to you so it will now leave the stack left the stack now the program flow is with print three it will leave the stack this will go out of the stack leave the stack print three is going to do the same thing print three is going to be like okay i am leaving print three as well i don't need to do it spring three will also leave the stack it will give the program flow to pin 2 it will also come out from where it was executed from here it was executed hence it came out print 2 is going to be like okay i am also done it will also be removed from the stack print one is going to be like okay i am also done it's going to be removed from the stack and go where it was called print one is going to be like okay i am also done from the stack now main function will be there main function will be like okay i am also done in the stack main function is the last function that is removed from the stack and then the program will be over program over output one two three four five remove from the stack remove from the stack remove from the stack remove from the stack this is how function calls work while a function call is not finished executing it will stay in the stack memory okay cool let's talk about recursion now what is recursion so recursion is basically um can you see that i am making repetitions i am making repetitions so if i copy this file number example recursion okay so basically what we are doing is if i see what we are doing i am creating all of these functions that you can see that i am creating they have the same body taking a number printing a number calling another function taking a number printing a number calling another function let's say the question was print one lakh numbers will you copy paste this one lakh times point to be noted over here is if all these functions have the same body and are doing the same things then why are you creating these functions again and again a simple solution for this is call the function itself so instead of having all these remove all these functions remove all these functions because they had the same body i'm just going to rename this as print only okay instead of calling another function i'm going to call this function only print itself okay so let's notice the stack first thing that was happening is it was calling number one ok and that was calling number 2 ok so if i passed n over here it should be calling n plus 1 so basically you can see print 1 the parameter 1 was calling 2 or i can just show you from here also no problem this is exactly the same thing we are doing so you can see the parameter with 1 was calling 2 parameter with 2 was calling 3 parameter with 4 was calling 3 which was calling 4 4 was calling 5 5 was not calling anything so whatever the parameter will be what was it calling what was it calling if the parameter is n isn't it calling n plus 1 so this is print 3 here 3 is passed isn't it calling 4 this is print 4 4 is passed over here isn't it calling 5 so if i write a generalized answer and n is passed over here will it not be calling n plus 1 does that make sense and one more thing i want to share is when the value of n is 5 is it calling anything this is a special case because the body here changes function body here changes because it is not calling anything all of these function bodies are same print call print call print call but here only print is there so when the value of n is equal to 5 it is not calling anything else so i can write a check over here if n is equal to equal to 5 don't call anything what can i do to break this function from here i can say return simple return don't call anything don't execute this thing let's try to run and what see what happens i will explain this also in detail don't worry okay i know you might be confused please give me five minutes ten minutes i will explain this in detail okay don't go anywhere let's run this for see the output one two three four i forgot to print i can print it i can print five as well one two three four five isn't this exactly the same that we were getting previously and isn't the body of the function also the same print call print call what is happening over here what is recursion what do we mean by recursion recursion means a function that calls itself that is recursion what is recursion function that calls itself function that calls itself remove this condition i know you might be confused from this so let's remove it let's remove it and run this let's see what will happen it's not stopping it gave me an error gave me an error after printing 19 000 numbers okay few things what is this what is this particular call the what is this check why are we adding this check that is the doubt number one that people will get how the flow of the program is working in recursion doubt number two what actually is recursion why we are using a doubt number three what was that error that we get doubt number four let's resolve all these doubts okay so far we have only done some simple things okay um because as you can see if i have removed the complex thing that you may have problem with so let's remove that for now you can see this this exactly the same this is just more generalized answer internally it will be doing the same thing let's try to see how this is working internally put a deeper pointer over here start debugging it okay so in the stack now i have main it is going to call print one no problem i'm gonna create a you know uh the drawing for this as well no problem so recursive call recursive function or the same okay so don't worry about the check condition i made okay i if that was confusing to you forget about it forget about it we will cover it in detail right now so here it's saying print one okay first of all main function will go in stack main is going to call print with the argument one print is going to print it it's going to print one no problem in that it's going to print one and then it's going to be like okay you have printed one now print two now print one plus one which is two so it's going to call the same function with argument two okay so it has called the same function with argument so first is going to print one at first it's going to print one like this then it's going to call the same function with argument 2 as you can see it will go in the stack now over here you can see with argument 2 here we have this one at line number 12 over here same print function is in the stack but this time even though it's the same function it's now with argument two for example it's going to say okay i will print one but i will call myself again this time with argument two print two is going to do the same thing print two is going to be like okay i am going to print two please notice this ends value is equal to two so here also it will be two because that is what force passed so i'm like okay i'm going to call two plus one three no problem print it and call two plus one three no problem it will be waiting in the stack it is going to print two then it's going to call print three similarly this is going to print three and it's going to call print four this is going to print 4 it's going to call print 5 this is going to call print 5 this is going to call print 6 is going to print 6 and so on and so forth it will keep going it will keep going it will keep going is there a particular stop over here in this program right now it will keep going you can see keep going 7 8 9 10 11 12 13 14 15 16 21 23 25 26 27 28 29 it will keep going like this indefinitely it will keep going what is happening over here you are not stopping this call anywhere right this function is calling itself but you're not stopping anywhere so in order to do that you need something called a base condition what do you need base condition base condition in recursion it is a condition where our recursion will stop making new calls this is a simple if condition okay it's a simple if condition so i can put it over here that okay if the value of n is 5 if n is equal to 5 just print 5 and don't do anything else just return from here only don't execute the future lines just return this function from here only return this function from here only that is what will happen so basically over here you can say after printing five i just erase this after printing five it's going to be like like i have printed five now what is going to happen let's try to debug it again first main will go in the stack okay then one two three four and five this is equal to five it's going to print five and it is not going to call another 6 it's just going to return from here only and where is function return to from where it was called so it will be emptied from here and it is now going to return to let's see where it will return to n is equal to 4 that function call that's true cool that's what happened over here so it will it will be out from here then it will be out from here then this out this out this out this out program over exactly the same thing we were doing previously what was the error that we were getting so the few questions that we had in mind were what is this condition this is base condition i explained this base condition okay and this is something i've already explained this is the recursive call recurs save call and basically one more thing i wanted to explain was each call is a separate you know you can treat it as a separate function call in the stack okay so basically if you if i just write it over here if you are calling a function again and again you can treat it as a separate call in the stack it's not like it's the same memory or whatever no function is called again it will be there in the memory as a separate function like we were doing in this example okay so basically oh by the way i um did not show it over here no problem so this thing is covered so this is the only thing that i wrote that uh if a function is getting called again and again and again even though in this demo you can see it's the same function that is being called again and again but every function call is taking the memory please notice as many times as you call the function it will take memory separately if this function is called for argument 1 it will take memory separately separate memory for this separate memory for this separate memory for this separate memory for this so for example if there was no base condition in the previous example we saw that we were getting error when i remove the base condition no base condition means what function calls will keep happening function calls will keep happening stack will be keep getting filled stack will be filled again and again and we know that every call takes memory we know that every call of function even though it's the same function different funder function does not matter if you're calling a function more than one times simultaneously that's simultaneously right this is called first now it's in the memory waiting for the another call of the same function to give the answer it's gonna be like okay argument two please give me the answer till that i'm waiting in stack argument two is going to be like hey argument three call please give the answer i'm waiting so again and again every function call will take some memory so if there is no base condition it will keep going keep going keep going and one time will come where memory exceeds memory of computer memory of computer will exceed the limit this is going to give stack overflow error this is the name of the website also the name of the website stack overflow comes from this error stack overflow error i hope you are able to understand the stack overflow error i hope you are able to understand what base condition is i hope you are able to understand why we need base condition i hope you are able to understand every function call is going to have its separate memory i hope you are able to understand this particular example with previous example i hope you are able to understand how these pieces are these function individual cards are stored in the memory are actually waiting for other function calls to resolve i hope you are able to understand how these function calls are getting out of the stack okay i hope you're able to understand how this flow of program is working i hope you were also able to understand the basic the debugging that we did that is recursion in store for everyone recursion made simple oh that was a lot was i recording yes thank god all right oftentimes it happens i explained something in very detail and i realized i haven't stopped that play uh you know started recording but anyway all right base condition body recursive calls okay so we did the introduction of recursion we did the flow of recursion program with the stacks and now let's look into uh let's answer one more simple question why recursion okay that's also an important point why recursion let's write that down as well and then one more thing i have to explain to you all is how to actually study recursion right how to actually study about recursion that is also something that is we have to cover in this video itself how to actually study recursion so first why recursion why do we need recursion why recursion what is recursion we already covered uh recursion is actually function calling itself that is what is recursion okay so why recursion why do we need recursion um simple answer it helps us in solving bigger complex problems in a simple way that is why we use recursion it helps us in solving bigger and complex problems in a simpler way so when you're given a problem relative to dynamic programming or whatever or you're given some you know other problems like we have star of annoy or whatever with recursion these problems can be solved very simply so to answer your question why do we do recursion we do recursion because it helps us in solving problems easily it helps in solving complex problems easily you can convert recursion solutions you can convert the recursion solutions into iteration and vice versa what is iteration iteration basically means not using any function calls iteration means loops so you can create you can convert any recursion recursion function into iteration that is the idea first solve it using recursion first solve complex problems using recursion then convert it into iteration to get a more optimized answer because directly solving into iteration is difficult that is why we use recursion okay so that is also a great point and so iteration basically means loops and for loops by the way this is something we will be doing also so we will be doing it uh we will be learning how you can convert to iteration to recursion and recursion to iteration uh we will be doing it in uh when we when we are done with stacks and queues okay because we are using the stack memory so stack data structure we have not learnt yet so we will be learning about it in the future and in dynamic programming we will actually be solving questions using recursion then we will be solving it with iteration that in that in those questions you will see how to convert from one to another and another another okay so we will do this in detail okay when to use recursion um by the way recursion actually takes a space as well space complexity this is very common sense because each function call is taking some memory hence the space complexity is not constant not constant for printing one to n numbers it took a complex space complexity of n whereas on the other hand if you just ran a simple loop it will not take any extra space it will just print all the numbers in constant complexity if you want to print thousand numbers using recursion thousand function calls will go in the stack space complexity of n so by the way in the next video itself we will be learning about space and time complexity okay in detail for recursion as well so if you want to learn about space and time complexity in recursion we are not skipping that that is going to be covered very in detail you will not find that anywhere on youtube that much detail okay that is exactly the next video check out the link in the description of the playlist and watch the next video of space and time complexity i'll upload it in shortly and if you're watching in the future it's already uploaded space complexity is not constant because of calls because of recursive calls okay so very simple we use it because it's easy to solve problems then we can convert it into iteration space complexity is not constant because of the recursion calls did i miss anything else in this uh not really that's it it helps us in breaking down bigger problems into smaller problems it helps us in breaking down bigger problems in smaller problems i think this is the same point as point number one bigger problems into smaller problems let's we will also do this in action okay in the future sessions we will be doing a lot of question on this that was about why recursion so one thing i want to share is uh very important um in order to solve recursive problems when you're solving it on like pen and paper or whatever because these numbers like print one to n or whatever they were like very simple problems so since these are recursion calls these are function calls linked to one another i can visualize this as well visualizing recursion very important point very very very very important so let's say the previous example that we took of numbers from 1 to n right printing numbers from 1 to n calling the main function then it was calling print 1.2.3.4 and pin 5 okay we call the main function this called print function with 1 this called print function with 2 this called print same function with argument 3 this called print for argument 4 this called print for argument 5 this does not call anything it just said okay i'm just going to return it so it's going to return it from here it's going to pass the value from here to here like the fast the function call so something we have discussed already how the function calls are passed this is also going to be like okay i'm also done i am also done i am also done oops i am also done then program over and this is basically program start so what is this thing called this is called recursion tree it looks like a tree a branch or whatever this is known as recursion tree okay this is known as recursive tree that is it so we are going to utilize this particular concept to solve very very complex problems to visualize the problems okay that is the use of recursive tree this is going to come in importance when i actually tell you how to learn about recursion how to get the how to be good at recursion for this it is going to play a crucial role it's going to play a very crucial role all right let's move forward to a question let's take a question question is basically fibonacci numbers fibonacci numbers okay so question is find nth fibonacci number that's the question you know the fibonacci numbers are what zero one these are the first two the zeroth fibonacci number first fibonacci number second fibonacci number is going to be what some of the previous two which is zero plus one is one okay then third fibonacci number is going to be equal to what some of the previous two one plus one is two fourth fibonacci number is what two plus one three fifth fibonacci number is what three plus two five sixth fibonacci number is what five plus three eight seventh fibonacci number is what 8 plus 5 13 and so on and so forth okay that is what we want to solve using recursion so whenever you're given a question like this when you will like find the nth number okay or something like this always you know you can try to see you can try to break it down into recursion so how do you identify whether a problem can be solved in recursion or not that is another important point point number one it comes via practice point number two try to see if there's a smaller version of the problem that you can solve that is how you actually figure out how you can solve a problem using recursion you may ask me kunal how did you know that you can solve fibonacci numbers with recursion how did you know that it's very simple check if you can break it down into smaller problems so if you want to find the nth fibonacci number how can i find that what is the nth fibonacci number going to be so i can say fibonacci number nth is going to be equal to what is it not going to be n minus first fibonacci number plus n minus second fibonacci number if i write it down clearly nth fibonacci number is going to be n minus first fibonacci number plus n minus second fibonacci number this we got from common sense this we got from like very very common sense because this is exactly what we have been doing so far isn't this basically saying that now this entire problem is divided into two smaller problems here hence you can apply recurs one bigger problem is divided into two smaller problems this problem itself can be broken down into two smaller problems i can say fibo of n minus 1 is going to be equal to favor of n minus 2 plus fibo of n minus 3 it will keep going on so if i try to build a recursive tree for this let's say you're trying to find the fibonacci number for um you know let's say you're trying to find the fifth fibonacci number so it's gonna be like okay fifth fibonacci number is going to be equal to what it's going to be equal to 5 minus first fibonacci number which is 4 and fibonacci number 3 plus answer of this plus answer of this this is going to be like so when we call fibonacci number of five it's going to be like hey fibonacci number four give me the answer and hey fibonacci number of three please give me the answer fibonacci number is going to be like 4 is going to be like hey wait a minute let me get the answer from my function calls this is itself going to call the two things fibonacci number of three plus fibonacci number of two this is itself going to call fibonacci number of two and fibonacci number of one this is itself going to call fibonacci number of one this is going to call fibonacci number of zero this is going to call same fibonacci number of one and fibonacci number of zero actually this is looking a bit messy let me clean it up and let me write it for a smaller number so let's say i want to figure out fibonacci number of 4 it's basically going to say it's fibonacci number of 3 plus fibonacci number of 2 this is going to be like okay i am going to call fibonacci number of 2 plus fibonacci number of 1 this is going to call fibonacci number of 1 and fibonacci number of 0 this is going to call fibonacci number of 1 fibonacci number of 0 okay that is how you identify whether a solution can be solved via recursion or not you try to see if a smaller problem if you can break it down into smaller problems that is how you check it okay that's the first point break it down into smaller problems this thing is actually called this is known as recurrence relation when you write the recursion in a formula it is called recurrence relation okay this is known as recurrence relation all right because you're saying nth fibonacci number is n minus first plus n minus 2 you can even break this down into smaller ones as well yeah i broke it down into smaller one at the end it will stop somewhere the base condition is represented by answers we already have for example in this case we know that zeroth fibonacci number is zero first fibonacci number is first this is base condition okay very very very very important how to figure out base condition we also covered that simple answer what it so two so few doubts you may have like how did you find it was a recursive solution i saw what uh you know um i saw that uh i've written it down over here uh i saw that uh what um you know with the if i can break it down into smaller problems okay that was the first point and the second point is how did you figure out what was the base condition base condition is going to be the answers that are already provided to you that's the base condition very simple stuff okay and what is this formula called this formula is actually known as a recurrence relation any recursive solution you can convert it into a formula okay for binary sorry for uh minuses we'll be doing later on but for fibonacci numbers this is the formula this is the recurrence relation okay this is the tree recursive tree for fibonacci number okay let's try to code this solution okay so for every problem i am repeating it again so you don't get confused and i will repeat it in the end as well but for now i'm saying what all things i did so that you don't say hey how did you know about it point number one how to find if a problem can be solved with recursion try to break it down into smaller problems okay if you can break it down into smaller problems you can apply recursion on it this particular formula that you can create for such problems it is known as a recurrence relation in order to make your concept stronger i will also share let's see how you can solve binary search because in binary search we also break the problem down into smaller problems we have we divide the array in half that is what we do so we will also cover that in this lecture so this is known as a recurrence relation okay it is known as a recurrence relation the second step is try to figure out the recursive tree try to figure out the recursive tree this is the main function call it's calling these two function calls okay then when this is finished executing it will save its value and when this is finished executing it will save its value it will add these two values and return it similarly the answer of this is going to be when this is finished executing when this is finished executing it will return the sum of this and basically add it and you know store it over here basically we will dry run this entire function okay we will dry run this entirely so don't worry stay with me for now let's just try to code this and then we will dry run it entirely and see every step in action okay let's do it so here it's just saying that if i create fibonacci public static void main so basically here you can see it's actually returning an integer so this function call is returning an integer this function call you can see it's returning an integer this is returning an integer so i can just say something like this pibo it's taking an integer and what is the nth fibonacci number going to be nh fibonacci number is going to be fibonacci number of n minus 1 plus fibonacci number of n minus 2 all i need to put is a base condition base condition we also covered if in the question few answers are already given that is a base condition in this case we are given if the number if the fibo of if you are calling fibo of one just return one and if you are calling fibo of zero just return zero so if n is less than 2 return n basically if n is 0 it will return 0 if n is 1 it will return 1 that is it let's try to print the fourth fibonacci number it should give me 3 but let's try to print the 6th fibonacci number it should give me eight we will also see how this is working internally don't worry oops i accidentally printed six i wanted to print fibonacci number of six should give me eight right giving me it if i'm saying print the seventh fibonacci number it should give me 13. very cool stuff how is this working internally what is happening and all these things and how is this thing returning and what is it returning why are you putting into over here kunal we have only studied till void how are you putting into over here let's try to see how this is working internally let's put a diva pointer here let's try to debug it for something smaller let's say if i try to debug it for four let's try to debug it for four let's try to debug it okay so here i have my recursion tree that is how it will be running so first it's going to call main then it's going to call f4 i'm also going to create my stack memory over here my stack memory main will go over here okay and then f of 4 will go over here fibo of 4 paper 4 is going to go over here and let's say here what is happening let's go internally nope not in println but over here one second if i just go inside like debug i don't want to go inside print ln i want to go inside um fibo of 4. so i can just save it as an answer somewhere let's say i can say int answer is equal to this okay and i can put a debug pointer over here and i can just debug it go inside this it will go inside this it's going to be like for n is equal to 4 it's going to be like is n is less than 2 no it's not it's going to be like okay then do this thing if you want the nh fibonacci number f of 4 is going to be like hey f of 3 i need your value and f of 2 i'm also i also need your value in the previous example we were only calling one function call from one function call now for every function call we are actually calling two function calls in recursion so f of 4 is going to be like hey i am going to sit in the stack f of 3 and f 2 please give me the answer so it's first going to call f of 3 f 3 is getting called let's see so here you can see first f of 3 will be called this is a very important point f of 3 will be called first okay now it goes inside f of 3 n is equal to 3 is going to be like it's going to be like hey let me call f of 2 and f of 1 so for this first f of 2 will be called so this is the flow first it called f of 3 then it called f of 2. okay f of 2 is going to stay over here so f of 3 will stay over here then f of 2 will stay over here f 2 is going to be like ok let me call f 1 it will call f of 1 f 1 will stay over here let's see how this is working internally so now f of one will be called this particular function will be called this first one f of one so it's gonna be like is one less than two yes it is it's just going to return one okay it's just going to return one and it will come out from there from where it was called so it will come out from here let's see in the tree so it will say okay i will just return one and it's going to come out from here so now if it's going to come out from here the right hand side will be called so if it's coming out from here notice over here if it's coming out from here next point in the flow of execution of the program is the function call f of 2 that is correct you're calling it for f of 2 right now for f of 2 it will call the right hand side that's correct it will now call the right hand side for 2 minus 2 which is 0. that is true it's calling for it's calling for 0 that is true so it will be like okay let me go over here f of 0 is going to return 0 that is also true if i run this you can see f of 0 is going to return 0 it will go into f of 0 it will return 0 it will again come out of f and f of 2 so you can see it came out of f of 2 now both the calls are finished executing it will add the answer of both of these calls that it has gotten answer number 1 it has gotten from here answer number 2 it has gotten from here 1 plus 0 is going to give 1 so the answer of the entire function call 2 is going to be 1 plus 0 1 answer of this entire thing is going to be equal to 1 f of 2 is going to be equal to 1 second fibonacci number is going to be equal to 1 let's see okay now it's outside for n is equal to 3 so this itself is going to have a value of 1 and it is now going to get out from where it was called it was called from where it was called from f of 3 that is true for f of 3 it was called in f of 3 here it was called f of 3 minus 1 2 so here it will come out from here now it will call f n minus three which is one one is called it will return one both of these are finished executing f of three is both of the function calls of finish executing this has finished executing and this other one has finished executing so this has finished executing and this has finished executing as well the answer for this is 1 so f of 3 is going to be 1 plus 1 which is 2 answer of this is 2 it will now return from where it was called which was the left hand side of ff4 it will now be returned from f of 4 you can see now its function call 4 it will be returned from here now it will call 4 minus 2 2 4 minus 2 2 that is also true so now it will be returned from here it will return 2 from here it will call 2 2 is going to call 1 similarly like it happened on this this is going to return 1 then it's going to call this it's going to return 0 it will return 0 plus 1 1 then it will return from here it will return one from here then it will be like okay f of 4 all that both are finished executing before you know both the both the ones are finished executing you can see it will call f of 2 f of 2 is going to call 2 1 and 0 and that is finished executing the answer for this is going to be 2 plus 1 which is equal to 3 now this will be outside it will be like now called back to main back to main it will print three answer so the answer it will store will be equal to three okay it will go back to main it will be value to value 1 back to main this value will be equal to 3 answer is equal to 3 that's it okay so that is how it's working internally so here you had like you know first you had function called main then you had function call 4 then you had function call 3 and 2 then 1 then 1 is actually finished executing it will be removed and f of 0 will go over here ok and if zero is finished executing it will be removed f of 2 will be removed then f of 1 will go over here again f of 1 will be removed then f of three will be removed then it will go over here then f of two will be executed f of two will come over here then f of two is going to call f of one f of one will be removed it will call f of zero f of zero will be removed f of two will be removed and then f f4 will be removed then main will be removed that's how it's working internally so doubts that you can have over here i'm gonna you know note over here please note this is very simple try to run it on pen and paper try to see how these function calls are executing best way to do it is use the debug pointer okay you will you know you might face issues but that is what i want you to do try it out yourself build this tree yourself and build these arrows yourself see the flow of the program okay let me clear all your confusions in just like this one simple step there's a few things i want to mention and then i will clear your confusions so one thing i want to share is that in this example you can say that uh you know um this f of 2 was actually waiting for f 1 and f of 0. can you see that this f of 4 was actually waiting for f of 3 and f of 2. can you see that it will be like okay f 3 give me the answer f of 2 will give me the answer as you can see over here here you can see f for f of 4 it will be like f of 3 will give me the answer f of 2 will give me the answer then i will add these two numbers whatever answer i get and that will be my overall answer how f 3 is getting the answer that is up to f of 3 how f 2 is getting the answer that is up to f of 2 can you see this on the other hand this was not concerned with it in this particular example print five just print one is just going to print one and that's it it's like okay i have done my part now i'm handing it over to print one plus one two is it really doing anything with this thing this is the last statement that is executed point to be noted this is the last statement that is executed in this function in this recursion function over here that is not the case this is not the last statement in this function call basically in this function call this is not the last statement because once this gives the answer this gives the answer this is actually the last statement but over here this is the last statement in this function call so when you have the last statement in the function call it is known as tail recursion this is called tail recursion this is the last function call this is not tail recursion because for this function call let's say function call of fibo of 4 it's actually saying call this function call this function then do the addition of it and return it so this extra step of addition and returning that is not tail recursion in this this is tail recursion this is the last function called it's like i have printed what i wanted to print now it's up to you i don't care what you do do whatever you want that is known as tail recursion okay and in fibonacci numbers or whatever example that i am taking over here steps to understand a problem okay how to understand and approach a problem please follow these steps and you will find recursion very easy very very very very important identify if you can break down problem into smaller problems like we did in fibonacci number point number two form the recurrence relation this is what i'm telling you right now how to understand a problem in fibonacci in recurrence okay in in recursion write the recurrence relation if needed point number three draw the recursive tree please follow these points very carefully no doubt will come to you i assure you you will understand every question okay point number four is about the tree about the tree these are points you need to follow when learning about the tree in this you will have sub points see the flow of functions how they are getting in stack identify and focus on left tree calls and right tree calls for example in the debugging session we also saw the question to you is is this f 3 going to execute first or this f of 2 going to execute first f of three is going to execute first because that was written in the formula first that was written in the formula first so of n is equal to r fibo of n minus one plus v of n minus two so until and unless fibo of n minus one has not finished executing how can you execute fibo of n minus 2 this is this point identify the flow of left tree and write recalls so first this will be called the the i'm going to list the you know i'm going to list the order in which this is called first this is called second this is called third this is called fourth this is called fifth this is called then it will go back sixth this is called go back seventh this is called it will call its left tree eighth this is called it will go back ninth this is called that's it zeroth main function is called first this is called second third fourth removed five six and all these things are you able to understand now very simple stuff okay so try to see how these things are getting in stack this is not going to be called until and unless this entire left until unless this entire tree is finished executing none of the right tree will be called similarly until and unless this entire this entire tree is finished executing this will not be called okay i hope you are able to understand this thing this is something i also explained in detail in the debugging session i explained that okay so this entire formula that we have written please understand this very carefully this is the most important point how is this thing working internally before when we are calling fibo of 3 and fibo of 2 this will not even execute till fib of 3 has given me the answer that is why this is containing all the bigger numbers and this is containing all the smaller numbers very simple stuff so how can we understand this kunal you can understand this why identifying this and the steps to follow in this is draw the tree and pointers again and again using pen and paper use a debugger to see how the flow to see the flow on the pen and paper if you don't draw it again and again you will not understand before asking me the question before asking me any doubt ask yourself have i followed these steps if you have not no one can explain recursion to you no one can explain recursion to you if you are not drawing the tree on pen and paper no one can explain in 100 years you will not understand the cursing if you are not using a pen and paper by heart follow these points when you are starting out with recursion by heart fifth point also about the tree or something see how the values are returned at each step here you can see when this is finished executing and this is finished executing it will return one plus zero one this entire will be one okay so this is also very common see where the function call will come out of in this example it was coming out of where it was coming out from here and here then it was giving the entire value and then coming out of from where it was called previously okay no words can explain this why am i not making why am i not explaining this again and again because no one in the world can no one can explain it until unless you draw it on a pen and paper so i have explained to you in detail all the things we did entire debugging i also write the numbers and pointers and everything try to debug it on your own okay so try to see how the values are written at each step and how the function call will come out okay and in the end you will come out of the main function okay see what values are returns and see how the values and what type of values so i knew that i was returning integer like is it an integer is it a string etc what are you returning that is also what you need to see that's it with these five steps you can understand any recursive problem for every question we do if you're a beginner follow these five steps oh point number six one more thing subscribe subscribe to the channel and like comment share on socials so point number six this is actually very very important actually there's one more point which is do a lot of questions but that's self-explanatory all right for the fibonacci number pause this video right now try to do all these things on your own and it will be able to understand you will be able to understand okay so this is known as recurrence relations let's look into another problem which is known as binary research so let's see how we have already done binary search let's see how we can solve binary search using recursion because in binary search it's very common since we are dividing the problem into half so a problem is dividing into sub problems definitely we can apply binary search let's try to see now this is another important point as i am clapping pay attention very important point the place so there are two key areas of focus when you are trying to understand or when starting out with recursion or solving recursion programs and you want to have a strong foundation in recursion two key areas one of those we have already talked about which is the how the functions are getting called and the tree and the you know how this function will be called and all these arrows and everything that we did function call stack and everything that was the first point second place where everyone who just starts out with recursion faces doubt what is that second point variables variables and data types and all these things in this example let me bring on the screen in the fibonacci example you can see there are three types of variables one variable is actually in the argument okay one is the one that is being returned and one is that something you may be having in the body which variable type to to use in which place and what to return if someone knows this they know entire recursion these three variable points are very very important that's why i'm going to write it down and explain in a example let's explain this is an example how to figure out what to pass what to create over here how to understand that how do we understand that what to return let's see very important point please note carefully also make notes of this if you want so working with variables and recursion very very very important point this is very very very very very very important because without this you will not get the feeling so variables the three types in the arguments you can have return type and in the body of the function okay cool let's take a question related to this and then it will be clear binary search with recursion so what is binary search you're given an array like this size n it will be like okay let's compare the middle element with the target element does it exist in the left hand side or right and right it says exist on the right hand side then we will do it like this n by two so on and so forth at every step it's doing two things comparing which is just a single step so it takes constant amount of time you just need to check whether a number is greater than equal to or less than the number the middle number but the target is less than equal to or greater than it's well just one single step hence it's taking constant time okay for example if you don't know about time complexity we've already covered it in binary search lecture so please watch that okay so this comparison actually takes constant time what do i mean by this is let's say the array is of size one lakh or area is the size one million or areas of the size 100 checking where the mid whether the middle element is greater than equal to or less than the target element the time for that is going to be similar it does not depend on the size of the array that is why i mean constant in detail if you want to look into it check out the next video which is on time complexity second thing is we are dividing into two half so here you can see uh whenever we're trying to figure out identify whether you can break it down into smaller problems check we did this write the recurrence relation okay we can do this as well so it's saying that to find a number you know in uh if i'm taking a function for binary search size of array n if you want to search in the size of array n it's basically saying i am making a comparison in constant time okay plus now search in the array of size n by two this is the recurrence relation very simple recurrence relation this is for what this is for what this reconciliation is for the comparison that we made okay and this is what this is basically dividing array in two parts dividing in half okay that's it that is it here we are making the comparison here we are just saying okay i am making the comparison for if you basically this says in words if you want to write it if you find if you want to apply binary search on the array of size n take a constant do a step that takes constant amount of time plus search in the half of the array so it's going to be like okay let's say it exists over here then give me the answer what is over here this array itself will apply this entire thing in its own itself it will also divide it into half let's say it will do it something like this for n by four recurrence relation okay point to be noted over here is i hope you are able to understand this particular thing in words very important point is types of recurrence relations this we will go in detail later on when we will be doing space and time complexity number one is linear recurrence relation example is fibonacci number number two is divide and conquer ref current's relation this is binary search why here you can see the number n the search space is actually being divided by a factor search space is reduced by a factor reduced by a factor in this case divided by 2 in other case it can be divided by 3 divided by 4 or divided by whatever these are known as divide and conquer recurrences divide the answer into something via a factor on the other hand for fibonacci number let's take a look at that this is not getting divided this is actually being subtracted or edited added or whatever linearly it's not saying n by 2 or n minus n by 4 or whatever it's actually subtracting at it linearly it's reducing it linearly it's not dividing the entire search space these are known as linear recurrence relations so our search space is getting reduced much faster in divide and conquer recurrences is it not true dividing a number by 2 it's definitely much faster than subtracting 1 2 from it from 2 to it which is much more efficient than divide and conquer this is very very inefficient let me show you let me show you it's saying you are this recursion call it's very very inefficient let me show you this example why because the bigger number is actually getting smaller smaller in a very small small steps let's open up the fibonacci number problem let me try to run this for a small number called 50. give me the 50th fibonacci number 50 is a very small number when talking about computers let's run this not giving the answer program stuck not giving the answer not giving the answer still not getting the answer for such a small number i'm not getting the answer what is happening over here this is happening over here since this function call is like decreasing one by one one by one in the function call can you see that this f of two this tree and this tree is actually getting repeated can you see it if you are actually getting the answer of f of 2 why are you computing the answer again over here this is getting repeated repeated function calls imagine for f is equal to 50 how many repeated function calls will be there so many how can we solve this problem dynamic programming dynamic programming in short basically means if in the recursion calls two or more recursion calls are doing the same work don't compute it again and again we will learn about it in dynamic programming lectures okay don't worry about it right now that is why this is very inefficient that is why recursion plus dynamic programming is a very popular topic in interview problems memoization we will learn it later on if you check a time complexity of this particular recurrence relation what is the time complexity is going to be it's one point six one eight uh so one point six one eight some something like root five uh plus one divided by two whole raised to power n people say that the time complexity of fibonacci number of n many people many youtube channels and many thing you will find they will say that the time complexity of this thing is 2 raised to power n that is wrong it's not that it's actually the golden ratio raised to rn and one more thing i can share with you how what if i told you you can find the formula of fibonacci number and you can actually figure out the fibonacci number in just one single step like this if you can get a formula for nth number of any recurrence relation like this how cool would that be no need to apply recursion no need to apply iteration just apply just fill the value of n in that formula the formula that i'm talking about i think it's root 5 plus 1 upon 2 raised to power n how to get this formula i will teach you this in the next lecture make sure you subscribe and press the bell icon i will derive this entire formula step by step i will teach you how to figure out the time complexity and space complexity just using simple mathematics 2 raised to power n is actually saying they are saying exponential which is somewhat correct but it is not the correct answer this answer is not 2 raised to power n time complexity is not 2 raised to power n it's actually golden ratio raised to power n so if anyone says it's 2 raised to power n wrong answer it's actually golden ratio raised to power still very bad exponential complexity very bad that is why for 50 it was not giving the answer how to figure this out watch the next video which is it is going to be on space and time complexity okay so that was about divide and conquer recurrence and that was about linear recurrence the differences uh this is just the tip of the iceberg we will go into details of these when we learn about merge sort quick sort and space and time complexity we will learn about details of this so don't worry all right that is what i wanted to share so we're dividing the array in half and we're actually taking the recurrence relation so how do we actually solve this problem we're actually going to do the same thing that we did previously uh one more thing i want to share about uh this particular thing is when you're trying to solve uh try to do all these things you know try to do all these things whenever you're solving when you're doing buying research or whatever most important tip do not overthink how let's see how can you not overthink overthink only after you have solved the problem in order to understand the problem if you want to solve it then afterwards you can overthink like actually seeing how it's working internally if i create let's say binary search i can say static i need to return the index what will be the return type b inc i can say search i'm going to create i'm going to pass an array and i'm going to pass my target element now one more thing i want to tell you is these three tips that i had for you these three things so return type is very simple whatever you want to return that will be the return type no escape from that what will go in the argument and what will go in the body of the function in binary search what variables do we have figure out the variables that we have in binary search we have start end and mid which will go in the body of the function and which will go in the arguments so basically we are trying to reduce the size of the array and what all variables are the variables that determine whether the size of the size of the array is reduced start and end okay one important tip for you is whatever you put in the arguments it's going to go in the next function call it is going to go in the next function call if you're saying start is zero end is the size of the array okay start is let's say zero comma six okay start is zero end is six you put it inside the let's say you put it inside over here something like this okay let's say initially you say in start is equal to zero and then you say intent is equal to uh array.length minus 1. now when you call the recursion function array comma target you want to divide this array in half in the recursion function you have to divide this array into half in the sub recursion function very common sense because we are applying recursion how can you do that you can't do it right now and what are the two function what are the two variables that are determining what size of the array we are taking start and end how do i pass these start and end into the future future methods how do i pass it only one way to do it put it inside the argument now here you will be passing start and end accordingly okay so similarly don't over think same thing we did in binary search if start is greater than end means you have not found the answer return -1 not found the answer written -1 next thing if sorry middle element need to check the middle element in middle is equal to start plus and minus start divide by two this is the particular thing that i was talking about this type body of the function what type of variable we go in the body of the function this will be specific to that call so variables that are specific to that call that function call that will go inside the body of the function if i'm talking about middle of the element okay so if i'm saying you take an element like this continuation of variables okay let's say continuation of where to take which variables very important point two variables we are focusing on like this it will check for the middle then it will be like okay this was start and end now in the function call it will have start over here and over here then it will check for mid now in another function call this is function call this is function call this is another function call of recursion function call in case in this case start will be over here end will be over here can you see that these start and end variable start and end variable these are actually being passed in the function call these are very important that is why this will go in the argument because i will be passing these values when i call this function call in the argument i will be passing so in short if there are a few variables that you need to pass in the future function calls put it inside the argument this middle value this middle value is this really beneficial to the future calls is this middle value really beneficial to the future calls no this middle value is only beneficial for this call hence this will go inside the body of this function okay so whatever variables you need to pass in the future function calls put inside the argument without thinking twice what all variables you need to that are only that only you consider to be valuable in that function call only that you don't need to pass inside the future recursion calls put it inside the body of that function very simple stuff don't overthink i will i am repeating it many times don't over think so middle of this array initially the original area that i'm taking middle of that i'm only taking in that i don't care about it because if the middle is five and i've divided the array into from zero to comma four is that five actually going to be beneficial in the area of size zero comma four no hence this is only going to be beneficial at this particular call only but now i'm just going to make how many checks did we have in binary search three checks equal to less than or more than so if array of middle is equal to equal to target return my answer otherwise i can say if target is actually less than array of middle it basically means that my element lies in the left hand side okay what is the condition for that end should be mid minus 1 so i'm just going to say okay end is now going to be equal to mid minus 1 so it's going to say hey recursion i was not able to find the array in the right hand side please search for the array on the left hand side please do it please do recursion do it for me it's going to be like okay i will call another recursion call i'm going to say search array will not change target will not change start will not change end will change end will be mid minus 1 also notice one more thing whenever you're calling any recursion call this is another important point whenever you are calling a recursion call make sure you are returning it if there is a return type another important point that i have over here that you will face very tip tip tip over here make sure to return the result of a function call of the return type if there is a return type in make sure you return whatever function calls you are making because if you don't return it what will happen in the end it will be called after all the sub problems are solved and whatever in the end it will be calling the main function if the if the original one is not returned the main one also will not be returned your answer will not be returned hence here i will say return whatever answer you are getting from this it's like okay i don't care now you are solving the left hand part just whatever left hand part you are getting give me the answer for that this is very important point do not over think next point can be okay otherwise it lies on the right hand side so if it lies on the right hand side then you can just say return start is going to be mid plus 1 end is not going to change end is going to remain e only that is it that is it that's it let's try to run this and then i'll try to debug it 1 2 3 4 55 66 78 try to print in this i'm going to say print in the array let's say i try to print the target target start from 0 and from array dot length minus 1 let's say my target is equal to 4 so it should return me 0 1 2 3 index number 3. that's correct if i say 66 it should return me index number 5 if i say 78 last element it should return me index number six if i say one it should return me index number zero if i say something that does not exist like 67 it should return minus -1 binary search using recursion people how simple is this to understand try to convert these things in words all the places where you will face doubts i have added it in the notes please watch this video again and again let's try to i know we'll debug this as well we'll debug it and we'll see okay so where you will face doubt you will face doubt in three points this return value what to actually return i also may already mentioned whenever you having a function call that has a return type make sure you're returning it this will not work because in the end it's actually returning the original answer till 0 till end and if you don't have return over here it will not return the answer okay let's try to debug it i'm going to say 6 let's say or i can say 78 let's try debug see how this works internally and now in order to understand you have to actually check you know the um just try to make a tree of this so initially it's from zero till six no problem i can put it in my you know recursion call as well let's see how the call call is working let's see how the recursion call is working no problem no problem over here okay so i'm going to say main function is called first then it's going to call the entire array from 0 till 6 from 0 till 6 is going to call and it's going to say what is it going to say it's going to call it it's going to say this will not be called middle will be equal to 3 so middle will be equal to 3 at this call and this this box itself is a you know function call it's going to be like hey is 3 equal to equal to like um you know is this equal to target no it's not so it's now going to be like 0 1 2 3 so it's gonna be like target is actually greater than this so it's actually going to go over here so now it's going to be like okay array and this start will remain as it is in the function call in the new function call start will remain is equal to mid plus 1 which is equal to 4 start will remain as 4 in the function call and will be equal to whatever end was in this function call which was 6 there you have it here's the next function call start will be equal to mid plus 1 and will remain as it is it was in the previous one now it will call this function now it will call this function let's call this function this entire function will get called it's going to take middle element again which is 5 middle will be 5 let's see which condition will hit it's going to be like again this condition is hit so now it's going to be like 5 plus 1 6 so it's going to call for 6 so now the new function call will be 6 6 start and end another function call let's try to dive into this function call remember all of these will be in the stack these are waiting for the answer this is waiting for the answer this is waiting for the answer from here this is waiting from the answer from here okay this is going to be like okay give me the answer let's see how this goes now the millionaire element is going to be equal to 6 only middle element is going to be 6 itself okay now it's going to be like is this equal to equal to this it's going to be like yes it is it's going to say return 6 you have found the answer return 6 okay no problem so it's going to be like okay i have found the answer return 6 found the answer where is it going to return from where it was called very important it was called over here so it will return 6 over here that is why i mentioned please draw this again and again until unless you draw it on your own you will not understand let's say let's see from where this will come out it will come out somewhere from here for the call of four comma six that is correct it did came out but it like uh you know uh covered it so for example it will come out of here for the call for four comma six it will return six now this function call is going to have answer six it's also going to then return its value question is why is it going to return its value kunal because of this return whatever answer you are getting return whatever answer you are getting return whatever answer you are having that's why it's returning that's why return statement is important how to figure out when to put return statement if there's a return compensation over here make sure you're returning whatever answer from the sub calls you are getting i will repeat it again and clap if there's a return condition over here make sure you're returning the type which is same as this make sure returning the type which is same as this which is integer hence i'm retaining integer make sure you're returning the type which is same as this very important point make sure you make sure you're returning whatever the sub condition whatever the sub recursion calls are giving us make sure you are returning what are the subrecords and calls are giving us sub recursion calls is happening make sure you return it subreddit recursion call is happening make sure you return it okay because we have a retention type over here this type should be same as the base condition type because if you if you're hitting and if you're writing an array or something over here and it's taking an integer that will give you error obviously okay so over here what happened then it's going to return 6 this is also this now this entire value will be 6 this is going to return its entire value because it came it came a value 6 came from here this entire value will be 6 it will return 6 from here ok now this will return the entire value to main which is equal to 6 main will print 6 answer and function over that's it so can you see how this value six that was figured out in the last step traveled through function calls can you see that this is the key point please please you will not understand it if you don't run it on pen and paper and debug it yourself okay that was a very good uh good thing okay so that is what i wanted to share with you all i shared a lot of concepts a lot of hints a lot of doubts i laid i also literally told you how to how to approach these problems trust me if you cannot understand it's not about the courses there is a reason that many people drop out of the one of the best courses as well it's not about the course there is no problem in these courses if you go watch recursion of some other course you will not find like let's say a better explanation than this they will also do some great work but you will not find a better explanation than this then you might be asking kunal why is it that no course is making me pro in recursion just by watching the course because it's not possible no course can make you pro in recursion only thing that can make you pro in recursion is the points that i mentioned pen and paper can make you pro in recursion very important point please do it okay right after this video solve these problems on your own okay and make sure you check out the assignments in the link in the description what is next what is next for recursion recursion is going to happen throughout so memory management space and time complexity how much space is the recursion call taking you know and how to actually solve the exact formula for you know how to actually get the space and time complexity which is space and time complexity how to solve recurrence relations how to get the exact formula returning data structure so you might be possible that a recursion call is returning arraylist or whatever how do error list and objects and reference variables and all these things compare to each other uh when we are passing these inside the argument of the function you know complex data types that is something we'll cover in the future if you want to return the entire error list or something inside the rep function call in the recursion how can we do that that is something we will cover in the future variable function calls here we know that for every particular time we are actually calling two function calls one function call will call two one function call will call two it might be possible that one function call calls variable number of calls so for example one function call is going to call three one function of that third one can call call four another one can call five another call six permutation combination sort of questions so variable function calls we will do questions on that we will do lots of questions an entire course from now on will be based on this truth is please the truth is there is no other course that can teach you recursion like this if you're not able to understand recursion right now in this particular lecture no other course can teach you because that is the point of recursion you have to do it manually please do it manually that is more than enough it's not a problem in the courses it's problem that the recursion itself is a very complex topic for starters once you follow the approach that i mentioned once you actually have the mind map the points that i have mentioned in the notes uh notes you can find in the description below the github link okay don't leave this course saying that i am not able to understand recursion that is where you will lose because no other course can teach you recursion only way you can learn recursion is buy a pen and paper but if you had fun in this lecture please make sure you comment like and please please please make sure you share it on social linkedin and twitter share your views about recursion and how you're learning about it and don't skip this topic because entire course will not be beneficial to you then recursion is going to be heavily used in all the other data structures in the future okay so what i want you to do right now like comment subscribe share in your groups share in your private groups in your social groups in your college groups and we'll be doing some amazing questions all these things i mentioned in the future videos that we'll be doing make sure you do that and space and time complexity will be very next level lecture i'll teach you some of the nicest tricks and uh recursion we'll be doing many more questions so make sure you practice practice practice practice do questions visualize it see all the ones we did but very important thing i wanted to do right now very important thing share on socials share your views about this program in socials and tag me tag community classroom you can find our handles in the description make sure you give us a follow share it everywhere so that everyone can benefit from these amazing courses you will not find an explanation of recursion like this on the entire youtube i am like very confident in the courses so please make sure you do it thanks a lot for watching and i'll see you in the next one uh please make sure you share this is a very it was very hard and i'm taking so many resources out of my own time and money and energy and whatever you know all those these equipments and everything calls money and i'm not taking and taking anything from any person and we have so many big plans for the community if you support me i will make sure i give my 200 you can write it down you can take a clip of this video not a single rupee or dollar i will charge any person and i will give you my thousand percent i am saying it very confidently you will not find the quality of the courses that i'm providing anywhere on youtube don't trust me check out this check out all the other recursion videos you will not find this in-depth explanation where i actually teach you how to think this is nothing wait till we do dynamic programming i will actually teach you how to think in dynamic range actually in the mind youth details what your thought process should be trees and all these things how actually questions are asked bfs dfs recursion whatever things please support me please it's very important that these courses for free reaches to thousands and millions of millions of people at least in india because in india this is very important topic the you know people over hype company programming and then they do you know for not just india but like um the coding rounds of conte of interviews right i am saying you right now recursion is the most important topic for your interview rounds period most important topic so what what do you do now you share it in your groups you share it on socials you tag a stack community classroom do it right now please share if you like this video it will really help me and please comment comment is very important so future people can discover this video comment for reach for example okay so follow us on socials i will i hope you will follow you know if you have benefited and you benefited from my time i hope you will share about it i hope you will support my work and uh thanks a lot for watching i really appreciate your support and i'll see you in the next videos in the next video we'll be doing uh merge sort quick source then we'll be doing entire time complexity and space complexity from beginning scratch thanks a lot for watching make sure you do all these action items that mentioned practice practice is key i will see in the next one take care [Music] bye

Channel: Kunal Kushwaha

Views: 568,900

Keywords: recursion in java, interview preparation course, recursion fibonacci series, recursion and backtracking, recursion in programming, recursion in 1 shot, introduction to recursion, recursive functions, recursion masterclass, recursion from scratch, how to master recursion, backtracking, recursion basics, java course, recurrence relations, binary search recursion program, recursion playlist, best recursion tutorial, dynamic programming introduction, tail recursion

Id: M2uO2nMT0Bk

Length: 115min 49sec (6949 seconds)

Published: Sun Sep 12 2021