What is recursion (recursive function call)?
A free video tutorial from Holczer Balazs
4.5 instructor rating • 31 courses • 203,972 students
Learn more from the full courseRecursion, Backtracking and Dynamic Programming in Python
Learn Recursion, Backtracking, Divide and Conquer Methods and Dynamic programming via Examples and Problems in Python
09:01:27 of on-demand video • Updated February 2021
- Understanding recursion
- Understand backtracking
- Understand dynamic programming
- Understand divide and conquer methods
- Implement 15+ algorithmic problems from scratch
- Improve your problem solving skills and become a stronger developer
English [Auto] In this chapter, we are going to talk about recursion and recursive function calls in Python. So first of all, you may pose the question that what is a recursion? Recursion is a method or procedure where the solution to a problem depends on a solution to smaller instances of the same problem. So we are going to call the same function over and over again in order to reduce the original problem into smaller and smaller instances. So we break the task into smaller subtasks. Basically, this approach can be applied to many types of problems, and recursion is one of the central ideas of computer science. We are going to talk about backtracking, backtracking. Related algorithms rely heavily on recursive function cause then, for example, graph algorithms such as Bread First Search and that first search uses recursion under the hood, or, for example, when we want to find the maximum or the minimum item in a binary search. We have to use recursion again. By the way, it is not necessary to use recursion because we can solve problems with recursion or with iteration so we can transform recursion into iteration. And why versa? Recursive approaches are very, very elegant and this is why it is a fundamental concept in computer science. By the way, we have to define base cases in order to avoid infinite loops, but we are going to talk a lot more about base cases. OK, so let's take a look at a concrete example. If we want to order the first and integers, we can use iteration a simple Falu basically, or we can use recursion, as you can see, where we call the same function over and over again. So let's take a look at the iterative approach. We have integer and we define a result and initialize it to the zero. We just have to make a simple for loop and make as many iterations as the value of this and variable. And basically we just have to sum up the values. So this is why we increment the result by this is how we sum up the first and integers. And finally we return with the result. So this is how we solve this problem with the type of iteration. Let's take a look at the recursive solution. We have the recursive Samah function with the input and we have to define a base case. This is what we have been talking about, that we have to define a base case is in order to avoid infinite loops. Of course, if we call the same function over and over again without the base case where we define when to stop the algorithm, of course it's going to be an infinite loop. So if the N is equal to one, we return one. And anyways, we return with N plus the recursive sum on and minus one. This is what we have been talking about, that the solution to a problem depends on solutions to smaller instances of the same problem. As you can see, we keep calling the same function with and minus one value. What does it mean that the value of and keeps decreasing, which means that finally and will be equal to one. And this is the base case when we return one. OK, so this is the recursive approach. This is the iterative approach. Both of them are valid and working fine. Let's talk about the types of recursion. There are two types, the tail recursion and had recursion. If the recursive call occurs at the end of the function, then it is called tail recursion. So tail recursion is very, very similar to a loop, whether it is a for loop or a wire loop. This method executes all the statements before jumping into the next recursive call. On the other hand, as far as had recursion is concerned, the recursive call appears at the beginning of the function. In this case it is called had recursion. The method saves the state before jumping into the next recursive call, which means that had recursion and needs more memory because we have to store the state of the actual function cause. OK, so let's take a look at recursion and had recursion, as you can see, because both of these cases are recursive function calls. This is why we have to define the base cases. So if and is equal to one and then we return. And as far as tail recursion is concerned, first we do the operation. In this case, we just print out the value of N and the last statement of the function. Is the recursive function call, so this is talu recursion, where no need to consider the last item to be able to get the result for the first operation. This is what we have been talking about, that the recursive call occurs at the end of the function. What about the recursion as far as had recursion is concerned? Again, we have to define the base case. Then we call this function recursively and finally we do a given operation. As you can see, the exact opposite, what we have done with the recursion. So first we call this method recursively and then we print out the value of an and this is why we have to consider the last item to be able to get the result for the first operation. We are going to talk a lot about the memory complexity of had recursion and recursion. And we are going to see that as far as had recursion is concerned, we have to store more items on the stack memory than with recursion. Anyways, in the next lecture, we are going to talk about the concrete implementation of recursion and how recursion. Thanks for watching.