Recursion

[00:00:00]
>> Kyle Simpson: I know when I bring up that word recursion, it sends shudders through the spine of many of you because you're thinking, it's so difficult and so complicated. And I want to assuage those fears, I want to allay those fears and tell you that recursion is not as complicated as is often made out to be.

[00:00:19]
I remember distinctly when I was back in school, who knows how many years ago. I remember feeling frustrated and confused by this topic. But I think it's more related to our lack of proper perspective on the topic than the fact that it is just inherently hard to understand.

[00:00:39]
And as a functional programmer, as somebody who aspires to use functional techniques, your toolbox would be incomplete if you were to say no, I'm just not ever gonna use recursion. It is a significantly important tool. So we should spend a significant amount of time making sure that we can get comfortable with this topic.

[00:00:59]
Let's take this example of wanting to count the number of vowels in a string. I've got the quick brown fox jumps over the lazy dog. That's a weird thing from the days of typewriters because that's a sentence that has all of the letters in the alphabet in it and that's why that sentence exists.

[00:01:18]
But it was just the first thing that came up on a Google search. So there you go. There's a sentence and we want to count how many vowels exist in that sentence. And you can imagine very straightforwardly an iterative approach which is what I'm doing on lines 5 through 13.

[00:01:33]
I'm setting up a counter, I'm doing a loop over that and I'm checking to see if it's one of those five letters that is a vowel. And if so incrementing my counter and then returning the number and indeed the answer is 11.
>> Kyle Simpson: The problem with this looping approach is that the looping approach is basically telling us you have to read the code to convince yourself of what it does.

[00:02:00]
You cannot simply glance at any given for loop somewhere and absolutely know what that for loop is gonna do. You have to read it and execute it, to the extent that it's written pretty simply, it doesn't take a lot of mental processing power. But you cannot glance at this and immediately know what it's doing.

[00:02:18]
So this is one of those situations where we might ask, is there some more declarative approach? And there are multiple ways to solve this problem. I am not suggesting that recursion is the only way to do so. But recursion is going to be a significant solution or an important solution that we should get more comfortable with.

[00:02:39]
Because there will be some problems where recursion is much more of the best answer to the problem. And in fact, some cases, almost the only practical answer to the problem at hand. So some problems can be solved with recursion and some problems really must be solved with recursion.

[00:02:58]
And because that is the case, it should be a tool that we are at least familiar with. The question you have to ask yourself is what would be a recursive definition for any problem. You have to understand a recursive definition for a solution before you can start writing a recursive function for it.

[00:03:17]
I know this is a shock, but as a programmer, your job is not to get the code to work. Your job is to actually first understand the problem. And so the real question here is, if my problem that I need, or the algorithm that I want to design, the solution that I want to provide, is how many vowels are in a string?

[00:03:37]
I have to ask myself how would I define that in a recursive way before I could ever start writing a recursive function. And there are in fact often multiple ways to recursively define a problem. Some problems, basically there's only one. Some problems there's two or three. So I'm not suggesting this is the only way to approach to it but I think it might be one of the most natural ways to approach it.

[00:04:00]
And it goes under the general heading of reducing the problem set, okay? So I have an undetermined number of characters, I don't know how many characters are in that string. I have an undetermined number of characters. And, in fact, if I'm trying to create a utility for this, it needs to handle any string length from zero all the way up to infinite string length, right?

[00:04:23]
So I don't know how many characters I might have to look at. But what I can say is that it would be better if I solved a smaller problem. Whatever the string length is, if I was looking at one fewer character in that string, that would be an easier problem to solve than my current length by one character.

[00:04:44]
And if I can think of it as reducing it by one character, then I can think about doing that again, and now I've reduced by another character. And doing that again, and now I've reduced by another character, and so on. And so we can, from that way of thinking, by saying, I want to reduce my problem set to something that is easier to solve.

[00:05:04]
From that way of thinking we can say the number of vowels in this string can be defined as the number of vowels in the first character, plus the number of vowels in the rest of the string. Now, number of vowels in the first character sounds like a silly question to ask, but it's basically just a binary choice.

[00:05:25]
Is it a vowel or not? So it's a zero or one sort of question. And whatever that number is, plus however many vowels are left in the string. And then, I could repeat that process by saying, I've got a smaller string, and I could say, how many vowels are in that one?

[00:05:43]
As a matter of fact, I could do that exact thing that I just described iteratively. You could set up a for loop that looked at the first character, said if it was a vowel or not, added zero or one to the count, and then reduced the string size.

[00:05:56]
As a matter of fact, that's sort of what we're doing with the index here. We're sort of indexing through the string rather than trimming the string down. But we're saying, how many vowels are here plus how many vowels do I need to count in the rest of the string?

