so before starting this video i'd love to thank the sponsor of this video which is code studio now if you are willing to practice uh interview problems topic wise this is the place where you should look for because core studio has over 2000 plus problems and has all the problem solution in c plus java as well as python if you're looking for a guided path then you can find for python for dbms for object oriented programming operating system computer networks system design web development any other thing that you're looking for you'll find guided paths for
every other thing over here also also if you're looking for any top company questions let's say if you have an interview at amazon if you're looking for amazon questions you can get all the top amazon coding questions via tag and all the solutions in c plus java as well as python also if you have an interview schedule you can read their interview experiences where there are 600 plus interview experiences from companies like amazon microsoft adobe google etc so what are you waiting for code studio has a lot of free resources for interview preparation the link
will be in the description make sure you check it out hey everyone welcome back to the channel i hope you guys are doing extremely well recursion yes one of the toughest topics for the beginners is what i'm going to start today so it's going to be an entire playlist do you need to know any prerequisites yes there is a slight prerequisite uh you should be knowing what is a function yes what is a function like how do you write a function to add two numbers you should be knowing that much if you know how to
write a function to add two numbers that is more than enough to watch this playlist well this playlist be in c plus plus or in java doesn't matter just watch this because i'm gonna write pseudocodes and i'm gonna write i'm gonna explain the entire concept so language will not matter c plus plus java python doesn't matter okay so to start with what is a recursion let's read the first line when a function calls itself very important when a function calls itself that means if i'm writing this function and inside that this function inside this function
there is this function being called again so this is what is the definition of the first line so in order to understand this first line in depth how does it work and everything let's take a super quick example to print one using a function like using a recursive function and once you have understood how recursion works then we can understand the second line which states until a specified condition is met so generically there is a main if you're using java that's a public static void bin if you're using c plus plus it's an int so
if there's a mean and i'm saying a function let's assume i write the function as f okay this is what i'm calling and the f function is a void f function which says hey can you please print one in c plus plus it's gonna be c out in java going it's going to be system dot out dot printer and i call the same function again so how does the program runs first the program comes to the inter main the execution then it comes to the f and whenever you're calling a function it straight away goes
and calls this function void f okay so i am going and calling this function void f now the void of goes and prints this line one yes it executes this line one so i can say if i'm having if i'm having an output screen on that output output screen at this moment one will be print okay after this this line is executed which states calling of the function like calling of the self function f so how will this work well it will it again call back like this or how will it work it eventually calls
back the same function but in order to understand in a much better way what i'll do is i know like if i just write it over here there's a problem so i'll just create a replica of this function and i'll write it over here okay so i'm calling the replica of the function print one and again f so this f again calls the same function so basically it calls the same function again because this function is in your memory right so it calls the same function again and again this first line yes again this first
line is executed so again there will be an output of one and again after this this particular line will be executed so how will this particular line get executed it again calls the same function in memory so if i write down the f function again print one f again so this f will now go and call it perfect so again this line will be executed print one so again you print it one and again this line will be executed which again calls one more uh same function in the memory which is avoid f and again
it prints one and after that again calls f so this if you write the program this keeps on going for every day why because there is no stop condition yes there is not a condition where you say okay wait no more going to call me again and again and again there is no such condition thereby if i keep on writing if i keep on writing this will keep like uh sorry uh this will keep calling someone again this will keep calling someone again this will keep calling someone and this will keep on going forever so
it's a non-ending recursion or i can say an infinite recursion because you're calling the function again and again and again and there is no specified condition mentioned where you say that hey listen now you're gonna stop so if there is no specified condition mentioned it's gonna fall under an infinite recursion goes and calling goes on calling so if i show you this in my code editor by the way uh this is a sublime text editor that i use if you want to use the same format you can use my watch my video how to install
a sublime text so this is uh for sublime text this is the int main you can write it in java as well print print is calling c out of one which is again a print statement and again print so if i run this if i just have a run on this what will happen is it will print unlimited once till it runs out of memory and throws a segmentation for because it just see it it did print so much but after this it did ran out of memory because the program cannot keep on running keep
on running so this is what we call as stack overflow now what is stack overflow let's understand let's come back to the code so if i show you the code this was the mean correct this was your main and this main called this f write this mean call this f and after this this f called the sky so this f is this f is not yet completed this function call is not yet completed so it will be waiting in the memory correct so the weight so there is a stack yes there is a stack you
don't need to know any specific definition of stack just you can just uh take it as a thumb rule there is a stack whenever you uh read uh data structure algorithms in the next chapters you'll understand what is the stack but let's understand this function call yes this function call calls this f which indirectly calls this so this function call is waiting why because this function called has called this so this will wait where does this function call wait i can say this function call waits in line number two because the line number two has
been called and it is waiting now this function called is called over here you're calling this guy if you see you're calling this guy so apparently another function call with line number two is weight now this function call is called again this guy is called so another function call at line number two is waiting so if you just keep on calling them yes if you just keep on calling them again and again and again so these particular function calls will be waiting in memory will be waiting in memory because they are yet not completed now
when do you call a function to be computed if the last line has been successfully executed but this has not been because because this call this guy hence the last line has not been completely executed so this is the weight this weight is what we call as stack overflow now remember if you keep on calling if you keep on calling like in the example in the sublime text you kept in calling it went print one print one print one and at the end it stopped at five two three uh zero three seven like it's it's
uh compiler independent so in some compilers it might go beyond that so it did stop why because this particular stack space would be keeping f yes would be keeping another f would be keeping another f would be keeping another f but this has a specific memory it cannot just keep on keep on compiling up a lot of function calls because these function calls are yet not completed so it cannot just keep on piling up in the memory so that is when the segmentation fault happens and it's commonly known as stack overflow when there is numerous
function calls waiting due to recursion because you call the recursion so one function call was waiting you got another you got another you got another so it kept on waiting this is what we call as stack overflow got it so this is why uh infinite recursions are not written because because you'll end up having stack overflow and this is the stack space like these function calls are waiting so in short this is uh the definition of the first line definition when a function call calls itself i hope you have understood how the function call calls
itself now we are going to understand until a specified condition is met what does this mean now if you carefully observe we call this then this guy called this then this guy called this then this guy uh this guy called this then again this guy called this then this it will keep on going but there has to be a condition where you stop calling now that condition is something which is known as base condition yes base condition so let's quickly write down the function so assume i'm writing an f okay and just assume there's a
global variable i've kept it as count equal to zero a global variable okay and over here i'm writing print count and i'm doing a counter plus plus and i'm calling the function okay now if i keep on doing counter plus plus what will this function like i have already told you from the main if i call this function what will happen can you think what will happen yes i think you can this function call will ultimately call this guy then the print of count will happen and what's the value of count initially zero so the
output screen will print zero correct the output screen will print zero next counter plus plus will happen so the counter value will change to one and after this this function will again be called to f of 0 and again print of count will be called but this time counter value is 1 so 1 will be printed again you will do a counter plus plus so counter is increased to 2 again you will call this function and again this will call someone else so it keeps on going like this and you'll be doing print count counter
plus plus again and again f so you keep on doing and again print of count will print the next uh two counter plus plus will make it three and again this will call this will keep on going now you need to stop it somewhere so the condition that you use to stop it is known as the base condition yes the condition that do you use to say that hey listen you're no more gonna call it you gotta stop so assume i say that we're gonna print only uh up till three assume i'm saying you are
going to only print up till three so how will you modify it so you'll basically say function let's understand how this works right at the starting right at the starting of the function you're gonna say initially the count is zero you're gonna say if count is equal to equal to four i am going to return okay i am going to return i'll explain you this as well i'm going to return else i'm going to print count i'm going to do a counter plus plus and i'm going to call the function and in the main yes
in the main i'm going to call this function so if i ask how will this work let's understand so let's first keep the output screen and let's see how this works so i'm saying function this function is called i mean so it goes and calls this particular function what is the first line counter is equal to equal to four is it counter is zero so counter is not equal equal to four perfect next goes to the next line which says print count what the value of count the value of count is zero so you print
zero correct next counter plus plus that means counter becomes 1 this line is executed next function has been called so in the stack space this function will be awaiting this function will await in the stack space so in the stack space this function which is the line number line number one two three four five in line number five this function awaits why because it goes and again calls the same function in the memory which this time checks is count equal to equal to four and then returns print again the same thing count count the plus
plus f this time is count equal to equal to four no print count counts value is one so to make uh things simpler let's keep count as uh two so that we don't have to print a lot of times op count as 3 count is 3 let's keep count as 3 so that we don't have to print a lot of times so counter is printed again counter plus plus so this line has been executed function has been called so the moment you call the function this guy yes this guy goes into the stack space saying
that okay another function call at line number five awaits to be completed so you again go and say f of if counter is equal to equal to 3 is it counter is 2 so it's not so this line is still not executed you will print counter then you will do a counter plus plus so print counter will be executed prints counter plus plus makes it three and then again you'll call the function okay now this guy will again go into the stack space saying i'm still awaited i'm still awaited to be completed and this time
this function call will again call some other function but this moment counter equal to equal to 3 and counter is if you carefully observe counter is indeed his counter is indeed three counter is indeed three so you can say that this line yes this line will be executed and you will see return and you will say return thereby all these lines like all these lines will not be executed all these next three lines will not be executed and the moment you return this function is terminated remember if you're writing a return statement inside a function
the function gets terminated then and there so this says okay i'm over i'm over so this function called called this but this is over now the moment you come over here this guy gets out of the stack space saying okay it's time to be executed so this line is over now and this time it comes over here and now it goes back why because the function call is over if the function call is over you can directly go back next it comes over here again you can say this is done again goes back because this
function call is again over now this is also completed goes back to the f and this line gets completed so this is at the end completed so what happened was you you called called called called and this guy said i'm over went back went back went back this is what we call as a specified condition because you specified that counter has to be three only till then keep calling keep calling the moment uh the moment the counter was three if you carefully observe over here the moment the counter was three you said stop and return
you x like you stopped it you no more called this function line because you stopped and due to that stoppage the other guys also completed their function calls and this time there was no stack overflow because you did not call any further than three recursion calls so this stop condition is what we call as base condition now remember there can be a single base condition there can be a multiple base condition i'll be talking about all of them in the upcoming video but i i'm assuming you have understood uh the entire stuff i'll try to
code this up so if you see the code now this time what we will do is we'll keep a counter variable as zero okay and what we are doing is we are printing count and we have something like count is equal to equal to three then you can uh simply return or else you can see out count and do a counter plus plus this is the code now let's run it this time so if i run it this time you'll see just 0 1 2 being printed because print went on and called the functions and
this is the simple drive now what is the recursion tree there is something in recursion which you will be hearing a lot recursion tree now if you carefully observe in order to explain you i wrote the entire function then i again wrote the entire function then again root the entire function then i again wrote the entire function but will someone do this every now and then no so this is basically truncated into a very simple thing what we call as a recursion tree so basically i'll say the first function was called which is specifically uh
this guy and then this guy called f so this guy again called f then this guy again called f and then this guy again called f so again called f but this guy returned this guy if you carefully observe this guy returned so what you'll do is you return so you went you went you went and you returned and you returned and you returned so instead of writing the entire function we basically represent them in terms of f okay and that is what we call as recursion tree we'll be talking about depth and record like
i'll be doing a lot more problems so you'll understand what is the concept of recursion tree so basically uh the same function call is what i've represented in smaller uh func smaller representation and that is what we call as uh recursion tree so in order to summarize the class i hope you have understood everything like what is a recursion like calling the function within itself infinite recursion after that you have understood what is a base case the moment you say that hey listen you are not going to perform the below lines you go back there's
no more no more recursion being called go back so that is what the base cases you also understood what is a stack overflow a stack space stack space is the space where the remaining non-executed functions like non-completed functions rather because this function this guy was called so this function was yet to be completed so stack space stores the yet to be completed once and there is something which is known as recursion tree it's basically the diagram in which the function calls someone then that guy calls someone it's basically a shorter version of the diagrammatic explanation
that i gave you so i hope you have understood all these three things okay so in the next video i'll be uh doing couple i think three or four problems i'll be learning recursion in more depth so just in case you have understood recursion in entire depth like a theory concept please please please make sure you like this video and if you're new to our channel please do consider subscribing and yes if you haven't yet checked our strivers hd sheet the link will be in the description please check it out because a lot of people
are getting placed using that particular sd sheet and yeah with this i'll be wrapping up this video let's meet in the next one where we will be solving some problems from recursion [Music] don't ever forget
