Recursion - Level 1 Questions (Theory + Code + Tips)

hey everyone welcome back to another video and this is the second video in the complete recursion series so in the first video we did the introduction of recursion that video is very important to watch please watch that video first by the way we're doing the entire data structure algorithm boot camp and recursion is also a part of it and we've already learned introduction to recursion video is already done so in that video we actually shared how to learn recursion how to understand the problems and now let's say we have given an introduction to recursion now to the most important part which is lots of concepts and questions so this is going to be a series so i'm going to be making video on like right now we're doing this video is about um basic easy questions on recursion just this is just to give an idea about like some some little bit basic practice to students after that i'll teach you recursion with arrays so like how to return arrays how to pass arrays in the argument in recursion and stuff um after that we'll learn about recursion with patterns so patterns forming with recursion sorting and searching with recursions we'll do that then we'll do another video on uh recursion of strings we'll do that and after that we'll do one more very important video which is recursion uh questions on subset subset questions and after that uh we'll also do questions on backtracking which is also a part of recursion they will be doing end queens and n knights and sudoku solver basically questions like this we'll be doing in this complete recursion series so make sure you like share and subscribe let's get started so this video is about basic recursion problems i am not going to repeat the things that i have already shared in the previous videos because that is a waste of time it does not make sense to say the same thing in every single video that is why i reference it i'm like okay i've explained this in detail in this video please watch it link in the description timestamps are also added so how to understand recursive problems what is the recursion tree so in this particular video you may have doubt like if you have not seen the previous video then you will have doubts like what is recursion tree what is call stack how the arguments are passed you know how the function value is returned from where the value is returned all these doubts will be solved if you just watch that video once the introduction to recursion video okay this is specifically about questions let's get started so in the first video we saw like how do we actually approach a problem right so we what do we do we build a recursion tree so when we are given a problem we try to see how to break that problem down into smaller problems that is what we do so for example if i want to print let's say something is given to you like n is equal to 5 n is equal to 5 is given to you so like n is equal to 5 is given to me question says print uh all the numbers from until uh one for example okay so you have to print five four three two one that is what you need to do just by calling a function you can only call one function like that so you can be like okay i'm gonna call function with the argument five this is going to print five and then it's going to say hey function four print all the numbers from four till one it's gonna be like okay this is going to print five and it's going to now be in the stack let me draw the stack as well again in detail explanation of this already given when a function call is called while it is waiting for the other call to finish it's going to rest in the stack i explained this in detail in the 2 hour long video the 2 hour long video is nothing but an introduction to recursion please watch that video your doubt will be cleared a very important video that will make you understand how call stacks and everything is working i'm not skipping anything please watch that video all right then it's going to be like f f of 4 is going to be like like the function will be called with argument 4 same function it's going to be like okay i'll print 4 it will print four and then it's going to be like hey let me ask the function call three to print three two one it's gonna be like hey function call three like same function call with argument three can you please print uh three two one and by the by that time i'm going to be resting in the stack and f of 5 is off function of 5 is also resting in the stack f of 3 is going to be like yeah sure i can print 3. similarly i can call f of 2. f of 2 will be like yeah i can print 2 i will call f 1 f of one will like i can call one do you want to print zero or something else uh they're gonna be like no no we don't we don't need to call any call anyone else example f of three is here this is stack memory explained in detail then f of one will be here somewhere f1 i'm going to be like okay i'm not calling anyone i'll be removed from the stack remove remove then remove then remove how this removal happens already covered any introduction to recursion video so make sure you check it out um okay and by the way i've also shown this by debugging this entire question we have solved in detail via running the program in debugger okay so we can do this this is very simple so now if we write the pseudo code for this so we can just be like okay there's a function that is known as let's say f u n it takes a number what does it do it prints n that's it and it calls function of n minus 1 that is it and a base condition will come over here that if n is equal to equal to 1 just print 1 and return that's it nothing else we need to do just return from it and i also explained this in detail how to form this particular pseudo code you have to think about what is the return type and i also told you if the return type is void you don't have to write return function call because if the function's return type is int whenever you're calling that function call you have to return this there is something we'll look into later on okay but right now what is the return type nothing you just need to print you just need to print 54321 hence no return type hence no need to say return f of n minus 1 no need to do it because there is no return type just call it void okay this is something i explained in detail but i will also explain this as an example of with a return type that will make things more clear let's try to code this thing so i've created another package called easy i can say something like uh you know n two one end to one okay so is there a return type no there isn't so void um i can say fun it's just taking an integer n and then what is it doing it's saying that if n is equal to equal to 1 or i can say if n is equal to equal to 0 just return don't do anything that is also fine recursion questions can be solved in many ways right so you can do it in many ways and then i can say otherwise just uh just print n and call function of n minus 1 already explained in detail in previous lectures that is it if i just say print not print i am not returning anything so i can just directly call this five okay run i also showed you how to debug this it will not make sense if i debug the same program again and again you can do it on your 54321 very simple i can do it as a reminder again but i should not be doing this because i've already done this many times in the previous lecture click on debug you will able to see how the stack memory is getting fill and everything you will be able to see here you can see the stack memory main is in stack then the function call uh for five is in stack then it's going to check hey is five equal to zero no it's not okay move ahead print five and now call for four now four will be over here now this is for four uh function call four this uh this fun is again over here right print four again fun will go on the stack fun is again on the stack and while these two are waiting while these two are waiting as you can see this is waiting this is waiting now this is in the stack it will print three three will be waiting it will be waiting for two to finish two will print itself now it will be waiting for one one will finish itself it will call 0 and 0 will not do anything it will just return that's it now how will it get out how will it get out we already saw it whenever you call a function when that function finishes executing it gets out from where it was called okay it will not make sense to you until unless you try it on pen and paper okay i explained the same question in detail previously please make sure you check it out okay that's it all the function calls will be removed from the stack now you may ask kunal what if i want to do what if i want to print one two three four five instead of five four three two one pause this video and think about it okay so now if you have pause this video so you're saying that uh when you are emptying the stack when you are emptying the stack then only print because now you don't want to print five four three two one remember what is happening you pass five you print five and then you call the recursion call for that recursion call you print four then you call the recursion call that is not what we want to do we're like okay you're passing five this five i will print at the end first give me the answer for one two three four let me bring up my um this thing drawing part so okay so what if you want to print one two three four five n is given five answer should be one two three four five so instead of printing five when you call function of five instead of printing five because if you print five right now over here it will print five four three two one okay so basically the idea is that uh you're like okay i will print five later on at the end first print one two three four for me it's going to be like four uh i'll four is going to be like okay i'll print four after one two three so it's gonna call three till this time these will be in the stack f3 will be like okay i will print three later on let me first ask the other function calls to print one and two after they have printed one and two then only i will print three okay two is going to be like let's print one first okay so one is going to be like uh that's it i can print myself so one can print itself then it will be out of stack and from where it will be removed it will be removed from where it was called and it was called here you you do realize this chain right if this is chaining to this means that this function call this function was called when in in this function's body it's very simple stuff i covered this in detail in the previous section okay so it will be like okay this is remove from stack now we are in this function call this has just finished now i can print so basically when the function call has finished executing then print your number it will be also finished executing now so when this function call is finished executing in this function then print three then print four then print five so where which function the function for which you are waiting for that you have to first wait for it to finish and then print so for example if i just copy this i can say reverse i can say one reverse so basically the idea is once it has finished executing it will come out from here then print that's it let's call fun reverse one two three four five how easy is it very easy stuff these are easy questions but very important to grasp it's not just it should not just be like okay i'm able to solve it no understand in depth how these things are working how every function call is working this will help you in solving complex problems that is why i'm teaching you first easy questions okay because then you will say kunal you directly jump on to difficult questions and you're not like true to your words it's not beginner friendly course no good cool questions will also come all right let's move forward now what if you want to print um one two three four five like five four three two one and one two three four five it's very simple just print this also and this also it will print like if you put s out over here then while it is forming the recursion calls it will keep printing five four three two one and once the calls are removed out of the stack one by one that will then it will print one two three four five both the concepts we just learned merge into one you can say fun both please i have explained in detail how to understand these questions in the previous video hence please check that out okay so i can say fun both this will print 543 to 1 then 1 2 3 4 5. so five four three two one and one two three four five that's it as simple as that complexity you can figure out yourself because it's just printing end times so often space complexity will also be often because it's storing that many function calls in the space we already talked about the space complexity of recursion in the space and time complexity lecture that is also something covered in detail link in the description below the playlist entire playlist is available over there the ongoing like uh or if you're watching in the future and the complete java plus data such as algorithms plus interview preparation playlist cool let's move on to the next question okay it may sound a little annoying like when all you are repeating these things you know the same guidance thing you're in your recursion video repeating again and again but it's very important anyone can solve questions any youtube video can t you know give you the solution to all these questions but nothing is going to benefit you if you're not doing it by if you're not following these steps that i mentioned in the previous video if you're not writing it on pen and paper if you're not building the thought process like i am over here right now i literally mentioned to you like the steps you know so basically that's the idea like the steps are very important okay so please make sure you uh you do that um just follow the steps like how to understand recursive problems uh like building the tree seeing where the call is happening how the function is getting you know executed and finished and how the stack is forming how the stack is getting emptied mentioned in the previous video now let's look at another simple question but very important for some some concepts that i was telling you about before now this question states that you have to just do a factorial but okay factorial is an easy question but very important concept over here that will help you in the future so please pay attention if you are specific if you are you know new to recursion so factorial of a number factorial of a number we have already done fibonacci of a number so please watch the previous video for that that's a factorial of a number what is factorial of a number let's say you're given let's say n is equal to 5 or something okay the answer should be equal to what answer should be equal to 5 factorial which is going to be equal to 5 into 4 into 3 into 2 into 1 okay something like that so basically this is equal to what 120 okay that is what we want to do again recursive problem try to see what are the you know try to see what are the recursive steps that you can break this down into that's you know in the previous video i mentioned like how do you find how do you approach a recursion problem because anyone can teach you relax hundreds and hundreds of videos on factorial of a number on youtube but try to see what why are people doing it the way they are doing it what is the approach what do we need to think about function calls return value how arguments will be passed what will be returned how the function will come out of the loop and all these things so basically here what you want to do is first we see what are the function calls being repeated can you see that if i'm saying that if i'm saying factorial of 5 can i not write this as 5 into factorial of 4 because this is equal to what 5 into 4 factorial can i not write factorial of 4 as 4 into factorial of 3 now can you see the recursion pattern that's it so what is factorial of n another recursive call that we made previously what is factorial of n n multiplied by factorial of n minus 1 that's it that is it what is the base case base case can be something like factorial of 1 is equal to 1 that can be our base case that's it now that you know how it's you know the function call now let's see how it's working internally like the graph of it the tree so basically 3 is going to look something like this f of 5 this is going to say okay the answer is actually equal to 5 multiplied by whatever the answer is of 4 is going to be like 5 is going to be like ok i will get multiplied by whatever the answer is of this thing but first give me the answer of this thing okay f of 5 is going to be like hey f of 4 i will give you 5 to multiply in yourself but at least give me the answer of it f of 4 is going to be like okay give me a second uh till then we both can rest in the stack memory i will ask f of 3 i am going to be like f of 4 multiplied by f of 3. it's going to be like hey f of 3 i am ready to give you f i'm ready to give you 4 can you please give me the answer of 3 factorial what is f of f of n is n factorial basically this means n factorial so i'll be like ok this is equal to 3 into f of 2 means 2 factorial this is equal to 2 into f of one f of one is going to be like okay i am the base condition my answer is one only f of one itself is one it's gonna be like okay then multiply it by two then it will come out of the stack it will return its value here return its value here is it printing value or whatever whatever what is it doing it's actually returning the value so what is the return type of the function going to be if it's returning a value let's say integer value int and what trick that i told you before if the function type is inked or anything else the function type is inked or anything else the recursion calls also have to return obviously because this function is i am not sure how to explain this in a simpler way but i i'm not sure if you're able to understand the common sense behind this please put a little efforts in this like it's very simple it's common sense see the thing is if integer value is asked to be written in a function call then a call of that function is going to return integer only right if f of 5 is asked to be returned that integer then f of 4 that is also the function call of the same body so it's also going to ask to return an integer so wherever these function call is called this function call is called this is called this is called wherever this is called it will return an integer this entire thing will be an integer hence i have to return this this was the intuition behind it why we are returning every function call when there is a return type because the function is body is same you're just calling that function only and that that function requires you to return something if you don't return it then what will you return wide you can't return void int is required okay so when this comes out of the loop when this function is finished executing it will come out of the loop and it will actually return the answer of f of 1 answer f1 will be returned and it will be stored where very simple is the first lecture of functions where is the function return value stored from where it was called very simple very basic first lecture okay so this will return one so this entire call will be equal to one two into one will be equal to one now this entire so two into one will be equal to two so this entire thing now will be equal to two this actually will return to it will literally return to not print or anything this entire value will be 2 it will be stored somewhere let's say and that here it will be like okay now this is 2 3 into 2 is 6. now this value will be 6 when this comes out of the function stack as well as 6 into 4 24 and now it's going to be like 24 into 5 120 make sense very cool stuff so this will 24 okay so 4 into whatever whatever what was the answer for this 6 right so 4 into 6 is 24 and this will be now 24 so 24 into 5 is 20 so this entire thing will be 20 this will now be returned from where this will now be returned to main because it was called where it was called in main and that's your answer that's it as simple as that how easy was this the function call and everything okay let's try to code this i'm going to say factorial you can try for long or whatever but i'm going to just for this week of simplicity static end factorial it just takes an integer n that's it it's saying if n is equal to equal to 1 what do i need to do just return 1 only because factorial of 1 is what 1 in case you try for 0 so 0 factorial is also 1 in that case also i can say let's say if n is less than equal to one in that case just return one if you put zero it will return one if you put one it will return one okay um and then i can say we are imagining that we are not adding negative numbers and after that what can i do just return what n into factorial of n minus 1 that is it that's it answer why am i returning this see i'm returning this i am returning the function call okay previously in printing what i was doing i was doing something like this but i'm actually returning the value because i already explained this so answer will be returned so this value will be returned the entire answer will be returned over here and i can just say print answer should give me 120 120 okay you can debug it as well one by one that's it as simple as that similarly what can you do sum similarly you can do sum what do you need to do sum of n numbers okay that is what you need to do so what is the sum of an n number is going to be instead of multiplication let me just change the name so it's not confusing instead of multiplication what are you doing addition is there any change in this in factorial you are doing multiplication here you're doing sum of n numbers what's so difficult in this what is sum of 5 4 3 2 1 let's see 15. now let's do another question this is called sum of digits now notice something we're not saying uh sum of like the range or anything no but actually some of the entire digit so basically question says sum of digits so basically let's say n is given to you like 1342 the answer should be equal to 1 plus 3 plus 4 plus 2 which is equal to 4 4 8 10 answer should be 10 so actually sum of individual digits if you want to do it normally how can you do it if you want to do it like normally basically over here also we can see how to break it down into smaller problems right so this can be basically broken down to 1 plus sum of digits of the number 342 okay this can further be broken down 3 plus sum of digits of the number 42 as simple as that make sense and that is what we're going to be doing today so how can we do this how can we do this thing so basically the idea is that uh what is the base condition going to be obviously well if the number is 0 if the number is uh 0 then return the number itself return zero okay that's it maybe that can be our base condition in order to make things simpler so basically the idea is that f of n okay it's equal to like the first digit whatever digit we have let's say yeah whatever digit we have how do we actually get the individual digits we can take uh remainders make sense you can take remainder by 10 we have uh done this previously as well so if you want to get 2 then 4 then 3 then 1. how do you do it you just say remainder is equal to n modulo 10. so remainder is equal to n modulo 10. so you know one three four two divide by ten remainder will be two and that is it two is you are getting then n will be reduced to and divide by ten n will now be reduced to 134 something like that okay so i can say that f of n means uh the sum of digits of all the numbers in all the let all the digits in n is going to be equal to what all the digits in n divided by 10 right plus the digit last which is n remainder 10. that's it that is it you know you want to build a tree for this you can do it so basically the idea is going to be that one three four two so it's gonna be like okay what is what are the sum of one three four two it's gonna be like the remainder two plus whatever the sum is of 134 it's going to be like 2 is going to 11 okay yeah i'll wait give me the answer of 1 plus 3 plus 4 2 is going to be like i will wait obviously what are we returning number so return type will be what integer hence we would have to return this thing we cannot leave it without return because of the same concept i explained to you previously i explained it to you very in detail for five minutes i think so it will be very not good if i explain it again and again okay because this is actually asking 2 is actually waiting for this to return 1 plus 3 plus 4 hence it has to return literally say return 1 plus 3 to plus 4. okay 2 is asking for it to do it that is why i'm going to say return whatever answer you're getting when it calls this it's going to be like return 4 plus whatever the sum is of the digits 13. so whatever the answer of this is it will actually return from where it was called it was called from here okay very simple let's code this i think after doing factorial this should not be an issue so actually a very you know simple problem now so i'm gonna say i'm gonna say digit sum and complexity what is complexity the number of digits you have seen what are the number of digits are obviously in match for you know the number theory video that we did i explained to you how to use log to find the number of digits complexity is login okay cool so we are just going to say static whatever returning integer okay i'm going to say sum of digits integer n will be available over here all right and i explained to you previously as well in the intro to recursion video and this will be much more clear when we do arrays and more complex question whatever thing you pass over here in the argument that will be passed to the recursion call whatever you add over here whatever variables you create over here they will only stay for that recursion call if you are not understanding what i'm saying it means you have not watched the previous video carefully i explained that specifically i even wrote that in my notes and many people who watch the video they also give a shout out like what a brilliant way to share okay please watch that video i explained it very in detail and what what do we have on the white board over here it's just basically going to be like if n is equal to equal to 0 that's it otherwise i can say that just return what n modulo 10 plus sum of and divide by 10 okay let's try to run this i'm going to say sum of one three four two what is the answer one three four two ten 10 simple stuff similarly if you want to do product digit product product of all the digits in the what do you have to do i just rename this so no no actual change in the concept right now product instead of addition you can do production but here just a very slight change will be required because when it returns zero and all the answer that you have gotten anything multiplied by zero gives zero so in the end it will give the answer zero only so it's a way what we can do is if one digit is remaining return that digit okay maybe we can do something like that so you can say if one digit is remaining if n modulo 10 is equal to n itself then return n what is 1 into 3 into 4 into 2 it's actually equal to 24 that's correct let's say 55 this should give me 5 into 5 25 but it also works if there's a 0 in it so as you can see the digit 0 is in this so answer should be 0 0 okay similar concept let's move forward let me teach you another concept about like passing numbers right so it's a it's an important concept so i'm just going to teach you over here i'm going to say concept um i'll write some code and you tell me what the answer will be okay i'm going to say void just a function okay and i'm going to say if n is equal to equal to 0 i'm just going to say return okay now i'm going to say print n and then i'm going to call this function i'm going to pass n minus minus over here okay i'm just going to say n minus minus now if i call this with 5 okay so it's like okay 0.5 then n minus minus 4 and minus minus 3 and minus minus what should be the output tell me pause this video think about it okay i hope you thought about it let's try to run this no don't just think write it on pen and paper okay let's just run it infinite recursion infinite recursion stack overflow you know we talked about it's just printing 5 only what is happening like why is it not subtracting n minus minus means n is equal to n minus 1 that is correct but no this is the concept that we learned about it's like n minus minus versus minus minus n it's not similar n minus minus means let me just bring my whiteboard okay so let me just write it down i'll write down in red color n minus minus versus minus minus n what is the difference both are like n is equal to n minus 1 right so then what is the difference difference is this this will pass the value of n first and then subtract it so if i'm saying n minus minus for n is equal to 5 it will pass the value of 5 first and then subtract it afterwards when when after the function is over or whatever but since it's already subtracting adding you know it's already passing 5 then you want to pass five minus one then it will again pass five then you want to pass five minus one into again past five it's always passing five only it's not actually subtracting that comes later on okay and here it's like actually past the value of n first sorry pass so i subtract first and then pass the value of n subtract first then pass okay there was a basic concept i want you to know let's try to change our code i can instead say minus minus n that's it cool i can actually put it over here concept i'm gonna say concept only okay sounds good all right um let's move forward to the next question okay now let's look into the reversal number problem let's say another question we can take is reverse a number this is something we have done via and by the way try to solve these simpler questions like iteratively and then you can also try like recursively usually it's the other way around you first solve complex problems using recursion i covered this already i'm not sure why i'm saying it again and again so recursion makes it simple for us to solve bigger problems into smaller problems then you can use iteration to convert it into iteration so reverse a number reverse a number using recursion n is given to you 1 2 three four five you should return five four three two one okay it does not have to be sorted so you can take it like one eight two you should 4 you should return 4281 how do we do this what can be the recursion call in this recursion call in this can be that hey this if i want to reverse i can say that i will add if you just reverse let's say this half of the array and i'll just add one over here the you know let's say some one over here first one will come at the end once you just reverse this now this is the sub problem we can use apply recursion over here also this can be converted to hey try to reverse 24 and i will add let's say you know um eight over here in the end in the output we cannot convert it into strings okay so we have to do it without strings so we have to think about it or we can do it like the other way around i can say i can say i could get the last element or or i can say that i can get hey what you can do is let's say instead of this you can say okay if you want to reverse this entire thing right you want to reverse this entire thing try to reverse 182 like the first one try to reverse 182 and add 4 in the beginning add the last digit in the beginning plus try to reverse 182 something like that you can do now this can be like add the last digit in the beginning try to reverse 18 yeah now it makes sense you may be asking quran how are you able to come up with this because we've already done this thing okay you just take one element put it in the first last last take the last element put it in the first the last element put it in the first okay so basically whenever this is a pattern okay that is why i am able to solve it very easily whenever you ask like digit by digit problems in that case you are going to be taking remainder and dividing the number by 10 okay that is the pattern um and this can be eight plus reverse of one so basically it means that whenever you're trying to reverse a digit of one like a single digit number just return that number itself that is what we can do okay so it's can be like function n is actually equal to last digit will go over here you will add this with what you have to add it right you have to add it with the reverse of the remaining which is n divided by 10 182 is what n divided by 10 so reverse of n divide by 10 this will give you the reverse number but how do we actually add it i need to get the 4 to the thousands place okay how do we do that many ways to do it i'm just thinking which one to tell you or i can tell you all the ways you can either take a separate argument you can take a separate argument so there are a bunch of ways by which you can do this so one of the things that i'm trying to figure out is like um how do we actually increase this particular like 4 to you know towards the thousands place so what you can do is uh the number one way you can do it is let's say take the value of this base counter in the argument itself um that is something you can do we can we can try that or what you can do is you can take a separate answer outside the function and you keep updating that answer you can do that right that's the easiest way one more thing you can do is you can take a separate like base outside and uh you can then um keep updating like usually in the final let's let's let's talk about it way number one so way number one basically means what okay so way number base uh way number one basically means that you will have your function over here okay your function will be over here and your function is going to contain the number n okay so basically what you're going to do is you're going to say that if the number is not equal to zero okay um in that case you're just going to say or here i'm just going to take a sum outside this okay it's going to say remainder you know is equal to i can just say if sum is equal to 0 return 0 base condition can be over here if sum is equal to 0 or you can just say return no need to return 0 okay and then you can say that something like this you can say we know remainder is equal to and modulo 10 so if i'm saying the number is 1 3 4 2 okay the answer will be 2 4 3 1 how because i know remainder is equal to n upon 10 which is 2 and it's going to be like 2 um reverse it just put it at the first and reverse whatever that you're getting over here means reverse 134 okay what is the actual answer initially going to be it's going to actually start adding from 2 then 4 then 3 so 2 will be added first okay then 4 will be added then 3 will be added then one will be added that is what it's doing so one by one it's adding so as you can see first two is added then when three is added two comes at the tens place so instead of how do we do this how can we say that 2 plus 3 will give me something like 23 can i not do something like if that say initially the sum is 2 over here okay can i not say 2 into 10 plus 3 is equal to 23 now when i want to add 4 it's ok when i want to add sorry it will be 4 over here not 3 4 because 4 is the second one so it'll be like 24. okay 24 will be available over here and after that it's going to say okay now the n divided by 10 is giving me three and like the remainder is now giving me three how do you add three over here it's gonna be like okay multiply this by ten plus three by the way we've covered this previously it's gonna be like 243 now one will be available here into 10 plus 1 which is equal to 2431 only recursion that is happening is n divided by 10 that is the only recursion happening main value that is getting updated is outside hence no return value is required why do we need to return value we need to return value when some answer is being calculated for some number inside the function why do we need to return value because the value that is formed inside the function the variable will have the scope inside the function only in order to accept it outside the function access is outside the function we have to return that value but since the number is already outside the function over here you can just do calculations okay so you can say sum is equal to what previous sum multiplied by 10 plus remainder that way one by one it's getting multiplied by 10 and 4 is moving towards the thousands place in four three two one or whatever you wanna do okay and in the end i'm just gonna say okay once you have moved two and four now trying to move and divide by ten then again move and divide by ten i can just call function off and divide by 10. sort of like cheating because i'm using an extra variable over here outside the function okay i'm using an extra thing outside the function that is why this is cheating it's not like pure thing like i want to do it just using recursion okay in that way we can also do something okay maybe you can take a base over here or something okay let's see how we can do that but i think this is very clear one of the ways you can do this second way i'll teach you i can quote this as well by the way if you want let's code this okay and then you'll say kunal you skipped it okay so here i can say reverse a number many ways i can teach you so one way can be something like i can take a number outside static int i can take sum okay which is initially equal to zero and then i can say why what is the static we'll cover in object-oriented programming so i'm not returning anything because i'm already changing the original value that is outside it so here i'm just gonna say this sum is going to be like this is something we'll cover in scoping okay don't worry like the outside could how are you forming this variable outside okay so we'll cover it when we do the scoping things and like i think i believe i covered this like a little bit previously but we can dive more into it when we do objective programming okay so let's take an outer variable that can be accessed by all the functions and everything and i'm just gonna say reverse method number one it's just taking a number n and it's saying if n my alarm went off for something if n is equal to equal to zero oh yeah by the way uh over here i did uh sum it's not going to be sum it's going to be n n is equal to 0 obviously okay so if n is 0 don't need to do anything don't do anything then i can just say remainder it's going to be n modulo 10 and i'm going to say sum is going to change the original sum is equal to sum multiplied by 10 plus remainder and then i'm just going to say call and divide by 10. okay actually gonna put it above it somewhere over here let's see then we have just following convention so i'm going to say i'm just going to call reverse one one two three four then i'm gonna just then i'm just gonna print sum sum should be reversed to four three two one four three two one okay and now i may ask you now what if i don't want to take the outside value as the main value what if i just want to do it like this like this how can we do this this is a very important point now you need this base condition now now you're not like skipping one by one so you actually need some value in order to like okay how many times you want to skip it you know not skip like how many times you want to shift towards the left so you can either add like int base over here something like this okay or you can add static in base times over like times you will multiply it by 10 that is basically what i'm saying you can add it over here or what you can do is you can return the value of some other function okay so you can say helper function if this takes n and it takes a base base can be anything let's first try to do it in whiteboard and then i'll teach you so something sometimes that happens you know you might need so basically the idea is sometimes you might need some additional variables in the argument in that case make another function helper function okay so let's see how we can do it okay so what is the idea let's see the way number two is what you're given a number let's say for simplicity you're given one two three four okay one two four three or no for simplicity i can say one two three four you have to reverse it and what you can do is we can take another function maybe whatever what we are going to do is similarly we are taking the remainder 4 and we are adding 123 to it but in order to add 123 this should be 4000 okay this should be somewhat like 1 4 into uh you know 1000 plus 123 we need this that is what we need so from where can we get this thing that's a good question it's actually equal to 4 into 10 raised to power 3 plus 123 okay and what is this going to be the reverse of this 3 into 10 raise to power 2 plus reverse 12 okay what is this going to be 2 into 10 raised to power 1 plus reverse of 1 that's what it's going to be so this particular thing i can actually pass as an argument okay so i can just pass initially the argument i can pass is what the total number of digits minus 1 total number of digits minus 1 so i can pass the argument like this i can say f of n and initially i'm passing the number of arguments number of arguments number of arguments i can pass in this okay it's going to be equal to what the last which is n like the remainder multiplied by 10 raised to the power argument minus 1 my handwriting is not very good right now okay never mind i'll try to write it in a clear way so right now i'm passing two things in the function call because you understand why i'm taking arguments over here right you can also take it outside it but right now i need it that's why i'm taking it inside the call and i'm going to create separate helper function for it n argument is actually going to be equal to remainder multiplied by 10 raised to the power argument minus 1 plus reverse what do i want to reverse n divide by 10 and argument will now be reduced to if it was 3 then 2. so argument -1 that's it that is it as simple as that okay so i hope you are able to understand i also formed the tree and all the pseudo code and everything that is it you know once you do all the once you try to analyze the patterns and everything you will be able to do it okay so let's try to do it i'm going to create a helper function so i'm going to say return so first of all digits what are the number of digits going to be integer value of math dot log n of n plus one okay we covered this in mathematics if you are not aware okay from where did you get this formula already covered in the mathematics video okay so the total number of digits and then i can just say return reverse sorry no i can make a i can make a helper function i can make a helper function and it will it will basically pass n and number of digits that is it let's create it it's going to return actually it's going to actually return the reverse of a number hence we will have integer obviously now everything changes because here you here you may have a question like canal you may not have a question because we are changing the original like outside the value so nothing inside this is getting changed like only the outside variable are getting change hence no need to return but here here you do need to return because actually things inside this function are being changed any variable anything made in this function will be changed because you know right if i make num some variable over any variable we make over here that will be only for this function call and it will not be available outside it okay if you want to access this digits in this other function you cannot do it scoping we covered this in functions so no need to think about now because we already discussed it so i'm just going to say that first of all if the number is a one digit number return the number itself okay otherwise what do we need to do otherwise we need to say return remainder so return remainder into math.power of 10 digits minus 1 plus the function call recursion call and divide by 10 digits minus 1 all right let's try it yup should convert it into integer you should use long or something because for bigger digits so let's see i'm going to say reverse 2 is this reverse 2 yeah okay and i now i don't want to print the sum i actually want to print this answer whatever answer i'm getting from here can debug it if you want um let me now run this should give me four three two one four three two one all right hope you're able to understand um how i was able to solve this using a helper function sometimes you may require such helper functions okay cool let's move forward now another thing you can do is you can basically check whether number is a palindrome or not so i can use a similar concept okay and by the way we have done the palindrome function using like the while loop you can try to convert that into recursion very simple just like i did for this one it's literally the same thing okay let's try to do that just gonna rename this to reverse and now for palindrome it's going to be like static boolean palindrome number okay so i'm going to say if number n is equal to equal to the reverse of that number then i'm going to say or i can just say return return this thing because this is a statement the statement will either be true or false right so this statement will either be true or false and i can just return it right this so i can say palin is it palindromic or not this is should going to say it's it is palindromic okay true but if i remove like something from here and run this then it's going to say false very simple stuff make sense if i took one digit number it's gonna say true easy peasy okay now similarly you may ask kunal what if you don't wanna use this reverse function and use it on your own you can do it we have already done the palindromic function just check the first element with last element okay this element second last third last element uh so on and so forth like first and last person like that that you can check okay now you're taking indices you can take that like a helper function okay you can take a helper function let's try to do it you know let's do it yeah okay so what if i want to figure out whether a number is a palindrome or not palindrome or not so example number is given to you one two three two one how to figure out whether it's a palindrome or not we're going to say one two three two one is given check this and this start and end we can take okay so you can say start and end this should be equal yeah that's correct move forward this should be equal correct this should be equal you know while start is less than end okay we have done this but over here like you do know how can we solve this with like recursion how can we solve this with recursion so if my start and end are over here initially in the recursion call i can have start and end that's correct so i can add function call the number itself start and end something like this okay okay but uh this is like checking whether a number is palindrome or not and uh i think um the first and last check that we can do if you convert this integer number into let's say a string uh then you can check that or if you have an array then you can check like the you know this is parent room or not um but like for i think uh checking a number is parent or not i think this should be this should be fine all right cool that looks good let's move on to the next question another very simple question are you given a number you have to count how many let's say zeros are in that number okay let me bring my white board up so let's say count zeros question count number of zeros in a number okay let's say number is given to you three two three zero two one four 0 9 or something let me take a smaller number no problem again something like 3 0 2 1 3 0 2 0 4 then the answer should be equal to 2. i don't think i should even do this just take remainder check whether the remainder is 0 or not that's it that's it while entire n is not equal to 0 this is very simple stuff what is in this question nothing okay but the thing is like you have to count the number of zeros right so how can we do this like in recursion we have to return the count you can either take the count inside the argument itself okay so if we take count inside argument let's do that first if we take count inside argument what will happen it's going to be like function of n is going to be equal to this is basically going to call any one of these two things so notice what will happen if you're taking count inside it so initially let's say the count is zero two things will happen if digit is equal to zero then it will call what function of n count plus one sorry and divide by 10 count plus 1 else it will call function of n divide by 10 and count hope that makes sense okay here it's going to say count initially let's say three zero two zero four is available over here count is zero it's going to check for the remainder hey is uh is four equal to zero no it's not okay count will remain that no same number will now be three zero two zero that's gonna be like hey is remainder equal to zero yeah it's equal to zero increase the count by one okay count will be one number will be three hundred and two is remainder equal to zero no it's not count will remain as it is number will be reduced to 30 is remainder equal to zero yes it is count will be increased by one number will remain three is remainder equal to zero no it's not count will be remain the one it's when it's when it's equal to zero then whatever answer you have return answer so basically imagine what will happen it will return 2 so this will return 2 means this entire value will be 2 this will also then return 2 this will return to this will return to and this will return to oh good this is actually a good question in order to understand the flow of program for when you have to count numbers can you able to are you able to see how that when the number is reached zero whatever count value will be over here that is your answer can you see that and i'm just returning it over here when i'm returning it from here where it will be returned from where it was called it was called from here 2 will be returned since this answer is returned this function is over here the answer is 2 because 2 was returned from the below this will also then return 2 this will then return 2 this will then return to then return to okay so it's going to be like hey what is the answer you are getting what is the answer you are getting what is the answer you are getting so it's actually returning the answer whatever it's getting from the below at every point of step we are not doing return the argument no we are only doing return argument in the base condition that is the main point so whatever argument value of count is there in the base condition that will be returned only once because base condition will be hit once only and whatever value is returned from there that will be returned from everywhere important concept for count i can write it important concept right over here okay try to debug it on your own but it's very simple i believe they explained it very clearly so let's try to like code this thing okay let's try to code this thing so where is my editor now all right so i can say count zeros is actually a good question publix and not just zero you can count any number it will be counting zero let's say i have to return the count integer int count in the number and i'm going to say helper n and initially sum is 0 okay this is my count see that looks good and basically i'm just going to say that if n is equal to equal to 0 return whatever count you have this is a very simple question you know just make a tree on your own write it on a pendant paper like i did and we'll also try to debug it so that you are able to see how these things are flowing see if you follow what i told you in the first lecture if you follow how the value is being returned from there the function is exiting from where the function is inputting how the stack is filling up how the stack is filling out then you will understand any question same with this and what is this it's saying that remainder it's going to be equal to this if the remainder is equal to equal to 0 count will increase so i'm just going to say return whatever answer you are getting from and divide by 10 and count plus 1 otherwise you can say return whatever answer you're getting from n divided by 10 count will remain as it is that's it let's try to run this i'm gonna say count number of zeros in three zero two one zero or something this should give me two okay if i add some number here that should also give me two only okay if i add two more zeros it should give me what for now pretty good stuff as simple as it gets we can also debug it you can see if you want to debug it so if you want to debug it it's very simple actually so here i can say just move forward so initially it's uh a very big number it's going to be like hey what is the remainder it's going to be like it's four okay then just call um you know three zero two one zero zero zero and count will remain zero only it's gonna be like yeah okay it's going to be like now count will increase 1. so instead of calling this it will now call this where count is increased by 1. in the end you will see it will just have all the value of counts over here c will now be equal to 4 and now n is equal to 0 so it will return 4 it will return 4 from where from where this function was called either this or this so either this entire value will be 4 or this entire value will be 4 and this will actually whenever 4 is returned over here it will return the function itself so wherever this function wherever this is being called that entire value will be returned as well so basically if this was called in uh you know if this entire thing was called in um three zero two one zero so this zero let's say this is the part of three zero two one zero zero then when you return this for you know three zero two one zero zero then you can see that it's returning the value 4 only so as you can see this c is only being returned once as you can see in our uh this also helper function also now it's getting outside but yeah you can see this line is only hit once only 4 was returned once then it's just passing the 4 above in the above calls that is what is happening special pattern how to pass is a pattern how to pass a number to above calls how to pass a value not just a number how to pass a value to above calls 4 is returned you can see 4 will be returned to every single value so as we see in the diagram as well let me bring up my whiteboard so it's going to be waiting for this it will be waiting for this so i can just write it over here special example to return value to to return same value to above function calls okay it's going to wait for this it's going to wait for this it's going to wait for this it's going to wait for this this is going to be like okay i have the final answer it will return 2 to this it will uh it's going to be like okay answer is 2 it will return to this answer is 2 return to the answer to answer is 2. that's it you can also use without this like the you know taking the outside variable you can do that as well um it's very simple just take an outside variable like we did with the previous example and yeah that's it let's move on to the next question okay so that was an interesting pattern to count the number of things okay similarly in this step also you have to count the number of steps to reduce a number to zero is very simple question it says that you're given a number uh you know number and you have to find the number of steps to reduce it to zero what steps we can take we can take two steps if the number is even divided by two otherwise subtract one from it no problem no problem i can do it very simply i can make a helper function i can uh yeah let's let's do that okay so i can say public static void mean this will go over here and i can just say return helper you should not have this doubt like kunal why are you taking helper whenever you want to because you all your doubt about which variables to include in the argument of the function in recursion that is already cleared hence you should not be having because we are i already covered it in the first lecture of the recursion introduction to recursion that is why we are taking a helper function okay because we need to pass these values in recursion calls and i can only pass values and recursion calls when i am putting it in the argument that's why i'm using helper function initial number of steps 0 for example okay create a new method helper total number of let's say steps okay what is the answer for this so if the number is zero return the total number of steps that's it and um dividing the number by dividing the number by 2 is one step subtracting 1 from this is another step so basically if the number is even so if the number is even in that case well this is one step but here i'm just saying divide the number by two so num divide by two steps plus one otherwise num minus one because if it's odd and steps plus one because this is also one single step like subtract the number by one divide by number by two is also one step that is it coil paste this should work okay let me submit this let's run the code that's it submit how easy was that even though the question was easy is important because this is also doing the same thing if you want to look at it in the whiteboard we can we can do that as well no problem okay so for example the number is given to you let's say something like 41 okay 41 is given to you so you have to find the total number of steps let's say initially it's 0 so 41 is what odd number okay if it is odd number then it's gonna be like okay increase the number of steps by one and um reduce this number by one because that's what the question says number will now be 40 function call number is even okay increase the call by one reduce the number by half that's it okay increase the number by one reduce it by half because it's even okay again it's even reduce it by half no problem this will keep on increasing by one this will now be five it's odd so it will be like 4 no problem okay now this will be divided by 2 2 6 and then it will be 1 because divided by 2 1 7 this will be 1 minus 1 0 8 total 8 steps for 41 total 8 steps are required how how simple is this right why did i not like i did explain it in detail like you know you can see i debugged it like on pen and paper and it's pretty straightforward like what else do you want me to say in this it's literally like the same approach we did previously right so you can see like if i try to put um a test case of what 41 over here and i try to run this let's see what the answer will be should give me eight getting it all right so this was the recursion easy questions video hard questions all the ones that i mentioned previously will come if you want to show the support to channel make sure like share and subscribe like like right now and comment right now i would highly appreciate it because if you comment then other people will be able to see this so it wasn't much about let's say the easy problem but more about the patents because if you're new to recursion so please make sure you check out the assignment link in the description you can also check out various platforms where you can find recursion problems like hacker rank and lead code and stuff all the links are in the description notes you can find it in the description code samples you can find in the description and i'll see you in the next one [Music] bye

Channel: Kunal Kushwaha

Views: 349,869

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, recursion playlist, best recursion tutorial, recursion basic questions, recursion level 1 questions, recursion questions, recursion tutorial

Id: JxILxTwHukM

Length: 73min 22sec (4402 seconds)

Published: Sun Oct 03 2021