5 Simple Steps for Solving Any Recursive Problem

Today we are going to talk about recursion. I think most CS students would agree that recursion feels more confusing than the average CS topic. In this video, I'll show you five

simple

steps

you can use to help you tackle any

recursive

problem

. and I hope these

steps

help you realize that recursion isn't actually that bad. I'm going to show you how to apply these steps in the context of

solving

three specific

recursive

problem

s, each progressively more difficult than the last, so make sure you stick with the end of the video and, as always, I think you'll get the most out of it. this video if you take the time to pause and reflect on some of the problems we work on and the steps we take to solve them.

Without further ado, let's get started, suppose we want to solve the following problem, recursively write a function that, given a final input, sums all non-negative integers up to n. Here are a couple of quick examples of inputs to this function to give you an idea of ​​what we're trying to implement. Many of you may have seen an iterative version of this function or even a mathematical version that we saw during a previous video, but if you had to solve it recursively, how would they do it? Recursion is about taking a problem and

solving

it using

simple

r versions of the problem, so the first step in solving a recursive problem requires you to ask yourself what is the simplest possible input to the function.

Here the simplest possible case is n equals 0, where we know that the result should also be 0 the simplest case often translates 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 will build on the base case the second key The step to solve recursive problems is to try examples and visualize how the inputs and outputs of these functions interact in this problem. A fun way to visualize things is to treat our sum like building a triangle with the base as the input value, that way part is a whole. number of individual blocks in this triangle, you can try as many examples as you want, once we have a set of examples, now we want to move on to the third step, which involves relating larger examples to smaller examples, take a second to see if you see any relationship.

Among the cases listed here, put them in more specific terms with these examples, ask yourself hey, if I were given the answer for the case N equals 4, could I solve the case N equals 5 if I was given the ancestor case N is equal to 3? Can I see the case N is equal to 4? An interesting relationship that you may have noticed is that if we know the answer to the case N equals 4, all we have to do is add 5 to this answer to get the solution to our case N equals 5. and similarly , if we know the answer to the case N equals 3, we can get the answer to the case N equals 4 by adding 4.

It's not too difficult to convince yourself that this should be true in general, but if necessary, feel free to try Something bigger. cases to verify this now takes us to the fourth key step which is to generalize this pattern, let's say we want to calculate the sum of the input N equals K, we can find the sum by first taking the sum until N equals K minus 1 and then all we have to do is add K to this value once we have generalized a pattern, the last step now involves writing code combining this recursive pattern with the base case, this is actually not too difficult as the code almost writes to Starting from our base cases and recursive pattern, let's dig a little deeper to see how this actually works for a particular input, let's say we run this function for the input N equals 5, what actually ends up happening, well, we go through the initial function and then we press a recursive case that adds 5 to the result of calling some function on input 4, so we know that this should theoretically give us 10, but technically this function has not been evaluated yet, which actually ends up happening It's just that we have to go back.

In our function and we repeat the process, we reach the recursive case again, which causes us to now add 4 to the value of the sum called 3, which once again starts the same process as before. Let's take a moment to see how it unravels. This continue. until we get to the base case which is then used to smooth the addition function called n equals 1, which then solves an addition function called n equals 2 and so on until we finally construct the solution for our original N equals 5 . In this case, it's always okay to take some time to figure out recursion and ensure things work, but as you get more experience solving these types of problems, there's a concept called a recursive leap of faith that I'd like you to think about. makes solving recursive problems much faster.

It is about assuming that the simplest versions of the problem will be correct on this particular problem. The recursive leap of faith would say that if I wanted to solve some calls on n equals 5, let me assume 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's a useful problem. solving trick that helps in more complex recursive problems let's now explore a more complicated recursive problem here is 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 a N per M grid, a key restriction is that you can only move down or write one unit at a time before applying our five steps.

