"Recursion" Introductory C Programming for ECE at University of Toronto

welcome back to 105 I'm re-recording this uh because I forgot to hit the stream button so let's get into it so this is probably one of the toughest things to get your mind around being Rec recursion so might have heard of recursion before or in math a recurrence relation but if you haven't a recursive function is just a function that calls itself so in order to actually solve a problem recursively we need two things so we need a base case so that is a simple solution that we know and then we need a recursive step and the idea behind this is we don't have to solve the whole problem we can assume the solution already works we just have to put the solution in terms of a smaller version of itself and then through the magic of computers well we can have that try and make the problem smaller and smaller and smaller and smaller until it gets to our base case and then it will go ahead and solve our problem for us so if you went and looked in the dictionary for the definition of recursion you might see something hilarious like this where the definition of recursion just says see recursion and this would not solve any problem because well if you were going to read it you see what's the definition of recursion well it's recursion what's the definition of recursion it's recursion so so this kind of looks like an infinite Loop and well we can get like the same types of things happen whenever we do not have our two rules coming into effect where you know our computer would just essentially run forever because it's basically an infinite loop it's just more of a roundabout way to get into an infinite Loop so you may have seen Fibonacci numbers before they're also an example of recursion so they are in math a recurrence relation which means that they Define it like this they say that the value of the zeroth Fibonacci number is simply just a zero then the value of the first Fibonacci number is just one and then they give you the recurrent relation so to calculate the nth Fibonacci number it is the nus oneth Fibonacci number plus the nus 2 Fibonacci number as long as n is greater than zero so we're just assuming positive integers so we could also write a function to compute F ofn and what that would look like is well if We're translating into C we know that we are Computing the nth Fibonacci number and the type of n would be an integer and well we could go ahead and see that the condition to use the recurrence relation is if n is greater than one so we kind of know we probably want to do some type of if statement so for recursive problems typically once you're starting out to it's easier to divide it into the base case and the recursive step so in this example to solve the calculating the nth Fibonacci number our base case could be assuming that n is going to be zero or above not no negative values our base case would be if n is less than two then just return n so that covers actually both of our base cases so if n is equal to one well one is less than two and then based off the definition should be one in this case we just return n which is equal to one and also if we're calculating the zeroth Fibonacci number which should have the value zero well 0 is also less than two then we could just return n which is currently zero so we would get zero so if you wanted to if you could write two different if statements so you could have two base cases so if n is equal to zero return zero or if n is equal or else if n is equal to one then return one and remember you should use double equals not in equals because you might get into trouble for that and then the other part of the solution here is the recursive step so if it's not the base case then it's the recursive step so we could just do else and then we just write out the recurrence relation and just kind of translate it to C so we return just FIB of nus1 n plus FIB of n minus 2 and we will revisit this problem a bit later in the lecture too so let's start with a bit of an easier problem first so we could also calculate exponents using recursion as well so assuming that we have n that can't be negative if we want to compute B to the power of n well that's the same thing as B * B * B * B just n times but if we want to think about this recursively the two things we need are the base case and also the recursive step which is solving the problem in terms of a smaller version of itself so well our base case could be there's a few possibilities here but one of our base cases could be if the exponent or n is equal to zero then we know that the result is just one so that could be our base case so if we see n is equal to zero we should just return one we could also have a base case of when n is equal to 1 we could just return B but in general you kind of want to have your base case follow like the worst case scenario so if we assume n is going to be zero or positive the worst case scenario is that well in terms of our correctness would be that n is greater or equal to zero so our base case could be B to the 0 equals 1 and then in terms of our recursive step so to calculate B to the power of n in terms of B to the power of something well our recursive step could be that b to the power of n is equal to B * b ^ of nus1 and nus1 well that's an instance of the same problem it's just a smaller problem so we just take our number B and then multiply it by B to the nus1 so if we we were to write that out in C looks like the same thing as a Fibonacci number so we would create a function called exponent which would take two arguments now so we have a b and an N which are integers and then we could write out an if statement for our base case so in this case our base case is n is equal to zero we could just return the value one and then for our recursive step well we just return B * exponent B so we don't change the base at all and then n minus one so we can think of another way to calculate the exponent just using something like a wall Loop or for Loop but in some scenarios we're just getting practice writing recursive uh recursive Solutions because some problems lend themselves to this much more than others so we can go ahead and see that here is my program if I implement it I went ahead and also used the version of C or of the version of main that takes some arguments that we type in just because I'm saving myself from writing scan F and then having to enter hit enter two times to use this program so here I just check if there are three arguments so the first is going to be the name of the program and then I'm assuming the next are two numbers so I'll just assume that the user is nice I will use our a2i function that we discussed in the strings function lecture that will go ahead and give convert that string to an integer and then I will just call exponent with BN that I get from the first argument and the second argument and just display the results now if I go ahead and run this I might see that you know 2 to ^ 4 well that should give me what I expect and give me the result 16 and now if I do 2 the^ 5 I get 32 and this seems to actually work as I expect so now let's evaluate what actually happens when we are calling to to the exponent of four and this is where my recording catches up so let's switch to that there we go oops so if we hit or sorry if we do two to the 4 well we would call exponent 24 that would go into our recursive case so it would go into that lse statement and it would do return well 2 * exponent 2 to the power of three so before that function returns that called 2 to 4 it has to actually compute 2 to the 3 so we would do another function call so this is another function call so I put it here on the stack to indicate that the other one is still active it's waiting for this one to complete so right here in the gray text that is what we're trying to compute and every box is a new function call that would have its own local variables in this case it would be B is 2 and N is 3 so to evaluate exponent 2 to the 3 that would go into the recursive case so we would get 2 * exponent 2 to 2 okay well now we have to figure out what exponent 2 the two is that is another function call so we call exponent 2 to the two then that gets into the recursive case again so we get 2 * exponent 2 to the one then it gets kind of boring so then we do have another function call with exponent or 2 to the 1 and then well that is 2 * exponent 2 to the 1 so we would call that and then mercifully this is our base case so in this case n is equal to zero so it would just get a one so it would return one so the function that called it gets a copy of one and this whole thing kind of unravels itself so then it would return and then in our 2 to the 1 function we would calculate 2 * 1 which is just two and then that is the result for 2 to the power of 1 so that would get returned for this function call then we have 2 * 2 so that would be four so that's 2 ^ of two and then it would get returned here and then all kind of unravels right so now here that four is returned it gets a copy of it so then we would do 2 * 4 which is equal to 8 which is thankfully to the^ 3 and then here well we would return 8 so then we would get 2 * 8 and then we'd get finally our final answer 16 so lots of steps it would be in that case what five function calls but we got the answer in this case a for Loop would have probably been less confusing but is there any questions about how this worked because it's going to get weird once we get Fibonacci going so we're all all okay until it gets slightly more strange okay so let's go ahead and run it make sure it works so here is that exponent code so here I just have my base case and my recursive step step oops and then if I go ahead and run it I could do to the power 4 something like that I get 16 seems to work to the^ 5 32 but if we implemented this with a loop I could probably do like one to the power of I don't know some large number and that would be fine it would just might take some time to execute right well let's see what happens here so if I run that I get a segmentation fall crap well I didn't even use malachow in the blue hell do I have a segmentation fault so one of your steps might be okay well I'll use valren and then I'll see says okay I have no memory leaks I didn't allocate anything so what happened so you try and scroll up and then you get a bunch of random text that's probably not so readable the only thing that you have any hope of reading is this thing called a stack Overflow so we know that kind of what a stack is it's where all the local variables are and in this case a stack Overflow means basically it ran out of memory so this is a very common thing you can encounter once you do recursive function functions because if there's too much recursion we essentially just run out of memory so I did what to the power of like a million or something like that so that would mean that you know a million called 9 called 999998 called that called that called that called that and well every function that is active has a b and an N at least so it has two integers so I essentially just ran out of memory because every function call needs its own variables so that is what a stack Overflow means basically just I ran out of memory so again like I said every time we call a function that function gets its own copy of the variables in C they store local variables on the stack so if there's many active functions at once so there I did to the power of a lot so if I was to draw that on on the slide I would run out of room because it would just call itself over and over and over again until it actually ran out of memory so running out of memory for local variables called a stack Overflow that is the name of the helpful website that you can get questions and answer to for programming questions um so they named it that because well this is a common enough error that is really hard to go go it means you have screwed something up because usually people get to recursion and then things start screwing up and then most programmers see stack Overflow a lot when they are starting out so common cause for stack Overflow more likely than not is infinite recursion so it's similar to an infinite Loop except in an infinite Loop just takes a lot of time it doesn't actually need more memory each time you go through the loop for recursive functions it needs more meory memory essentially every iteration of the loop if we were thinking about loops so we can actually likely run out of memory before we run out of time so this is far beyond the scope of the course so don't worry about if this part doesn't make any sense but there are like certain forms of recursion that are more that can be optimized more easily so we can rewrite some functions to use what's called tail recursion so it's a special recursive function that just has a single recursive call in the return statement you do not need to practice actually rewriting this this is mostly for performance so if we modify exponent well we could create an exponent that takes three variables so before we just returned a number well like in our recursive case we did like two times the recursive function so if we want to be tail recursive we can't do that so we create another variable here that's local to the function called accumulator that just keeps track of the current value so in our base case instead of returning one we just return whatever the final value we have is so it would do like uh 2 to the 2 * 2 * 2 * 2 if we did 2 The Power four then eventually it would be 16 and then we just return 16 at the end and this is our recursive case so we just do the calculation with the accumulator so we just multiply B by it and otherwise it looks the same as before so if we want to keep exponent looking the same well we have the base and the n and we can just return exponent written in this tail recursive manner by giving the accumulator one and then giving B at the end and the only reason why I show this to you is because compilers can optimize this function so if it's recursive a lot of people don't like writing recursive functions because well it wastes a lot of memory and you can get into the stack Overflow issue where if you just wrote a while loop or for Loop or something like that that would work better and you wouldn't have that memory issue so it's actually guaranteed that compilers and you'll learn this in like fourth year whenever you get to compilers but it's guaranteed that compilers will optimize this away so it will optimize away the recursive fall call and just convert that whole function into essentially a while loop so it would convert it to this for you so just start off in x equals accumulator so in our case we set it equal to one and then it would just go while n is not equal to zero and just do the recursive step over and over again so now our codee doesn't have a stack Overflow doesn't have that issue because we're not actually doing recursive function calls we let the compiler optimize it away for us and in this version maybe you can argue that the recursive one was more readable so you'd rather have it than this but for calculating an exponent probably just a while loop is going to be much much much easier to do but it's good to think of things recursively because well some solutions lend itself better to recursion than others so let's rewind a bit and see what happens when we call FIB of four so this one is a bit different than the exponent where in our recursive step we return FIB n minus 2 plus FIB or FIB n minus 1 plus FIB n minus 2 so we do two function calls here so if we actually want to evaluate something like FIB of four turns out it's going to be a lot of work to understand how your computer actually executes this code so gets a bit ugly so if we evaluate FIB of four well we call FIB of four and again I'll just write in the gray here what the function is supposed to be Computing so it's supposed to be Computing the fourth Fibonacci number so in order to compute FIB of four well that's the recursive step right it should return FIB 3 plus FIB 2 so we have to do these function calls so c will go ahead and it does function calls in left to right order don't have to know that for the course but in order to figure out how this actually works on your computer it's important to know what happens first so we will do this function call for FIB of three so we'll do that function call it'll get its own copy of N and we do FIB of three well that goes into the recursive step so it would return FIB of 2 + 1 right then okay now we need to call FIB of two okay so we call fib FIB of two FIB of two is equal to FIB of 1 plus FIB of 0 mercifully when we call FIB of one that is thankfully our base case right so it would immediately return one so that whole thing would evaluate to one and then it would return and give us the value one back for in this case FIB of one so it returns and now oh no well we still have to find out what FIB of0 is right so now we have to figure out what FIB of0 is so that is another function call to figure out what FIB of Zer is that mercifully is another base case so that just gets the value zero so it returns and then we can finally figure out what the second Fibonacci number is so it's uh 1 + 0 so it would figure out that that is one okay great so that was figuring out what FIB of two was so that would return the value one okay well now we have to do the other half of it now we have to do FIB of one okay well that's another function call so we call FIB of one mercifully that is another base case so that just returns one and then well that returns one so then we can figure out what the third Fibonacci number is so it's just 1 + 1 so that's two so now that returns right so that is fib of three so that returns oh God but now we have to figure out what the second Fibonacci number is so that is another function call so this whole thing kind of goes again so we have FIB of two okay well that's a function call oh that's our recursive case so we would return FIB of one plus FIB of zero okay so then FIB of one that's another function call mercifully that's our base case so that's just a one so then that would return okay yay so now we have to figure out what FIB of zero is again so FIB of zero okay that's another function call that goes to the base case verely we know it's a zero then it would return and now FIB of two is done so we get one then that returns now we can finally figure out the fourth Fibonacci number which is 2 + 1 which is three yay wasn't that fun so any questions about how that works other than it seems like it takes a long time to figure it out so let's see so here is that implementation and just as a review for the last one instead of just asking and doing scan F I'm just using that other version of main that takes another argument that I can type to it just because I don't feel like hitting enter two times so I check that there's two argum ments and then use aot to convert the first one to an INT and I assume I'm being nice to it I'm just going to print the result of calling Fibonacci on whatever that number is so if I call FIB of four it was a lot of work for us to figure out all the function calls and you know how they work and who calls what and what values and when do they stop but computers are fast so it just gets three quite readily and works so if we did computed 10 we get 55 turns out it grows pretty fast 20 we get 6,000 something like that seems to be pretty fast computers are quick but if we get 40 you might have noticed that took a little bit of time maybe 44 44 took a bit of time it was a bit slow and also for this one we could just write it in a for Loop to and it would be way faster and way easier to actually compute but again we're just kind of practicing uh practicing recursion even though doesn't really make sense this would be a lot easier to just do in a for Loop so any questions so far about evaluating that yeah is there any way to know how much slower will get depending on how many yeah so the question is do we know how much slower it will be depending on how many steps it will get so you can kind of guess it's going to get like in this case almost two times slower every time because well if I have to compute 44 that means it has to compute 403 and then 42 and then if I have to compute the next one well then I have to compute 44 which is going to take as much as what I ran before plus a 43 so not quite two times slower every step but gets up there so if I do like 45 probably pretty slow yeah oh crap so oops so if I do 44 One Mississippi two Mississippi takes a bit of time if I do 45 One Mississippi two Mississippi three Mississippi four Mississippi okay so took about twice as long because essentially has to calculate everything it had to do before and then do it all again for the next number and then you might imagine this might be like exponential so I have to compute one side and then the other side and then I have to do it again and again and again and it's kind of a pain so that leads us to our next thing which is we can signif whoops wrong thing leads us to the next point of again so this part again is beyond the scope of the course for this course just writing recursive functions is good enough for us we'll get some more practice as it goes on but just so you know you can significantly speed this up without actually changing it from being recursive with something called memorization which is just a fancy word for caching and CA caching is just a fancy word for just saving values that you don't so you don't have to recompute them so even with FIB of calculating FIB of four well we had to calculate like FIB of two a lot of times and we had to calculate FIB of three once and FIB of two a bunch of times and then a lot of well we didn't have to calculate the value for FIB of one or FIB of zero but we could change our PR program a little bit so we don't have to go ahead and recompute them over and over again so one optimization we could do that you could probably implement right now but you don't have to for this course is just I could just remember some old value in an array and then if I've already calculated that value before I can reuse it again instead of recomputing it so this one took I almost counted like five Mississippi it was really really really really really really slow so I wrote another version of it that just uh that just saves the value that is computed already so it just reuses it over and over again instead of doing the whole recursive nonsense over and over again and if I run that oops that is the same function so if I run my optimized version boom look how fast that was so there are some techniques you might employ that some problems will have to be recursive and they might be slow and this is one technique to speed it up again just something to think about don't have to do that in the context of this course at all but it will come up you know probably in your next programming course so recursive functions are basically just another tool some problems are easier to think about recursively especially if you're like more of a matthy person that likes proofs and all that stuff was never me so it took me a bit to figure out this recursive thing but some problems believe it or not are actually easier to solve recursively so it's good to get some practice trying to get yourself into that mindset so typically recursive functions are going to take more space to execute tail recursive functions can be optimized again don't have to know that for this course but in your career that might be a good thing to know and try to write for so it's important to practice so you can go ahead identify these types of problems and be able to solve them and the main two things are given a problem you probably want to identify a base case so something you know a value for given one of the inputs and then you also want to create the recursive step so you want to solve the problem in terms of itself sorry you want to solve the problem in terms of a smaller version of itself so typically it'll be you do one thing like you just take one step and solve that so let's think about that that for more practice can we write a recursive function to calculate factorials so sit think about it for a few minutes and then we will try and come up with the code ourselves together so we're trying to calculate factorials and like for an example well the like four factorial would be 4 * 3 * 2 * 1 so take a minute think about how you would solve that and write that as a recursive function so these are the types of things that would be on exams and stuff like that like for this course most of the problems you'll see you can probably solve with like a wall Loop or something like that because well you have to be able to write them during an exam and recursive stuff takes practice so generally you'll probably get some question on the file will be like solve this problem with a recursive function all right I'll give you a few minutes for that and then we'll try and think about what the steps would be all right yeah I can't hear you sorry okay so I'll take you first so you you you will start half of it so the first thing we need is a base case that has been answered up there so our base case would probably be well if we're Computing like n less than two so if we're Computing the factorial we assume no negative numbers if we're Computing one factorial or zero factorial well they're defined as just being the value one so that is our base case so I'll get someone else for the recursive step so that is one thing we need so the other thing we need is our recursive step so anyone with the idea of what we should do in the recursive step so how do we solve factorial in terms of itself yeah yeah so my recursive step I could write in an else here or return doesn't really matter so in terms of solving in terms of itself well let's assume the number is four so in order to calculate four factorial well that's just the same as doing 4 * 3 factorial so if we wrote that in terms of C function calls our recursive step would be to return n * nus1 factorial which would just be factorial of n minus one everyone agree with that so turns out this one might be easier to think about than doing all the for Loop and everything like that so if we do I don't know 4 factorial 24 10 factorial some large number seems to work cool that was faster than I expected any questions about that yeah oh so the questions can I do a recursive macro yeah I'm not sure if the c pro pre-processor lets you define recursive macros I'm actually not sure I don't think so it's fairly straightforward and simple and that would probably complicate it so I don't think you can but can do recursive functions no problemo so any questions at all about factorial all right wow I outdid myself so here's the solution for you so same thing we developed so important thing so we will get a much much much much more complicated example in the next lecture I even have fun toy props that I can bring in but for this one just remember a recursive function just a function that calls itself in order to think about the problem well your solution needs two things so you need a base case so which is basically a simple solution you know so something you know how to do that you don't have to think very hard about and then the other one is your recursive step that you'll have to develop which just solves the problem in terms of a smaller version of itself so the idea here is since it's a smaller version of itself you're making progress each step you take eventually you will hit the base case and then you can just let your computer solve it for you so yeah we're really 13 minutes ahead all right cool I like it all right so I'll we'll just stick around for the remaining 13 minutes but just remember pulling for you we're all in this together