Hello and welcome to the lesson devoted to recursion. We start this lesson with a very soft introduction to recursion. So imagine a line to a museum. Imagine a person that just gets in the line, call her Alice. And she has this natural will to know the number of people before her. So she asks Bob, who is the person just right before her, "Could you please tell me the number of people before you." So what is important to realize at this point is that Bob faces exactly the same problem at this point. So Bob somehow computes the number of people before him is 239, for example. So at this point, Alice knows that the number of people before her is equal to 240, right? And this can be implemented in the following very simple code. So we call this procedure, number of people before some person in a line. So it is implemented as follows, just this four simple lines of code: If there is nobody before this person, then we just return zero. Otherwise there is a person before A, let's call him B. So what we do, we first make a recursive call for B. By saying recursive call, I mean the code for this, for exactly the same function because we need to perform exactly the same computational task. So we make this call, it returns us some result, we add one and then we return it, okay? So another very standard example is the following: it's computing the factorial function. So the factorial of positive integer n, it is denoted as follows, so pronounce it n factorial. Is by definition equal to the product of all positive integers from 1 to n. So for example, five factorial is equal to one times two, times three, times four, times five, which is equal in turn to one hundred and twenty. You can notice that it is actually same as one times two, times three, times four multiplied by five, but this is just four factorial, right? Just by definition, right? So this can be as well expressed as four factorial times five. And this gives rise to the following recursive definition: So n factorial is equal to one when n is equal to one, or it is equal to n times n minus one factorial, when n is greater than 1. So it is a recursive definition because it defines n factorial, so it defines a function in terms of itself. So it expresses n factorial through n minus one factorial, right? So the recursive definition defines an object in terms of itself. The recursive program calls itself. So when we have such and at the same time you can continue this further, right? So n minus one factorial is also n minus one times n, minus two factorial. And n minus two factorial in turn is n minus two times n minus three factorial. So we somehow need to ensure that this process of calling itself will terminate at some point and that there will be just a finite number of steps. So we need to somehow ensure this and we will get back to this just in a minute. So before this, let's first implement the very simple program for computing the factorial, and we first turn its basic definition into an iterative program. So here, we first make a check of areas in greater than zero, then we just declare some new variable, which is going to store our result. And then we iterate all possible values from one to n, this is down here. And for each such value, we multiply the result by it and finally, we return the result. So this is iterative program, okay? In turn, the recursive program gives rise to the following recursive procedure: Again, we first check that n is greater than zero, right? Then, if n is equal to one, then we immediately return on. In this case there is nothing to compute of course. Otherwise we return n times the factorial of n minus one. So what will happen here actually during this recursive program is that first, the factorial of n minus one is going to be computed, then it will be multiplied by n, and then it will be returned. So this way we transform our recursive definition into recursive program and once again, the way we ensure that the number of recursive calls is going to be finite in this case is exactly because we have this base case, the so called base case. So with each recursive call, n decreases by one. So eventually, it will hit one and at this point, our recursive procedure will return one and will stop using new recursive calls, okay? So termination is important and usually, it is achieved as we've discussed already, by keeping track of some parameter and by ensuring that it always decreases and that at some point it will hit the base case. Okay? So when we were computing the lengths of the line, we actually saw why our recursive procedure will eventually stop. Well, just because with each recursive call, we get closer to the head of the line. to put it otherwise, the number of people before the current person, it always increases by one right with each recursive call. And it cannot become negative and when it is zero, we actually return, we stop producing new recursive calls. And similarly, for n factorial when computing factorial, n always decreases by one with each recursive call and when its one, we just return, okay? Let me also show you several examples of` the recursion of an infinite recursion. So the first one is shown here. So here, instead of decreasing n with each recursive call, we actually increase it. So what happens here is that it will produce just an infinite number of recursive calls, an endless process of calling the same procedure. So in theory, such a program will never stop. So n will be increased to infinity. In practice, if you run this program, so what you get is that it will crash and you will get either stack overflow message or message like maximum recursion depth exceeded, okay? A little bit more examples, so for example, this is the same program for computing factorial where we just forget to add a base case. So in this case, while this is going to happen, regard this as an infinite recursion, so it is going to be infinite just because there is no base case. If you call for example factorial five, it will make make a recursive call for factorial four, then factorial three, factorial two, factorial one, then factorial zero minus one, minus two, minus three and so on. It will never stop. Another possibility of infinite recursion is the following, So in this case we have some base case, however, we do not change the parameter, the parameter does not decrease. So if you call factorial five, it will call factorial five again, and again, and again, and again, and again, so forever. Finally, two more jokey examples. So there is a standard joke that to understand recursion, you must first understand recursion, which again puts you into an infinite loop. So if you would like to start understanding recursion, according to this rule, you must first understand recursion, but to understand recursion, you must first understand recursion and so on. And finally, an example by Google. You know that in Google there is this spell checking property, a suggesting product feature, which if you make a typo in your search query, it will fix it for you and that's whether you mean the following. So if you type recursion, the Google will ask you, did you mean recursion and this is clickable actually, and if you click, you will get to the same page and it will ask you again and then you will click again, and again, and again, an endless number of times.
