Learn Competitive Programming, Recursion, Backtracking, Divide and Conquer Methods and Dynamic Programming in Python
15:39:24 of on-demand video • Updated November 2023
Understand dynamic programming
Understand divide and conquer methods
Implement 15+ algorithmic problems from scratch
Improve your problem solving skills and become a stronger developer
In this lecture, we are going to talk about an extremely crucial topic in computer science, the so-called recursion. So first of all, what is recursion? Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem. So essentially, we break the tasks into smaller and smaller subtasks. And what's crucial that we are going to solve the sub tasks with the same function. So essentially we keep calling the same function over and over again. This is very similar to the Russian dolls where items include smaller and smaller items recursively. So we have the smaller one, then the smaller one until we hit the smallest item. This approach can be applied to several types of problems. This is why recursion is in the center of computer science. For example, if you want to implement a binary search tree, then you can use recursion or for example, you are dealing with backtracking related problems or graph algorithms such as depth First search. You will come to the conclusion that most of these problems can be implemented with the help of recursion. So this is why it is absolutely crucial to understand recursion and then it is important to define the base cases. This is the case with the smallest item. We have to avoid infinite loops, so somehow we have to track when to stop recursion. And finally, every single problem can be solved either with iteration or with recursion. So if we have a recursive approach, we can transform that recursion into iteration and vice versa. If we have an iterative approach, we can transform it into recursion. So first of all, let's take a look at a concrete example. Let's assume that we want to calculate the sum of the first and integers. Of course it is quite obvious how to do it with iteration and denotes the first n integers we are going to sum up. So we have to define a result variable with initial value zero. Then we iterate through every single number within the range zero up to N plus one. Of course, the range function is exclusive. So if we define n plus one, then n will be the last item we are going to consider. But anyways, we will sum up these values and then we return with the result. This is the iterative approach and every single problem can be solved either with iteration or with recursion, so we can transform this iterative approach into a recursive approach. So this is the recursive approach. Again, we have to define n that denotes the first n integers we would like to sum up we have to define the base case. It is absolutely crucial that when we are dealing with recursion because we keep calling the same function over and over again, we have to define a base case in order to avoid an infinite loop. So if N is equal to zero, this is when we return zero. Otherwise we return with N plus. We call the same function recursively with n minus one. And you may pose the question that why do we use recursion when the iterative approach is usually faster? And the answer is that if we understand a problem, then it is way more easier to implement it with recursion than with iteration. We are going to talk about several problems during the coming lectures and we will come to the conclusion that if we understand the fundamental basics of a given problem, then it is going to be way easier to implement that given problem with recursion. And sometimes, at least for me, it is quite hard to understand an iterative implementation. We are going to talk about backtracking related approaches and backtracking related approaches is quite hard to understand with iteration. So this is why recursion is in the center of computer science. Here, for example, it is quite obvious that we are going to sum up all the values n plus the sum of N minus one. So we keep calling the same function over and over again until we hit the base case. So n is equal to zero. This is when we return zero. And we sum up all the values. We are going to talk about several examples in the coming lectures, and it is going to be clear. Okay, so this is recursion and what we show that there are two types of recursion tail recursion and head recursion. If the recursive function call occurs at the end of the function, it is called tail recursion. Tail recursion is very, very similar to a loop such as for loop or while loop. We can say that iteration is essentially tail recursion because the recursive function call occurs at the end of the function, which means that this method executes all the statements. Before jumping to the next recursive pool. This is exactly how loops work. As far as a for loop is concerned, we are going to do a single statement, a single operation in every single iteration. And of course, the programming language will execute every single operation related to a given iteration before jumping to the next one. And this is very, very similar to Taylor Recursion. What about head recursion? If the recursive function call occurs at the beginning of the function, it is called head recursion. This approach saves the state of the function call before jumping into the next recursive call. It means that head recursion needs more memory because of the state it stores. Okay, so let's take a look at a concrete example. We have Taylor recursion and we have had recursion. Of course, no matter we are dealing with Taylor recursion or head recursion. We have to define the base case. If N is equals to one, we return. Otherwise we are going to do some operation. In this case, just for demonstration purposes, we print out the value of N and then we call this tail method recursively with n minus one. This is Taylor Recursion because the function call occurs at the end of the function, there is no need to consider the last item to be able to get the result for the first operation because the operation precedes the recursive function call. Tail recursion is very very similar to an iteration. We execute the given operation and then we call the function recursively. Then we execute the given operation again and we call the function recursively until we hit the base case and then it's over. What about head recursion as far as head recursion is concerned? First of all, we have to define the base case as usual. Then we call the function recursively. So we call the same head function with n minus one as the argument. And then we do some operation. In this case, just for demonstration purposes, we print out the value of N. In this case, the algorithm has to consider the last item to be able to get the result for the first operation. Anyways, that's all about the theoretical background. In the next lecture we are going to take a look at a concrete example and it is going to be clear what is the difference between tail recursion and head recursion? What's crucial that tail recursion is very similar to a loop, whether it is a for loop or a while loop, while on the other hand, had a recursion needs more memory because it has to save the state of the recursive function calls. Thanks for watching.