Let's first get familiar with some inputs and outputs for this function. This is what happens when N equals two and M equals. to four we end up with exactly four paths and here is another example with N equals three and M equals three we end up with six unique paths, okay, let's get started, let's play with some simple inputs and see what happens, reasonable input dysfunction more The simplest possible is a one by one grid where we end up with exactly one path, if we really take a second to try other simple inputs you might notice something interesting, we can create a pretty complete base case by noting that if any of these dimensions go to be one we only have a single path, this can be written quite concisely as a base case following, often with base cases you want to find a way to be as complete as possible, don't be afraid to adapt, although it is completely normal go back. later and modify the base case, now let's look at a decent sample size of examples to get an idea of ​​the problem.

When creating examples for recursive problems it makes sense to make them broad where many of the examples are very close to each other, remember that our ultimate goal is to find a way to solve any specific case using simpler versions of that case, so you have It makes sense to have examples that are close to each other, now that we have a sizable set of examples. Take a look at these and see if you notice any interesting relationships between the cases. I know there's a lot to look at, so as a suggestion, let's limit our focus to just these three examples.

Do you notice anything? What if there's a really good one now? Correspondence -to one between each path and the two-by-three and three-by-two cases two for each path in the three-by-three case for each path in the two-by-three case we can take that path and go down one unit 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 to the right to create a path in the three by three case, so at least in this example we can say with confidence that the number of paths in the three by three 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 it is just a coincidence, let's see if we can try this pattern working back, let's try to find the paths in the three by four case by analyzing a similar set of easier examples following the previous pattern, let's see if the number of paths in the three by four case is really the sum of the Pats in the case of three by three and in the two by four case We will 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 will take each path in a two by four and we'll go down one step 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 unique paths to a three by four grid, take a second to Check this out for yourself if you're skeptical.

Let us 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 in the N by M grid minus 1, each of these paths corresponds to a path in the N grid by n since all we do is 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 a grid of N minus 1 by M where we now take each path, add one unit down and we get the corresponding path in the N by M case once we find this general relationship the hard part is over, the last thing we do is take this general pattern, put it together with a base case and now write the corresponding code for a seemingly overwhelming problem. ends up being remarkably simple and elegant and you'll see this a lot in recursive problems talking about 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 like We have done it so far, let's take a look at some examples to get an idea of ​​what this problem is asking, since N is equal to 6 and M is equal to 4, this is how partitions work, 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 is what the partitions look like for the entries N equals 5 and M equals 5 here we have seven unique partitions and be sure to take a second to really understand why these are the only valid partitions, then this problem definitely feels a little intimidating since it's not really obvious how we would begin to solve it, but this is where we'll have to resort to our five steps, let's get started.

With step one, the first thought about what the simplest possible input should be is when n equals zero and M equals zero, but what does this mean? What you are asking is how many ways can you partition 0 objects using parts up to 0. It may be a bit mind boggling but there is really only one partition and that partition should not include parts and in fact trying entries N equals 0 with M equals 1 and then N equals 0 with M equals 2 actually no different, this allows you to do another fairly complete base case where the number of partitions is 1 if n equals 0, but there are other simple cases we should also check if n is equal to 1 and M is equal to 0, how many partitions do we have?

How many ways can we split an 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 split these inputs and the story remains the same no matter what the N is. So this is the first example of a problem in the that we will need to separate base cases. The second is that if M is equal to 0, we have zero partitions. Okay, let's now visualize a considerable set of examples as before, let's look at examples that are relatively close to each other in numbers, so it will be easier for us to find patterns in the next steps once again, if your task is to solve this problem, you don't want to be embarrassed to write a bunch of examples, not only will you feel more comfortable with the problem, but it could also help you come up with key ideas for the solution?

Now that you have a good set of examples, take a moment to see if you notice any interesting relationships between the partitions. Feel free to pause the process. video, if you're having a hard time finding something, let's limit our focus to a subset of these examples, so the first interesting thing you may have noticed when looking at these examples is that many of the partitions in the larger problems are repeated in the larger version. simple explanation of a problem is not a bit far-fetched. These are the types of patterns that appear a lot in these types of recursive problems and we definitely want to see if we can check if this holds for broader examples.

