C_104 Recursion in C | Introduction to Recursion

so in the series of learning c programming from this video i'm going to start recursion in c this is very important topic in c and generally in gate exam you know you find questions on recursion right and during interview also they used to ask question from this topic and you can say it's a little bit tricky or you can say tough for the beginners for the students who are you know beginners in a programming language who are beginners in c language they'll find this topic very tough but it's not like that if you got what is recursion the basics and how we are going to solve the programs which are using recovers in the process you will definitely say that it's not that tough right so we'll discuss everything about recursion in this video we'll see what is recursion and we will see a simple program using recursion right but there are many things about recursion like types of recursion direct and indirect tailed and you know known tailed advantages of records and drawbacks of recursion why we use recursion and some problems also everything we will discuss recursion from the basics right one by one in later videos so this video is like introduction to recursion right but before that just want to tell you one thing if you are preparing for gate 2023 exam or will be preparing for gate exam then an academy is going to start a batch rohan for gate and esc from 13th of october in this course the top educators will be covering all the subjects of c s and i t which will help you to prepare for your gate exam the scores include preparation strategies some tips and tricks practice questions numericals along with the detailed explanation of the concepts and you know this course will be covered in both hindi and english but notes will be given to you in english only and you can you all your doubts will be clarified in the doubt clearing sessions in the course right but this one is paid but if you will use my code jkl10 you will get extra 10 discount on your paid subscription one more thing they are also going to conduct a combat it's like the ultimate scholarship test for gate and esc aspirants which would be on 17th of october so in this contest you will get the original and challenging gate questions you will get 20 questions and time limit would be 60 minutes you can assess your preparation in just 60 minutes and you can also see where you are standing among the others using the live leaderboard that would be updated after every question and if you take it live you'll also get a chance to win some exciting awards the detail you can see on my screen and you can take this test for free you just have to enroll the enrollment link i'll put in the description box of this video just have to go to that link scroll down pick up the right test for you and just click enroll and use my code jkl10 to unlock the test and there is one more great offer for you on an academy if you subscribe to 12 months of an academy gate or esc plan then you will get extra 4 months means you just have to pay for 12 months and you will get 12 plus 4 months for your preparation you can see the detail of the price on my screen so all the relevant links and the code i'll put in the description box of this video if you are interested you can go and check out now let's discuss what is recursion in c first of all what is recursion it's simple when a function call itself then it is called recursion see we have discussed like this is main function and here we are calling a function suppose add we have one function add we are calling this function here right and here we have suppose uh you know add and the definition of this function and before we have prototype like void add something this kind of thing so this is what function calling this function we are calling in main function right so this is what calling function this is what cold function but but if i write something like this i am writing void and this is i'm writing suppose definition of the function here i am writing some code and in this function itself here also i am writing some code this is what function calling i hope you know the syntax of you remember the syntax of function calling so this is what function calling and where we are calling this function add the same the same function so the same function is calling itself means this function is calling itself this process is called recursion right and this the function can call itself directly or indirectly that is why types of recursion comes direct recursion indirect recursion tail records and no tail records and that will discuss in next video right this is like simple introduction to recursion so because there is what when a function call itself directly or indirectly that thing is called recursion that process is called a course and that's it and this this function is called recursive function the function which is calling itself this function is called recursive function that's it i hope you got the difference now here we are calling in main this function but here this function is calling itself so this is called recursion this is no recursion this is simple function calling this is recursion right like suppose uh let's take a simple example suppose in my class i have a student uh having named rahul so i'm calling rahul like rahul but rahul is not responding again i'll call rahul this time also rahul didn't listen and he's not responding again i call rahul and this time rahul responded yes ma'am so now like suppose i that i'm one function rahul is another function so i'm calling rahul and when rahul will respond just stop that's it right but suppose i am calling myself so in the previous case the termination condition was when rahul will come to me i'll stop calling rahul right and suppose i have cold travel three times and after that rahul came to me and i have stopped calling rahul but i myself calling like jenny i'm also jenny i'm jenny and i'm calling jenny itself so i am jenny only so how jenny will come like i am calling jenny but i am jenny only so no how jenny will come to me so when i'm going to stop calling jenny i'm calling jenny jenny jenny but jenny is not coming because i myself is you know jaime so i myself calling no i'm calling myself so this is what recursion but now jenny is not coming so i'm calling jenny jenny jenny so this would be an infinite loop when i have to stop so this thing is very important when the recursion have to stop the termination condition or the base condition in the recursion this thing is very very very important the base condition or the termination condition so here i can you know put a condition like after calling jenny five times i i'll stop so i'll call jenny five times jenny journey journey and now i'll stop so that is what the base condition when you have to stop the recursion that is the base condition that is the termination condition of recursion and if you will not put that base condition properly then your program would be an in fine in in finite loop maybe it will show some runtime you know exception or infinite loop or undefined behavior it will show so you have to put the base condition very very very carefully this thing is very important when you are writing a program using recursion the base condition see let us take this example if i am writing a program of you know finding factorial of a number so i hope you know if i write 5 factorial 5 factorial means how to find 5 into 4 into 3 into 2 into 1 is equal to 120 right so 5 factorial what i can write 5 into 4 factorial that is also fine right 4 factorial what you can write 4 into 3 factorial that is also right again i can write 3 factorial i can write 3 into 2 factorial that is also right 2 factorial i can write 2 into 1 factorial that is also right right now 1 factorial is 1 or again i can write 1 1 equal to sorry 1 into 0 factorial 1 factorial you can write 1 into 0 factorial right so ultimately it means n into n minus 1 factorial right n is 5 so n into n minus 1 factorial this is what i am doing and again suppose here i am again 0 factorial means 0 into minus 1 factorial then minus 1 into minus 2 factorial and again it's going on if you will not put the termination condition you have to identify where you have to stop where you you are going to stop when when here or here also you can stop when n becomes 0 right because 0 factorial we know it's 1 0 factorial means 1 now you have to stop we will not move forward further we are not going to move here we are going to stop right or you can stop here like if and you can also put this condition if n is equal to is equal to 0 means stop now 0 factorial means 1 so from here obviously what we will do we are going to return back so we are we are going to multiply this 1 then this 2 then this 3 then this 4 then this 5 and ultimately we will get answer 120 so we are moving forward as well as after finding the base condition termination condition in the same process we have to move backward like this like this and from where you have started there you will have to stop now and after that you will get the result so what is the process behind recursion means we are finally you know you can say dividing a problem into smaller one we have divided this for 5 factorial into 5 into 4 factorial the smaller problem the 4 factorial is 3 into 4 into 3 factorial another smaller one because 4 factorial then three factorial this is smaller one then again we have divided this problem right and add some we have added some base condition right and that's it that is what recursion right so here this thing is very important where you have to stop otherwise you will go forward and that would be an infinite loop maybe the stack overflow overflow problem you will get generally you will get stack overflow problem when you are writing from you know programs using recursion because you do not put the right condition the base condition the termination condition here the termination condition is n is equal to is equal to 0 you have to stop or more precisely i can say if n become less than equal to 1 then stop if n is 1 here also you can stop because 1 factorial is also 1 so no need to move further right here also you can stop and you can move backward like you can multiply 2 into 3 into 4 into 5 that's it right so that is you can say this is the base condition so here if if i put a condition n is equal to is equal to 10 the termination condition by default i have put n is equal to is equal to 10 then you have to stop and i am finding factorial of 5 so is there any chance of getting n is equal to 10 in this process no so ultimately you will move forward forward forward and this would be an infinite loop this condition you will never reach to this termination condition right and in this case you will find you you can find out the error like stack overflow problem because every time you are going to call this function the memory would be located right and sometimes the memory would be exhausted the stack memory would be exhausted obviously out of you you know run out of memory so at that time you will find that stack overflow problem right so you have to put this termination condition very carefully in because in your recursive programs so i hope i guess you got the idea about recursion right basic idea a function calling itself directly or indirectly that thing is known as recursive in c right so let us take a simple example and we will see what kind of output you will get when you will run that program so now this is the you know simple program of precursor why recursion see we are having a function display and in this function only i am calling display again so this is what function calling itself directly right so now how it will execute it will be executed and what it will print the process behind recursion see you have to follow the steps only you have to understand this process very carefully if you got the process of executing the program having recursion recursion would be like it's very simple for you so now first of all the control will go to the main function so now from the stack memory one stack frame or activation record of that function would be you know uh hold in that memory so one stack frame would be allocated to this main ah let's say here this is from the stack memory here we have main one frame for main so here what would be stored whatever the local variables here that would be allocated here right now here we have n is equal to 3 and many more things also right like you know from where this function has been called and what function it is calling many things it is going to store but here for the simplicity purpose i am just going to record here the local variable so here we have n so we have n and n is equal to 3 so now next statement is display we are calling sorry display n obviously we are passing n you can pass three also but here are passing variables so what value would be past three right so now here from here it is calling display so means for display also one frame would be a located the activation record for this display also would be stored here in the stack so memory would be located obviously when you are going to call this function so this is what for display but here for display n3 for display 3 because anyway here we have n3 so in this display function we have a local variable the copy of these variables no these variables would also be allocate some memory n is equal to here we have 3 because 3 would be passed check the condition and less than 1 no this condition is not true so else part in s part we have three statements so this thing you have to you know check very carefully here we have three statements so first is printf so first we have printf so this printf will print what n so n value here is three so it will print 3 on the screen it will print 3 now next statement is display here we have display n minus 1 n minus 1 means 3 minus 1 that is 2 so here we are going to pass to and again it is going to call display itself so when it is going to call itself obviously above this one one more frame would be allocated to this function every time the function would call itself one frame would be allocated to that and these variables the local variables the the copy of the local variables would be here so here this display we are calling but here we have n 2 this is for display 2 right because from here we are passing 2 n minus 1 2. so here we have n but in this n we have 2 right check the condition if and less than 1 not true we are going to into we are going to enter into else part in else part again we have three statements see here here also we have one more statement printf n but this statement is still pending we haven't executed this print we have executed this printf only because before this we are calling this function so still this is going to be executed when i'll tell you so now here we are calling display one printf is there which is printing n so it will print two so in the on the screen it will print two now again next statement is display what we are passing n minus one n is two so we are passing one so and this printf is still still pending whatever is pending i am putting that into rectangle so display one so we are going to call the display one so again one frame would be allocated to display one this is for display one here we have n n is one so less than one no in else part we have three statement one is printf it will print n that is one so it will print one on the screen again we will call display display one minus 1 that is 0 and here also we have one more printf which is pending this printer so display 0 means again for display 0 we have this frame display 0 will be passed but this time check the condition n less than 1 yes condition true so here we have n 0 this condition true now return we are not going to enter 12 part return return is where simply this is return return means where the control will go the function which are calling this and from where we are calling this function display 0 from display 1 from here we are calling right this process you need to take care when you are moving backward so this is the base condition now you have to move backward in the same direction so now return back so from here we are going to return back to here i hope you can see this yeah from here we are going to return back to here display 0 is there any statement after display 0 yes we have the statement printf n so what it will print in this in this stack frame what is the value of n one n one so again it will print one right and after printing just closing of else and after this closing of this function right after closing of this function obviously the control will return but where it will return from where you are calling this function from where you are calling this display one this is display one so from where you are calling this display one from display to here so it will return the control here right now in display one also still we have one statement which is still no going to be executed so printf n what is the value of n here 2 in this frame 2 so it will print again 2. after that the control will return where from where you are calling this display 2 from display 3 so here we are going to return because here we are calling display 2. again this printf will print n 3 right and from where you are calling this display 3 from the main function so now after printing this we have returned to main and just exit from the main and that's it so this would be printed so this is the process of recording i hope you go to this is very simple you have to just maintain the stack frame that's it in the moving direction in the backward direction the same direction you will move if you are not going to maintain this one this is you know time you know lengthy process so while writing gate exam or any competitive exam in that case obviously we cannot maintain this kind of thing so simple method is also there that we will discuss in a next video with one more example properly right so whatever the you know extra things like the types of recursion and advanced advantages and dropouts of records and that we will see in the next video so i hope you got the basics about recursion so nice in the next video till then bye take care

Channel: Jenny's Lectures CS IT

Views: 187,741

Keywords: data structure tutorials, operating system, data structure and algorithms, jayanti khatri lamba, jennys lectures, jenny data structures, jennys lectures DS, jenny lamba, jennys baby, jennys lectures baby, data structures, recursion in c programming, introduction to recursion in c, what is recursion in c, what is recursive function, c programming tutorials for beginners, c jennys lectures, what is pointer in c, gate cs lectures, gate previous year questiona with answers

Id: KQZIBckWK-s

Length: 20min 43sec (1243 seconds)

Published: Tue Oct 12 2021