Intro to recursive functions in C

in today's video i want to talk about a recursion and what is it what is it used for and why should you consider it but first things first let's create a couple functions let's say here we have i don't know let's say we have f that simply prints hello from f right and then we have a function g and says printf hello from g all right and then you're like okay well i can call them in maze i can say f and then g and if i try to launch this i'm gonna see well both of the lines printed on the terminal here hello from f hello from g that works okay amazing but let's say i want to have g be called by f instead so that i only have to write an f call and i can write it here a g chord inside the f function and as a result we'll get the same thing all right it's just that well the order matters because g is not defined here so we should actually uh paste it here instead but we do get the same result now what happens well you know that f is a function and g is a function right we have here g being called from within another function well since g is a function can't we actually call f since it is also a function so that inside the f function we actually call itself can we do that well if we try to call f inside its own function and then call it firstly in the main function we're gonna end up with a recursive function and if we try to launch this you're gonna notice that it forever and ever and ever prints out hello from f to the point where crash is my program actually um yeah so that's something but it's not amazing because it's doing it forever and ever so what's the solution here for now let's forget about the g function we don't need it anymore we only have a function that is now recursive but it recurs it's recursive but it never stops executing now we know that we can pass arguments to our f function we can say here let's say in x and then let's well since we have to call it here let's pass x further down the line and inside the main function we can pass in whatever let's say we pass in 20 okay so that's working and let's say in the print f here in the function we say with x equals percent d and we actually print out the x value okay then what's gonna happen well if i launch this again i'm gonna get something but it's not great it still kind of uh breaks my id here but it does uh forever execute and it never really changes x is forever 20. okay but one thing is interesting here that we are not forced to actually pass in exact parameters that we have here inside our function so here since well we do get the x variable with its values we print on the screen but when you pass it down the line you're not forced to actually pass it as it is we can do any operations with it we can for example decrement it by one now what happens so if i launch this i'm gonna get again it's gonna forever execute but at least the x value is always changing it's always going uh lower and lower and lower below zero right so we started with 20 20 got into the first call of f we probably printed 20 but we didn't see it because it was way too fast but then we passed to the next call of our f function we passed in 20 minus 1 which is 19 so that got printed on the screen and then we passed in 19 minus 1 because at that point in the second iteration x was 19 then 18 and so on now how do we make this recursive function actually stop executing at some point because having a function that executes forever and ever basically nothing at this point it doesn't really help well we can have what is called an exit condition for our recursive function and we can see here if x is less than zero right so if we went into the negatives let's say just return what does that mean well that means that when x is 0 then this is going to be false so it's going to still print 0 on the screen and then it's going to call it with 0 minus 1 which is -1 and then the next time it comes along and tries to execute f of minus one then this is true and all the function does is just return print nothing on the screen and not call itself again so when i launch this you're gonna notice that the program actually successfully stops executing at x equals zero right so we have all the values of x from 20 to zero and then it stops this is the main structure of a recursive function we have here the main code whatever you do with the variable network you're working with then you have the recursive call so here you call the function that you're in right uh the recursive function itself with whatever arguments you have to pass in here usually they should be changed and then you also have an exit condition so that the function doesn't forever execute and there's the condition for me it was just that x was less than zero now this is all theoretical we don't do anything with these arguments we don't do anything with this exit condition we just print something on the screen but this could actually be very useful in certain situations now things actually get much more interesting if you start returning values from these recursive functions so suppose that instead of void we actually return an integral and well we're going to have to return in two paths here because we really have two paths we have this if which returns straight up and then we have this part which should return also something in here let's say we just return for example 0 right and then inside here what if we return the result of the next call down the line so we can simply say return f of x minus one that's actually valid because f well the compiler says okay well what does this return well this returns an integral right so calling f should give me an integral which corresponds with the integral that we have to return in the current function so that's all fine right now if i try to take the result of this and print it on the screen so say result equals net and let's say printf the result of calling f is percent percent d backslash n and we just simply say here result if i try to launch this now what are we gonna get we got 0 as a result now why is that well the answer is going to be more obvious if i for example call it with f of 2 because it's going to be the same for every single call of f so if i call you with f of two well i'm gonna get the zero here so first things first here the first call of f of two let's see what it does well it says okay x is two so definitely it's not gonna enter in here it's gonna actually print on the screen something and return f of x minus one so let's note that down let's say this is the return value that we get so return f of x minus one now we don't know what that is we're gonna have to execute f of x minus one but we know that x is two right so in that case we're gonna actually call f of one okay so this is the return value let me actually name it like so now f of one means that x is one okay then it doesn't enter this if it does print something on the screen and then it does f of x minus one well f of x minus one if x is just one is zero so this return statement since we have here return turns it into f of zero okay so f of one returns f of zero which what does it return so f of zero is x equals zero it doesn't enter here because zero is not less than zero it prints it on the screen we can see that down here and then it calls f of zero minus one which is f of minus one so we have here minus one instead and then once we get there x is minus 1 and it enters this if statement and it simply returns 0. so f of minus 1 is actually going to be 0. so of course we're going to get as a result 0. i'm going to do a small exercise with you on this topic uh let's say we want a function that what it does is given a number it sums up all the numbers from 0 up until that number so for example if i give it let's say number 4 it should give me 1 plus 2 plus 3 plus 4 which is 10. so it should give me as a result 10. if i give it a higher number it should give me a sum of all those numbers from 0 to that number how do we do that how do we adapt this f function to do something like that now we know that at each iteration iteration of this f function x is a different number and it goes down from the whatever x we give it first and then down to zero well that's perfect because in here we have all the numbers from zero to that number so if we give f the number four we actually get all these numbers but we're not summing them in any way how do we how can we actually sum them well we're going to have to play around with the return statement here and at each consider each addition an iteration of the f function well let's say we pass in here f of four right like we have up here okay the first iteration is going to have us at x equals four so it's gonna be for this addition right from the left to right and actually i'm gonna change the order the way i'm doing this addition so that it's like this okay and then we're gonna have here this be the first iteration and then we have an addition of something and that's something is well what this function does except for the number previous to the current one so instead of f of four it's actually a call to f of three and what do we have here exactly that so if x is four we actually get four minus one and that's three so we actually call f of three but we need to also add this value to the return to the return statement and that is well four is the current x value so i'm going to say here x plus f of x minus one all right and now if we try to launch this we will get a result that is correct we can get 10 right and if you pass the number bigger than 4 passing for example 10 we should get yeah that is correct for 55. okay so we did decide how to do all this but how does this actually work well you can always try to take a look at the first return value of the first iteration and keep on expanding it right so if we have here let's go back to four because it's simpler f of four is first call from the main function right so we go here f of four x is four all right and we print out something on the screen we don't that doesn't really matter but here what do we actually do well we do return x plus f of x minus one but what are the actual values well x is definitely four right and in here x minus one is four minus one which is f of three so we call f of three now we have to see its value what it is so we take a look f of three is when f is three when x is free i mean uh we print something on the screen and we say return x plus f of x minus one but this time x is actually free so instead of f of three we actually have x plus f of x minus one which is in this case three plus f of three minus one which is two and note here that we have different axes at each iteration of the function we get a different x variable just because they are named the same doesn't mean they are the same okay that's very important nice now we call f of two and we go ahead and take a look and we can see that it's again x plus f of x minus one but this time x is two right it's only that it's only there's a single x variable by the way that changes it's that there are as many x local variables as you have uh function calls or iterations of that recursive function right so f of 2 is going to be translated to 2 plus f of 2 minus 1 which is 1. okay and f of 1 well it's going to go down here again is going to say 1 plus f of 1 minus 1 which is 0. okay then f of 0 what it's going to do well it's going to go ahead and say okay x is 0 it's not going to enter here it's going to return well 0 plus f of 0 minus 1 okay fine and then f of 0 minus 1 is going to be just f of minus 1 which is gonna give us well since x is minus one is less than zero now it's going to actually go into this branch and just return a zero so you can replace this with a zero and there you go you have four plus three plus two plus one plus two plus 0 plus 0. so that's how we got to 10 if you actually add them all up you do actually get 10. now of course you can actually optimize this a little bit and not have this last zero here if you change this to be equal to zero so if x is actually at zero it should return zero that's going to be a bit better and it's gonna not have us add zero twice to our uh integral but this is how uh recursiveness works right it keeps on compounding to the same uh return value or maybe the same uh return values maybe there's an array that it keeps on adding to and it does basically the same step the same set of operations in this case it was just adding two numbers but it could be much much larger step with these parameters and at one point it gets to the end and that end is specified here this is where the operation ends and this is where i want it to stop because well for example for this operation right i have from four to zero i want it to stop at zero i want to keep adding numbers in the negatives and i want to see 4 plus 3 plus 2 plus 1 plus 0 parts negative 1 plus negative 2 and so on and so forth to infinity right i just want to stop at 0 and that is the stop the exit condition for our recursive function now there's all sorts of things you can do with recursive functions and i'm going to give you two homeworks that i think you should try doing because not going to take more than let's say half an hour at most right uh one of them would be to actually sum them up in a different way and that it only sums up either the odd or even numbers instead of four giving us four plus three plus two plus one it actually gives us four plus two plus zero it should be here we got six so uh the step should be two not just one how do you do that well we're gonna have to find out and another cool trick would be to actually get the sum of all the digits of a number recursively so for example if i give it a 150 let's say 156 if i give it 156 i want it to give me one plus five plus six which should be 12. now note here this is not the exact order of the operation that you might have uh to do but because addition is associative you can uh do that addition in any order but these two exercises i really think you should try uh at least try one of them it's not gonna be that tough that is for today if you do have any questions leave them down comments below or on our discord server the source code for uh this video will be found on our website link in the description below take care bye

Channel: CodeVault

Views: 2,251

Rating: 4.9540229 out of 5

Keywords: codevault, c (programming language), recursive, functions

Id: fXOOCpZyvwM

Length: 17min 38sec (1058 seconds)

Published: Thu Jan 14 2021