Let's take a look. In the case N equals 7, M equals 4, we have a total of 11 partitions, so, starting from our previous example, we expect that all partitions of N equals 7, M equals 3 appear in these partitions and in fact when we go through the partitions, we actually find that the 8 partitions of the case N is equal to 7, M is equal to 3 appear in thecase N is equal to 7 and M is equal to 4, how does that work? What crazy sorcery is going on here, the reason why this happens is actually surprising. It's simple, if you take a moment to think about it from the perspective of how you are actually creating these partitions, you will get an intuitive idea of ​​why this is the case when you try to partition 7 using parts up to 4 at some point. this will include all 7 partitions using parts up to 3, there is simply no other way around it more formally we can state that n partitions using parts up to n minus 1 is a subset of the partitions and end up using parts up to a M okay, so this seems like a good start, now we know that a subset of partitions of n objects using parts up to M can be found from the simplest partitioning problem and objects using parts up to M minus 1, but what What about the remaining partitions?

Where do these partitions come from? Let's analyze these cases. What do they all have in common? Sees it? It turns out that they all use the actual M value as part of each partition and this should make sense because the subsets we were moving or partitioning from n using parts up to M minus 1, so the partitions left here that use M represent the only other case At this point, you might be thinking, okay, so all the remaining partitions use M, how does this really help us? let's think about what it actually means to use them in a partition once we declare hey I'm going to go ahead and use them as a partition, this is what we end up having in each of those cases, all that's happening here is that we subtract M from our n original objects, so we have a new final value with the same value and as before and look at this, we actually have another one-to-one correspondence if we add em to each partition in the smaller problem we end up with. same partition in our original problem at this point, you might still be a little skeptical because we tested this only on relatively small examples, so to really verify this, let's try a larger example and this time we will try to work backwards as 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 that all partitions in this case correspond to the partitions where n is equal to 4 and M is equal to 5 case and then N is equal to 9 and M is equal to 4 case remember that the first subproblem represents all partitions that use our original m as part of the partition when the second subproblem represents partitions that use parts up to n minus 1 here are the partitions for the case N is equal to 4 and M is equal to 5 by adding M to each of these partitions we generate the corresponding subset of partitions for the case N is equal to 9 and M is equal to 5 and we combine this with the 18 partitions for case N equals 9 and M equals 4, we end up with 23 partitions in total for case N equals 9 and M equals 5 and you can take the time to check this if you want, but in actually end up being all partitions for N equals 9 and M equals 5, okay now let's generalize this pattern, if we want to solve the problem of counting partitions called in a and B, it will end up being the sum of counting partitions called in a minus B and B and then count the partitions called in a and B minus 1 this is the key recursive relationship that will solve this problem.

Now let's execute the final step and join our recursive relationship with the base case. An interesting aspect that we will have to take into account is that. of our recursive calls provides an argument that is n minus M. Some of you will have noticed that it is perfectly valid to have cases where n is actually less than M, which means that the new kalt will have a negative argument to count. To include this corner case in one of our base cases, if the given N value is negative, we will have no 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 nice thing about recursion is that for such a complicated problem our final solution actually ends up being only six lines of code, so to summarize what we did in this video, we go over five key steps to solving any recursive problem and then apply these steps to three problems of varying difficulty you learned the importance of starting simply and asking yourself what the simplest possible case is. You found it helpful to work through some examples to get an idea of ​​what the recursive problem was asking. You also related difficult examples to easy examples. to find a generalizable recursive pattern and then with this pattern in hand you started writing the code, because with everything you learned you will need to spend some time contemplating and working on recursive problems to really start mastering their solution .

The video is all about giving you a mental framework to do that and I hope it was helpful in that regard. Thanks for watching and as always, I would 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 support this channel more directly be sure to visit the patreon page linked in the description below, see you in the next video.