5 Simple Steps for Solving Any Recursive Problem

today we are going to talk about recursion I think most computer science students would agree that recursion felt more confusing than your average computer science topic in this video I'm gonna show you five simple steps that you can use to help you tackle any recursive problem and hopefully these steps will help you realize that in reality recursion isn't actually that bad I'm gonna show you how to apply these steps in the context of solving three specific recursive problems each of them progressively more difficult than the last so make sure you stick to the end of the video and as always I think you'll get the most out of this video if you take the time to pause and ponder some of the problems that we work through and the steps we went through to solve them so without further ado let's get started suppose we want to solve the following problem recursively write a function that given an input end sums all the non-negative integers up to n here's a couple quick examples of inputs to this function to give you a sense for what we are trying to implement a lot of you may have seen an iterative version of this function or even a mathematical version of it that we went during a previous video but if you had to solve it recursively how would you do it recursion is all about taking a problem and solving it using simpler versions of the problem so the first step in solving a recursive problem requires you to ask yourself what's the simplest possible input for the function here the simplest possible case is n equal 0 where we know that the result should also be 0 the simplest case often translates itself into a base case for our recursive problem the base case of a recursive function is the only input where we provide an explicit answer all other solutions to the problem we'll build on the base case the second key step to solving recursive problems is trying examples and visualizing how the inputs and outputs of these functions interact in this problem one fun way to visualize things is to treat our sum as building a triangle with the base as the input value that way some is a total number of individual blocks in this triangle you can try as many examples as you want once we have a set of examples we now want to move to the third step which involves relating larger examples to smaller examples take a second to see if you see any relationships between the cases here that pop out to you put in more specific terms with these examples ask yourself hey if I was given the answer for the N equals 4 case could I solve the N equals 5 case if I was given the ancestor N equals 3 case could I saw the N equals 4 case one interesting relationship that you may have noticed is that if we know the answer to the N equals 4 case all we need to do is add 5 to this answer to get the solution to our N equals 5 case and similarly if we know the answer to the N equals 3 case we can get the answer to the N equals 4 case by adding 4 it's not too hard to convince yourself that this should be true in general but if necessary feel free to try some larger cases to verify this now brings us to the fourth key step which is to generalize this pattern let's say we want to figure out the sum for the input N equals K we can find the sum by first taking the sum up to N equals K minus 1 and then all we have to do is add K to this value once we've generalize a pattern the last step now involves writing code by combining this recursive pattern with the base case this actually turns out to be not too hard since the code almost writes itself from our base cases and recursive pattern let's dig a little bit deeper to see how this really works for a particular input let's say we run this function for input N equals 5 what actually ends up happening well we go through the initial function and then hit a recursive case which adds 5 to the result of calling out some function on the input 4 so we know that this should theoretically give us the 10 but technically this function hasn't been evaluated yet what actually ends up happening is we have to go back into our function and repeat the process we hit the recursive case again which then causes us to now add 4 to the value of sum called on 3 which once again kicks off the same process as before let's take a moment to see how this unravels [Music] this continues until we hit the base case which then is used to softs the sum function called on n equals 1 which then solves a sum function called on n equals 2 and so on and so forth until we eventually build up the solution for our original N equals 5 case it's always ok to take some time to unravel the recursion to ensure that things work but as you get more experience solving these type of problems there's a concept called the recursive leap of faith that I would like you to think about the recursive leap of faith makes solving recursive problems much faster it's all about assuming that easier versions of the problem will be correct in this particular problem the recursive leap of faith would say that if I wanted to solve some called on n equals 5 let me just assume that some on N equals 4 is going to work and then if I add 5 to that some call on N equals 5 will also be correct don't worry if you're a little hesitant to believe in the recursive leap of faith but it is a useful problem-solving trick that helps in more complex recursive problems let's now explore a more involved recursive problem here's the problem write a function that takes two inputs N and M and outputs the number of unique paths from the top left corner to the bottom right corner of an N by M grid one key constraint is that you can only move down or write one unit at a time before we apply our five steps let's first familiarize ourselves with a few inputs and outputs for this function here's what happens when N equals two and M is equal to four [Music] we end up with exactly four paths and here's another example with N equals three and M equals three [Music] we end up with six unique paths all right let's begin let's play around with some simple inputs and see what happens the simplest possible reasonable input dysfunction is a one by one grid where we end up with exactly one path if we actually take a second to try some other simple inputs you might notice something interesting we can actually make a fairly comprehensive base case by noticing that if either one of these dimensions is going to be one we have only one unique path this can be written quite concisely as a following base case often with base cases you want to find a way to be as comprehensive as possible don't be afraid to adapt though it's completely normal to come back later and modify the base case let's now take a look at a decent sample size of examples to get a feel for the problem when coming up with examples for recursive problems it makes sense to do them in a sweeping manner where a lot of the examples are really close to each other remember our ultimate goal is to find a way to solve any specific case using simpler versions of that case so it makes sense to have examples that are close to each other all right so now that we have a sizable set of examples take a look at these and see if you notice any interesting relationships between cases I know that's a lot to look at so as a hint let's narrow down our focus to just these three examples do you notice anything how about now there's actually a really nice one-to-one correspondence between each path and the two by three and three by two cases two each path in the three by three case for each path in the two by three case we can take that path and go one unit down to create a path in the three by three case and for each path in the three by two case we can move one unit right to create a path in the three by three case so at least in this example we can confidently say that the number of paths in the three by three example is the sum of the number of paths in the two by three example and the number of paths in the three by two example but is that just a coincidence let's see if we can test this pattern by working backwards let's try to find the paths in the three by four case by analyzing a similar set of easier examples following the earlier pattern let's see if the number of paths in the three by four case is really the sum of the Pat's in the three by three case and two by four case we'll take each path for the three by three case and move one to the right to make a corresponding path for the three by four case and then we'll take each path in a two by four case and go one step down to make a path in the three by four case and it turns out that the set of paths that are created from this construction end up being all the unique paths to a three by four grid take a second to verify this for yourself if you're skeptical [Music] so let's now generalize this pattern we can find the total number of unique paths in an N by n grid by first finding all the unique paths from the N by M minus 1 grid each of these paths correspond to a path in the N by n grid since all we do is we move one unit to the right to create an Associated path and the remaining paths can be found by finding all the unique paths in an N minus 1 by M grid where we now take each path add one unit down and get the corresponding path in the N by M case once we found this general relationship the hard part is now over the last thing we do is take this general pattern bring it together with a base case and now write code the corresponding code for such a seemingly overwhelming problem ends up being remarkably simple and elegant and you'll see this a lot in recursive problems speaking of hard problems let's take a look at a really challenging problem here's the problem write a function that counts the number of ways you can partition and objects using parts up to M as we've done so far let's take a look at some examples to get a sense of what this problem is even asking for N equals 6 and M equals 4 here's how the partitions work out [Music] we end up with a total of nine unique partitions let's take a look at one more example to make sure we really understand what's going on here's what the partitions look like for inputs N equals 5 and M equals 5 here we have seven unique partitions and make sure you take a second to really understand why these are the only valid partitions all right so this problem definitely feels a little intimidating since it's not really obvious how we would even go about starting to solve it but this is where we're gonna have to fall back on our five steps let's start with step one the first thought for what the simplest possible input should be is when n is equal to zero and M is equal to zero but what does this mean what it's asking is how many ways can you partition 0 objects using parts up to 0 this may be a little bit mind-blowing but there's actually only one partition and that partition is to include no parts and in fact trying inputs N equals 0 with M equals 1 and then N equals 0 with M equals 2 is really no different this allows you to make another fairly comprehensive base case where the number of partitions is 1 if n is equal to 0 but there's some other simple cases that we should also check out if n is equal to 1 and M is equal to 0 how many partitions do we have how many ways can we partition one object if we are only allowed to use up to 0 parts well this is actually impossible we need at least one part so there are 0 ways to partition these inputs and the story stays the same no matter what the N is so this is the first example of a problem where we will need to separate base cases the second one being that if M is equal to 0 we have zero partitions all right let's now visualize a sizeable set of examples as before let's look at examples that are relatively close to each other in numbers so that it will make it easier for us to find patterns in the following steps once again if your task to solving this problem you don't want to be shy about writing out a ton of examples not only will it make you more comfortable with the problem but it also might help you find key insights to the solution [Music] so now that you have a good set of examples take a moment to see if you notice any interesting relationships among the partitions feel free to pause the video if you're struggling to find anything let's narrow our focus to a subset of these examples all right so the first interesting thing you might have noticed by looking at these examples is that a lot of the partitions on the larger problems are repeated in the easier version of a problem isn't that a little bit wild these are the types of patterns that show up a lot in these types of recursive problems and we definitely want to see if we can verify if this holds for larger examples let's take a look at the N equals 7 M equals 4 case we have a total of 11 partitions so going off our previous example we're expecting all the partitions of N equals 7 M equals 3 to show up in these partitions and in fact when we go through the partitions we indeed find that all 8 partitions from the N equals 7 M equals 3 case show up in the N equals 7 and M equals 4 case how in the world does that work what crazy sorcery is going on here the reason this happens is actually surprisingly simple if you take a moment to think about it from a perspective of how you are actually creating these partitions you'll get an intuitive sense for why this is the case when you're trying to partition 7 using parts up to 4 at some point this is going to include all the partitions of 7 using parts up to 3 there's just no other way around it more formally we can assert that the partitions of n using parts up to n minus 1 is a subset of the partitions and end using parts up to M okay so this seems like a pretty good start we now know that a subset of the partitions of n objects using parts up to M can be found from the simpler problem of partitioning and objects using parts up to M minus 1 but what about the remaining partitions where do these partitions come from let's analyze these cases what do they all have in common do you see it they all happen to use the actual M value as part of each partition and this should make sense because the subsets that we were moved or partitions of n using parts up to M minus 1 so the partitions that are left here that use M represent the only other case at this point you might be thinking ok great so the remaining partitions all use M how does this actually help us well let's think about what it actually means to use em in a partition once we declare hey I'm going to go ahead and use em as a partition this is what we end up having left in each of those cases all that's going on here is we subtracted M from our original n objects so we have a new end value with the same and value as before and check this out we actually have another one-to-one correspondence if we add em to each partition in the smaller problem we end up with the same partition in our original problem at this point you might still be a little skeptical because we tried this only on relatively small examples so to really verify this let's try one more large example and this time we're gonna try work backwards like we did in the grid problem let's look at the case where n is equal to 9 and M is equal to 5 based on our current observations we expect all the partitions in this case to correspond to the partitions in the n is equal to 4 and M is equal to 5 case and then the N is equal to 9 and M is equal to 4 case remember the first sub-problem represents all the partitions that use our original m as part of the partition when the second sub-problem represents partitions that use parts up to n minus 1 here are the partitions for the N is equal to 4 and M equals 5 case by adding M to each of these partitions we generate the corresponding subset of partitions for the N equals 9 and M equals 5 case and combining this with the 18 partitions from the N equals 9 and M equals 4 case we end up with 23 total partitions for the N equals 9 and M equals 5 case and you can take the time to verify this if you wish but these do actually end up being all the partitions for N equals 9 and M equals 5 case ok let's now generalize this pattern if we want to solve the count partitions problem called on a and B it will end up being the sum of the count partitions called on a minus B and B and then count partitions called on a and B minus 1 this is the key recursive relation that will solve this problem let's now execute the final step and put together our recursive relation with the base case one interesting wrinkle that we will have to take account of is that one of our recursive calls provides an argument that is n minus M some of you may have noticed that it's perfectly valid to have cases where n is actually less than M which then means that the new kalt will have a negative argument to count for this we have to include this corner case in one of our base cases if the N value provided is negative we will have zero partitions this problem is a good example of how you might have to modify some of your base cases after finding a general recursive pattern the cool thing about recursion is that for such a tricky problem our final solution actually ends up being only six lines of code [Music] so to recap what we did in this video we went over five key steps to solve any recursive problem and then went about applying these steps to three problems of various difficulties you learned the importance of starting simple and asking yourself what the simplest possible case is you found it helpful to work through some examples to get a sense for what the recursive problem was asking you also went about relating hard examples to easy examples to find a generalizable recursive pattern and then with this pattern in hand you went about writing the code as with anything you learned you're going to have to spend some time to really contemplate and work through recursive problems to really begin to master solving them this video is all about giving you a mental framework to do that and I hope it was helpful in that sense thanks for watching and as always I'd appreciate it if you liked the video if you enjoyed it if you want to see more content like this be sure to hit the subscribe button and if you want to more directly support this channel be sure to check out the patreon page linked in the description below see you in the next video [Music]

Channel: Reducible

Views: 925,412

Keywords:

Id: ngCos392W4w

Length: 21min 2sec (1262 seconds)

Published: Wed Dec 11 2019

Reddit Comments

[u/corrosivewater]

Awesome find! Thanks for sharing.

[u/fastfret888]

This still messes with my head, lol

[u/cakesngin]

excellent channel that I hadn't found yet - thank you for this

[u/OutdoorsmanWannabe]

This channel has some great videos. Here's another one on the Towers of Hanoi https://www.youtube.com/watch?v=rf6uf3jNjbo