Recursion - CS50 Shorts

Key Takeaways

[Music] you probably think that code is just used to accomplish a task you write it out it does something and that's pretty much it you compile it you run the program you're good to go but believe it or not if you code for a long time you actually might come to see code as something that's beautiful it's it solves a problem in a very interesting way or there's just something really neat about the way it looks you might be laughing at me but it's true and recursion is one way to sort of get this idea of beautiful elegant looking code it solves problems in ways that are interesting easy to visualize and surprisingly short the way of recursion works is a recursive function is defined as a function that calls itself as part of its execution that might seem a little strange and we'll see a little bit about how this works in a moment but again these recursive procedures are gonna be so elegant because they're gonna solve this problem without having all of these other functions or these long loops you'll see that these recursive procedures are going to look so short and and they really are gonna make your code look a lot more beautiful let's look at an example of this to see how a recursive procedure might be defined so if you're familiar with this from math class many years ago there's something called the factorial function which is usually denoted as n exclamation point which is defined over all positive integers in the way that n factorial is calculated is you multiply all of the numbers less than or equal to n to gather all the integers less than or equal to n together so 5 factorial is 5 times 4 times 3 times 2 times 1 and 4 factorial is 4 times 3 times 2 times 1 and so on you get the idea as programmers we don't use an exclamation point so we'll we'll define the factorial function as fact of N and we'll use this will use factorial to create a recursive solution to a problem and I think you'll might find that it's a lot more visually appealing than the iterative version of this which we'll also take a look at in a moment so here are a couple of facts pun intended about factorial the factorial function so the factorial of 1 as I said is one the factorial of 2 is 2 times 1 the factorial of 3 is 3 times 2 times 1 and so on we talked about 4 and 5 already but looking at this isn't this true isn't factorial of 2 just 2 times the factorial of 1 I mean the factorial of 1 is 1 so I can't we just say that since 2 factorial 2 is 2 times 1 it's really just 2 times the factorial of 1 and then extending that idea is in the factorial of 3 just 3 times the factorial of 2 and the factorial of 4 is 4 times the factorial of 3 and so on in fact the factorial of any number can just be expressed if we kind of carry this out forever we can kind of generalize the factorial problem as it's n times the factorial of n minus 1 it's n times the product of all of the numbers less than me this idea this generalization of the problem allows us to recursively define the factorial function when you define a function recursively there's two things that need to be a part of it you need to have something called a base case which when you trigger it will stop the recursive process otherwise a function that calls itself as you might imagine could go on forever function calls function calls the function calls the function calls the function if you don't have a way to stop it your program will be effectively stuck at an infinite loop it will crash eventually because it'll run out of memory but that's beside the point the reason we need to have some other way to stop things besides our program crashing because program that crashes is probably not beautiful or elegant and so we call this the base case this is the a simple solution to a problem which stops the recursive process from occurring so that's one part of the recursive function the second part is the recursive case and this is where the recursion will actually take place this is where the function will call itself it won't call itself in exactly the same way it was called it'll be a slight variation that makes the problem it's trying to solve a teeny bit smaller but it generally passes the buck of solving the bulk of the solution to a different call down the line which of these looks like the base case here which one of these looks like the simplest solution to a problem we have a bunch of factorials we can continue going on 6 7 8 9 10 and so on but one of these looks like a good case to be the base case it's a very simple solution we don't have to do anything special the factorial of 1 is just 1 we don't do any multiplication at all it seems like if we're gonna try and solve this problem and we need to stop the recursion somewhere we probably want to stop it when we get to 1 we don't want to we want to stop before that so if we're defining our factorial function and here's a skeleton for how we might do that we need to plug in those two things the base case and the recursive case well what's the base case if n is equal to 1 return-1 that's a really simple problem to solve right the factorial of 1 is 1 it's not 1 times anything it's just 1 it's a very easy fact and so that can be our base case if we get past 1 into this function we'll just return 1 what's the recursive case probably look like for every other number besides 1 what's the pattern well we're taking the factorial of n it's n times the factorial of n minus 1 over taking the factorial 3 it's 3 times the factorial of 3 minus 1 or 2 and so if we're not looking at 1 otherwise return n times the factorial of n minus 1 it's pretty straightforward right and for the sake of having slightly cleaner and more elegant code know that if we have single line loops or single line conditional branches we can get rid of all of the curly braces around them so we can consolidate this to this this has exactly the same functionality as this I'm just taking away the curly braces because there's only one line inside of those conditional branches so these behave identically if n is equal to 1 return 1 otherwise return n times the factorial of n minus 1 so we're making the problem smaller if and it starts out as 5 we're going to return 5 times the factorial of 4 and it will see in a minute when we talk about the call stack or in another video when we talk about the call stack we'll learn about why exactly this person this process works but while factorial 5 says return 5 times factorial 4 then 4 is gonna say okay well return 4 times the factorial 3 and as you can see we're sort of approaching 1 we're getting closer and closer to that base case and once we hit the base case all of the previous functions have the answer they were looking for factorial of 2 was saying return 2 times the factorial of 1 well 2 times 1 well if factorial of 1 returns 1 so factorial if call 4 factorial of 2 can return 2 times 1 and give that back to factorial of 3 which is waiting for that result and then it can calculate its result 3 times 2 6 and give it back to factorial of 4 and again we have a video on the call stack where this is illustrated a little more than what I'm just saying right now but this is it this alone is the solution to calculating the factorial of a number it's only four lines of code that's pretty cool right and it's you know it's kind of sexy so in general but not always a recursive function can replace a loop in a non recursive function so here side by side is the iterative version of the factorial function both of these calculate exactly the same thing they both calculate the factorial of n the version on the left uses recursion to do it the version on the right uses iteration to do it and notice we have to declare a variable an integer product and then we loop so long as n is greater than 0 we keep multiplying that product by n and decrementing n until we calculate the product so these these two functions again do exactly the same thing but they don't they don't do it in exactly the same way now it is possible to have more than one base case or more than one recursive case depending on what your function is trying to do you don't you're not necessarily just limited to a single base case or a single recursive case so an example of something with multiple base cases might be this the Fibonacci number sequence you may recall from elementary school days that the Fibonacci sequence is defined like this the first element is 0 the second element is 1 both of those are just by definition then every other element is defined as the sum of n minus 1 and n minus 2 so the third element would be 0 plus 1 is 1 and then the fourth element would be the second element 1 plus the third element 1 and that would be 2 and so on and so on so in this case we have two base cases if n is equal to 1 return 0 if n is equal to 2 return 1 otherwise return Fibonacci of n minus 1 plus Fibonacci of n minus 2 so that's multiple base cases what about multiple recursive cases well there's something called the Collatz conjecture I'm not just gonna say you know what that is because it's actually our final problem for this particular video and it's our exercise to work on together so here's what the Collatz conjecture is it applies to every positive integer and it speculates that it's always possible to get back to 1 if you follow these steps if n is 1 stop we've we've got back to 1 if n is 1 otherwise go through this process again on n divided by 2 and see if you can get back to 1 otherwise if n is odd go through this process again on 3n plus 1 or 3 times n plus 1 so here we have a single base case if n is equal to 1 stop we're not doing any more recursion but we have two recursive cases if n is even we do one recursive case calling n divided by 2 if n is odd we do a different recursive case on 3 times n plus 1 and so the goal for this video is to take a second pause the video and try and write this recursive function Collatz where you pass in a vale a value N and it calculates how many steps it takes to get to 1 if you start from N and you follow those steps up above if n is 1 it takes 0 steps right otherwise it's gonna take 1 step plus however many steps it takes on either n divided by 2 if n is even or 3n plus 1 if and is odd now I've put up on the screen here a couple of test things for you in a couple of test cases for you to see what these various collapse numbers are and also an illustration of the steps that need to be gone through so you can sort of see this process in action so if if n is equal to one Kol acts of n is zero you have to do anything to get back to one you're already there if n is two it takes one step to get to one you start with two well 2 is not equal to one so we're gonna do it's gonna be one step plus however many steps it takes on and divided by 2 and divided by 2 there is in the end yeah and divided by 2 2 divided by 2 is 1 so it takes one step plus however many steps it takes for one one takes zero steps for three as you can see there's quite a few steps involved you go from three and then you go to 10 5 16 8 4 to 1 it takes seven steps to get back to 1 and as you can see there's a couple other test cases here to test out your program so again pause the video and I'll go jump back now to the to what the actual process is here what this conjecture is see if you can figure out how to define Co lots of n so that it calculates how many steps it takes to get to one alright so hopefully you have pause the video and you aren't just waiting for me to give you the answer here but if you uh if you are well here's the answer anyway so here is a possible definition of the Collatz function our base case if n is equal to one we return zero it doesn't take any steps to get back to one otherwise we have two recursive cases one for even numbers and one for odd the way I test for even numbers is to check if n mod 2 equals 0 this is basically again asking the question if you recall what mod is is if I divide n by 2 is there no remainder that's that would be an even number and so if n mod 2 equals 0 is testing is this an even number if so I want to return 1 because I'm this is definitely taking one step plus colapse of whatever numbers half of me otherwise I want to return 1 plus Co lots of 3 times n plus 1 that was the other recursive step that we could take to calculate the Collatz this number of steps it takes to get back to one given a number so hopefully this example gave you a little bit of a taste of recursive procedures hopefully you think code is a little more beautiful if implemented in an elegant recursive way but even if not recursion is a really powerful tool nonetheless and so it's definitely something to get your head around because you'll be able to create pretty cool programs using recursion that might otherwise be complex to write if you're using loops in iteration I'm Doug Lloyd this is cs50