[00:06:12]
That's the recursive, or a recursive way of thinking about the problem. So let's try to set out to design a recursive function that solves this problem. Every single recursive solution is going to have at a minimum, a base condition. The base condition is how you know when to stop.

[00:06:33]
It's just like in a for loop where you have a test condition that tells the for loop to stop, so you don't get an infinite loop. In our case, the base condition most naturally is I have an empty string. Because if I have an empty string, I can definitely tell you there are zero vowels in the empty string.

[00:06:52]
So that's what I'm checking on line 2. I'm saying, if string.length = 0, just return 0. That is a base condition. And then I need to ask, what do I do if it's not 0? Well, I need to count, whether or not the current, character is a vowel, and then I need to count, all the vowels In the rest of the string, you with me?

[00:07:17]
So how do we do that? First we, line 3 create first and we set it to 1 or 0. If string sub 0 is a vowel we set it to 1, otherwise we set it to 0. And then line 4, we take whatever that value was and we add it to the count of the vowels in the rest of the string.

[00:07:40]
String.slice with 1 says slice off the first character and give me the substring that's left. So make it a smaller problem, smaller and smaller and smaller problem. So if we started out with a string that was 100 characters, the next time we called it we'd be at 99.

[00:07:56]
And then at 98, and at 97, and all the way down until we got to a string length of 0, in which case we'd get 0. Now we'd have all those stacked up ones and zeros, ones and zeros, ones and zeros and they're all in a big giant, basically addition string.

[00:08:11]
0 plus 0 plus 1 plus 1 plus 1 plus 1 plus 0 plus 0, and we just need to compute all of that. And that's what the return statements are gonna do, and they're gonna give us back the number, in this case, the number 11.
>> Kyle Simpson: Now here's why I think recursion gets confusing for people.

[00:08:28]
I think recursion gets confusing for people because they force themselves to try to think about the implementation of what's happening with recursion. The same way they think about the implementation when they write the for loop. And this is where we get off track because recursion is not designed to be an imperative approach.

[00:08:45]
It's designed, it's conceived to be a declarative approach. Remember, declarative says I'm not concerned with how it happens, I'm concerned with the outcome. So if I can say in my mind that I understand the idea that you could count all of the strings, all of the vowels to the right of me.

[00:09:08]
I don't know how you're gonna do it, but I understand that you could theoretically do that. And I can understand the problem of whether or not this single character is a vowel. And I can understand the idea that those two things add together to give me a total count.

[00:09:21]
Then I do not need to concern myself with how that other sub problem gets solved.
>> Kyle Simpson: You can, if you want to be a computer scientist, start drawing all these diagrams of the stack frames and the function call and what the values are. But I think that's where people get off track.

[00:09:40]
It's not that I don't want you to understand that stuff, but that's really deeper like, [LAUGH]. That's like computer science level kinds of stuff where you need to track all the memory frames and all that stuff. What I want you to think about as a functional programmer, is can I break this problem into some pieces that are easy to understand?

[00:10:01]
I understand that character one is either a vowel or not, and I understand that there is some way to compute how many vowels are left in the other string. And I'm gonna add those two together, and give you your result. And that's as far as we really should have to go in terms of conceiving and authoring our recursive algorithms.

[00:10:21]
If you find yourself having to go deeper than that, then recursion might not be the solution that is best for you.
>> Kyle Simpson: Hopefully, that idea will resolve some of the frustration that you may have built up in the past about recursion being confusing to author, confusing to understand.

[00:10:44]
And the point that I wanna make here is that even though there is some degree of imperativeness in this code, this code is much less imperative than the iterative equivalent on the previous screen. If you get to the point where you start to understand the patterns that happened with recursion, and there are a couple of major patterns that almost all recursion fits into.

[00:11:06]
One of them is solve the sub problems. That's the one I just talked about, do something and reduce my problem, set it to a sub problem and keep reducing. Another one's called divide and conquer, which takes a giant problem set and says, can I eliminate half of the problem?

[00:11:21]
And then could I eliminate another half of the problem, and another half of the problem, that's another pattern for it. If you can get to the point where you understand those patterns, then you will start to be able to see a recursive problem like this and say I know exactly how they're solving it.

[00:11:36]
They're solving it with the iterative sub-problem, they're solving it with divide and conquer, etc., okay? There's a tremendous amount of math behind that and none of that math even matters. All that matters is that we can trust that that stuff works. You don't have to be able to write the inductive proof for this thing.

[00:11:55]
You just have to be able to intuit that I understand that this part of the problem could be solved and this part of the problem I can concretely solve, and now I'm done.