Well, we've looked at two examples of recursion and we've dragged you through a very detailed analysis of their recursive definitions and functions. At this point, you've likely got the hang of it, so we could probably stop with all this recursion stuff right here, but we're going to look at one final example just to give you a chance to see whether you really understand it. We'll analyze this one too, but this time you should be able to stay one step ahead of us. That's good. If you find that it all seems familiar and there are no big surprises, great, you'll know you're a recursion expert. If not, that's okay too because this last example should do it. You might expect our last example to be the latest thing and recursion, not exactly. The example we're about to look at finds the greatest common divisor of two non-negative integers, and it is a slight modification of an algorithm that was recorded by a fellow from Greece named Euclid, 2,300 years ago. Friends, this guy Euclid, or as his friends in Greece called him Eukleídēs is a real rock star in the history of mathematics, and he recorded a lot of other hits too. Unlike the biggest stars, everybody knows him by just one name, like Sting, Adele, Beyonce, Sinatra, and Galileo, he's big. He's real big. But Euclid didn't invent the concept of the greatest common divisor, that had been around long before him. Well, so what is the greatest common divisor? The greatest common divisor, which is also known as the greatest common factor, is the largest integer that divides each of two non-negative integers with a remainder of zero, or put another way, it's the largest integer that is a factor of both of the integers. For example, if you have two numbers, 35 and 14, the greatest common divisor is 7. Because 35 divided by 7 is 5 with a remainder of 0, and 14 divided by 7 is 2 with a remainder of 0, and there's no other integer larger than 7 that does this, or put another way as shown here, 7 is the largest common factor of 35 and 14. A second example is the pair of integers 12 and 4, whose greatest common divisor or greatest common factor is 4. A third example is 6 and 0, whose greatest common divisor is 6. Because the largest integer that divides 6 with a remainder of 0 is 6 itself, and 6 also divides 0 with a remainder of 0. That's what the greatest common divisor is. But how would you calculate it for two numbers, say a and b? Well, one algorithm to do it would be to divide a and b by every integer that's less than or equal to a and b, and choose the largest one that has a remainder of 0 for both of them. For example, if a and b are 35 and 14, as in the first example that we just did and as shown here, we can divide them both by all the integers from 1-14, starting with 1, which always gives a remainder of 0, then by 2 whose remainder 0 only for 14, and by 3 whose remainder is not 0 for either one of them, and so on up through 14. Then we search back to find the largest integer with a remainder of 0 for both of them, which in this case is 7, and so 7 is the greatest common divisor of 35 and 14. That'll work every time. But Euclid came up with a more efficient algorithm, and we're going to show you a modification of his algorithm is even more efficient than that. The underlying ideas based on a simple observation. Which is, that the greatest common divisor of two numbers is also the greatest common divisor of the smaller number and the remainder of dividing the larger number by the smaller number. I didn't say it was obvious, just simple. That's true for a lot of things in number theory, which is the study of integer arithmetic. A statement like the one we just made and that we are looking at, might be simple. But why that statement is true is far from obvious. If you want to learn the why part, you can search for information on greatest common divisor or greatest common factor. But our goal here is not to explain why this statement is true, but to explain how to implement a recursive algorithm that's based on it, and that is simple. Let's do that. First we look at the recursive definition. By now the format should be familiar, a base case and a recursive case. The base case says that if one of the input integers is zero, then the greatest common divisor is the other integer. The recursive case is exactly the same as the statement that we just went over with all the pretty colored arrows. Now that we've got our base case and our recursive case, we're ready to go from the recursive definition to the recursive function. Here's a MATLAB function that implements the recursive definition. As you can see, we've named our function rgcd for recursive greatest common divisor. Its goal is to calculate the greatest common divisor of its input arguments x and y, and return it in the output argument d. As usual, we start with an if statement that checks for proper inputs. After that's done, we copy the inputs into a and b, making sure that a is not smaller than b. Now it's time to get into the meat of the algorithm. For that, all we have to do is implement the recursive definition that we just showed you. It's just 1, 2, 3, 4, 5 lines. We start with the base case, which is b equal to 0, and for that case the answer is a, so we copy a into d, we return and that's the answer. If b is not equal to 0, then we hit the recursive case. For that case, the function calls itself with the first argument being b and the second argument equal to the remainder of a divided by b as specified in the recursive definition. It probably won't surprise you to learn that MATLAB has a ready-made function to calculate the remainder for you. We use it right here, rem, and its name is the same as we used in our recursive definition. That's how it works. Let's try it. But before we do, let's put breakpoints on lines 12 and 16. The first one is at the point at which the function decides whether or not we're in the base case. The second one is just after the call to rgcd in the recursive case. If we run the function like this, we'll hit these breakpoints repeatedly. The first time that we hit one, we're in the first activation of rgcd. You won't be surprised to see that a is 63 and b is 28. If we take two steps, one, two, we see that since b is not equal to 0, we're going to call rgcd recursively. Let's click "Continue", and the green arrow, which you can barely see here, shows that we're at breakpoint 1 again. If we click up here on this little arrow of the function call stack, we see that we are now in the second activation. This is the first one. This is the second one. The white arrow down here shows where the first activation is waiting. Note that we haven't hit breakpoint 2 in either activation yet. That'll happen in a minute or two. But here in the second activation, you can see that a equals 28 and b equals 7. Since b is not equal to 0, we're going to call rgcd a third time. I'll hit "Continue", there. It might look like nothing happened because we're still at breakpoint 1. But if you look at the stack here, we're now running in the third activation of rgcd. If you check the workspace, a equals 7 and b is zero. This value b is important because it means that in this third activation, we've reached the base case. As we can see, if we click "Step" one time. By the way, it can be proved mathematically that following this algorithm, b is guaranteed to get to zero. That's a must, since it's our base case. The proof means that we will never get caught in an infinite recursion. Now instead of making another recursive call in the else branch of the if statement, we're going to simply copy a into d. Now watch over here in the workspace. When I click the, "Step" button, you'll see d suddenly appear with the same value, seven that a has. There it is. Now this third activation is calculated, it's d and it's ready to return that value to the second activation. But we haven't returned yet, which we can confirm by looking at the stack again. 1, 2, 3, we're still in activation 3. In this activation, we've calculated d, and it's seven. But neither of the other activations have a d value yet. Let's look at the workspace of number 2. It's waiting here with its a and b values, but no d. Activation number 1. Still only has it's a and b values, 63, and 28. Of course they all have x and y values, but again, no d. These are the values we started with because this was the first activation. It's time to let activation 3 return by clicking "Continue". When I do that, the d value from the third activation is copied into the d value of the second activation. There it is, d equals seven. We see the values of a and b in this activation, but we don't care about them now, only d. We're sitting at the second break point, in the second activation, and I'm going to click "Continue" again. Pow. The second activation returns its d value which is copied into the d of the first activation. Finally, I click "Continue" one more time, and we've returned to the Command window, with the final answer of seven. As we have already said a couple of times, every recursive function has an equivalent non-recursive version. That version is always iterative, but it's not always easy to write. It was easy for the factorial, hard for the Sierpinski triangle, and it's easy again for the greatest common divisor. Here's the iterative equivalent of rgcd. The function is called igcd for iterative greatest common divisor. As you can see, the recursion was replaced by iteration, hence the name. The idea is to follow the recursive definition as before, but instead of calling the function recursively, we simply change the values of the variables a and b according to the definition. This is a while loop and it checks to see if b is equal to 0, which was our base case before. If it's not equal to 0, then it iterates. It finds the remainder of a divided by b, as we did in the recursive version, and sets that into a variable called r. Then it sets a equal to b, and sets b equal to r. It repeats over and over until b finally equals 0, at which time d is set equal to a and the function returns. Well, let's try it. We'll use the same inputs that we just gave to rgcd, and we'll see whether we get seven again. Same result. Either they're both wrong or both right? Well, I'm betting they're both right or else we'll have a lot of people asking for their money back. What do you think? Do you see why recursion is my favorite part? It's an amazing tool and it's especially useful in natural language processing and in web searching. Both of which have been hot topics for many years and likely for many years to come. I love to teach it and watch students go through the three phases of recursion. One, disbelief, two amazement, and three, ho-hum. Once you understand it, really understand it right down to the stack-frame level, then it's not a big deal anymore. You know how to use it, but let's face it, the thrill is gone. I've been in phase three for many years. I wish I could feel phase two again, like I hope you just did. But that's the good thing about teaching it. I can get my vicarious thrills by watching someone else learn it. Hey, now that you understand it, I think you should teach it to somebody else and watch them go through disbelief, amazement, and if you do a good job of it, they'll finally get to ho-hum.