Functional-Light JavaScript, v2 Recursion Introduction

Transcript from the "Recursion Introduction" Lesson

[00:00:00]
>> Kyle Simpson: Let's turn our attention to recursion now. And I'm gonna fully state upfront that I understand recursion can feel quite intimidating, certainly, for the first several years that I was a programmer. I had heard about recursion and seen it done. And had no idea nor any desire to try to tackle it myself.

[00:00:21] It seemed a very strange way of twisting my brain to think about a problem differently that I saw no value, no benefit for. And as a matter of fact, even once I learned how to do recursion, I didn't really have a very clear crisp statement of value for why recursion was necessary.

[00:00:40] And it was not until I started digging into functional programming concepts that I really began to develop a sense of why recursion would be useful. Obviously, there are some functional reasons, some behavioral or mechanical reasons why recursion be helpful with certain kinds of problems. But I'm talking about beyond that moment where, I need to do a recursive dissent of a binary tree.

[00:01:06] Well, that clearly seems more like recursion than to try to do it iteratively. So there are things that recursion is better at in terms of algorithmic. But even if we didn't talk about algorithms, because, quite honestly, I just don't write a whole lot of depth first traversal of binary trees in my everyday coding.

[00:01:30] Maybe you do, but that's not something I do a lot. So for a long period of time, recursion felt like this one little highly specialized tool. And I wouldn't really pay that much attention to it. Several years back, I heard Doug Crockford give a talk. He was talking about the new things coming in ES6.

[00:01:50] And he suggested that now that ES6 was gonna have full proper support for a thing that we call proper tail calls. Sometimes, it's often referred to as TCO, tail call optimization. He said, as soon as JavaScript really gets that, I'm not gonna write loops anymore, it's what he said.

[00:02:13] And it twisted my brain again and I said, really? You would never write a loop again, you would do this only with recursion. And I knew I academically what he meant. Because, essentially, the calls in a call stack, especially if they're recursive, have the same shape as the iterations in a loop.

[00:02:31] So you can clearly model them, and they can be thought as isomorphic. That's a fancy way of saying two different behaviors represented differently. The same behavior represented two different ways. So you can think recursion and iteration as sort of isomorphic to each other in a sense. But I didn't really ever take that seriously, like, wow, I would really do that.

[00:02:57] And as I dug more into functional programming, I saw that, more and more of the time, problems that I probably would have defaulted to using a for loop with, I saw the functional programming using recursion. And I began to develop this deeper appreciation for why this tool is a necessary part.

[00:03:15] It's not just this highly specialized thing that we should never really take out of the toolbox, but something that we should regularly have at reach. And that means, of course, that we need to not just have a very surface level understanding, but a deep understanding of recursion. And a deep understanding of the meaning and the purpose behind it.

[00:03:38] If you have any familiarity with math, if you recall back to math class, you probably encountered at some point or another the little sigma symbol used to describe the summation of some series of numbers. Summation of x would literally just say, from one to whatever you were summing, add all those numbers up.

[00:03:58] And you could say, summation of x squared or whatever. And the notation is kind of like what recursion is doing for us. And so that's why I wanna talk about that for a moment. I really think that the benefit of recursion is that it moves us in the direction of declaring what we want to have happen, that declarative style.

[00:04:22] And away from the imperative of this is how to do it. So given some list of values that I need to perform some set of operations on. Instead of looping over those values to perform the operation, I could express that as recursively reducing the list one at a time, or two at a time.

[00:04:42] Or whatever the appropriate thing is, until I don't have any more items in the list to process, and then I'm done. That is the same thing as giving a new item, when we do that in the call stack, and each new frame in the call stack has a shorter list to deal with.

[00:04:59] It's the same thing as iterating through a list where you have an index variable that's updating. And there's a lot of things that we can erase or make less obvious in our code. There's a lot of details that can often distract us. When we move away from that imperative form and start to declare things.

[00:05:19] So it's similar to that sigma symbol, because a mathematician sees that symbol and immediately knows what it represents. At glance I know, okay, I know that's the sum of that geometric series or whatever the thing is. And what I'm hoping is that I can show you a perspective on recursion where that starts to become a little bit more true of your code.

[00:05:40] That you declare your recursion in such a way that, at glance, somebody can see that and recognize, I know what that's going to do. Just like if you had worked with binary search trees a bunch. And then you saw somebody implement a depth first recursive algorithm to traverse that list.

[00:05:59] You probably wouldn't need to read through each line of that algorithm to figure out what it was doing. That would probably just be familiar enough that you could recognize it. And I think we can actually go one step further in terms of not just that we implement it, but the style of how we implement it.

[00:06:17] To help us get a sense of when I glance at that, I know what that's doing. And not just us, but, also, the other readers of our code. So consistent with all the other same principles that we've tried to apply. We're trying to move from the imperative to the declarative.

[00:06:32] I think recursion is a very important tool in that mix. It is our sigma symbol notation, if you will, to help that part of the code be more recognizable. And recursion can certainly be done poorly, there's no question about that. But I think, also, recursion can be done well.

[00:06:51] And I think there's as much of an art to that as there is a science. So if I start out with a list of numbers and I talk about the iterative approach to that, this is one way you might do that. If you were given that interview question, sum up a list of numbers that we pass in.

[00:07:08] You might start out with a running total that var sum = 0 on line 2. And then simply loop over it and add the items into the sum, and then return the sum. Pretty straightforward, the terminating condition for you in that, that stops the loops, is when we've gone through the whole list of numbers.

[00:07:30] Now, that's fairly straightforward. Certainly probably not groundbreaking to any of you. But you might not have ever thought, what would it mean to sum up a list of numbers recursively? And so we need to talk about two different things here. One is gonna be the notation choice that we use, the syntax choice.

[00:07:50] And how we name things and position things, that's one thing to consider. The other thing to consider is, algorithmically, what would that mean? And I was hinting at that just a moment ago when I said A loop where the index is moving through the list can be modeled generally recursively as the list getting shorter and shorter.

[00:08:12] Because if you think about a list of five items, and you move the index from position 0 to position 1. If we went about this recursively, we could say that same list of five items, let me take the item off the list and do something with it. And now I have a shorter list which is just like if my index have moved to that position.

[00:08:32] So each time I paired down the list, it's like moving that iterator through the indexes of the list. Now when you think about recursion and if it is one of those topics that can be intimidating to you. I think it's often because we try to get our brains wired up or wrapped up in the how does it work.

[00:08:56] And this is one of those places, I don't necessarily always say this. But this is one of those places where the intent is to actually not worry so much about how it happens. The intent is actually to take that detail of iterating through a list and processing it item by item.

[00:09:14] Take that detail and try to make it as declarative as possible so that the engine takes care of that. And what you're left with is a more simple statement of the problem. So if you can twist your brain to think about recursion as an isomorphism of the iteration, as a way of expressing the iteration.

[00:09:33] Most of the time you can figure out a recursive way to express a solution to any given problem that you're doing. Of course if you're not doing iteration, you might have to get a little bit more clever. But most problems involve iteration, and most iterations can then be expressed as recursion.

[00:09:49] So this summation of numbers. If I were to take that idea to say, [COUGH] the way I paired down my list is to take the first item off the list. And process it and then recall myself with a shorter list and a shorter list and a shorter list.

[00:10:04] What would be our terminating condition? Here our terminating condition is i has gotten to the last item in the list. What is our terminating condition when the list is getting smaller?
>> Kyle Simpson: How about list of length 0, or length of list 1, I guess, would be the appropriate way to think about.

[00:10:29] When my list gets down to 1, I don't need to recurse anymore cuz I've dealt with all the values, make sense? Another way to state this if you were trying to think about it more mathematically is that the sum of a list of numbers is the same thing as the first number plus the sum of the rest of the numbers.

[00:10:50] And you would literally write it out that way if you were writing the recursive definition say in mathematical notation. You'd say the sigma of n is equal to n plus the sigma of n minus 1. You'd literally say it like that, because it implies that there's a recursive property to this solution.

[00:11:08] So let's try to express in code as much as possible, let's encode into our code, those ideas. To try to help our code be as recognizable of that algorithm as possible. There's nothing wrong with this algorithm, it will perform well. But if someone doesn't know what the algorithm is doing, they're going to have to read through each line to understand it.

[00:11:29] That's the hallmark of imperative code. Can we get to the point where somebody won't have to obsess so much about the how, and recognize the what. So the first thing I'm gonna do is try to signal that idea that there's the first item and there's everything else. You might not have seen the change that I made, but all I did now was name the first parameter in the parameter list, and I named it sum.

[00:11:55] So now I don't need a variable to keep track of the rest of the items. And I'm signalling something here important, which is to say, if you were to call some iteration the function sumIter with only one value, it is its own sum right?. So that's why I named that first parameter sum as opposed to num1 or something.

[00:12:18] I named it sum because in our base case where there are no more numbers it is it's own sum. And my algorithm actually takes care of that although it's not terribly obvious. My algorithm takes care of that because the nums array here would already be empty if only I passed in one number.

[00:12:35] Which means the for loop would never even execute. It would do that initial check for i less than nums.length, it's not. When i = 0 nums.length is 0, it's not less. So it would never do the for loop, and what would it do, just return the sum. So I just tweaked the way I expressed the same algorithm to begin to try to signal to somebody,

[00:13:00]
>> Kyle Simpson: That there's a recursive nature to the solution that I'm heading toward okay? It would not have been obvious to you to do that except for the fact that where we're headed is to try to announce they will. If that's my iterative solution what is the recursive equivalent?

[00:13:20] So let's think about how every time some Iter gets called it's automatically sorta taking the first item off the list and shortening the list by one item. That part's already happening for us, we're not gonna need to do any of that work. So really all we need to do is just process something with the item and sum, and then call the sumIter with the remaining nums, if there are any.

[00:13:48] So I'm gonna start out my sumRecur with that exact same signature. And then I'm going to show that when I call it I'm doing the same thing. And you'll notice that there's a match now between the sum variable and that first number, 3. If I didn't pass any of the 4, 5, 6, 7, 8, 9, immediately we would expect it to just return me back the sum.

[00:14:13] So what is our terminating condition, or in recursive terms, what is our base condition?
>> Kyle Simpson: How would we know that the number 3 was the only thing that was passed in?
>> Speaker 2: Your nums would be empty.
>> Kyle Simpson: If nums.length is equal to 0, right? That's our base check, our base case.

[00:14:42] And then if nums is greater than 0, that means there is at least one number in the list. Then we need to call the sumRecur function with that shorter list. And whatever it returns, we need to add it to sum. So let's just encode that directly in code.

[00:15:02] If nums.length = 0 return the sum otherwise return the sum variable + the summation of the rest of the list.
>> Kyle Simpson: Now you notice in that analysis that I'm not really getting all wrapped up around, well on the third stacked frame what is the value of this and the value of that.

[00:15:33] And all of those questions that oftentimes trip people up and intimidated people with recursion. I'm really trying to think about it more, almost from this high level, almost abstract sense, it's almost notation. We're still writing code, but it's almost notational in nature. And I'm allowing all of the details of that stepping through to be encoded in a couple of different places.

[00:15:58] One, I've encoded some of that information into the parameter list. I've allowed the parameter list To suggest that we're gonna pare down one, the first item off the list each time. And by the way, there's a name for that in functional programming. That's called the head of the list, and everything else is called the tail.

[00:16:15] So I literally could have called this head,...tail, if we were trying to use the actual sort of official terminology.
>> Kyle Simpson: So did you see how I went about that thought process?
>> Kyle Simpson: It's starting first with what would if I was gonna do it iteratively? And then saying well what's the recursive algorithm to express the solution problem?

[00:16:43] And for things where you're just looping over a list, it's usually just reduce the list by one. Sometimes you reduce the list by two, or three, or four, or something else. But generally, the list is gonna get reduced each time until the list is at some base condition, like empty, or one item in it, or two items, or whatever.

[00:17:04] Generally that's gonna be the case. Now there's something about this expression of the algorithm that has always, a bit bugged me. It's more like an implementation detail, and generally we shouldn't get too worried about micro nuances of performance or implementation. But there's something that's always bugged me about this particular kind of algorithm, because what you'll note is that if nums is length one.

[00:17:36] That is like if I called sumRecur and I passed in 3 and 4, that's it. Well, we would not be at a base condition, because the nums.length is 1. So what we would do is say return 3. On line three, we'd say return 3 + and then we call sumRecur with just a single item in it.

[00:17:57] And that would immediately come in to the next recursive call, hit the base condition, and come right back out. There's in a sense sort of a wasted function call. If I could know now that I don't really need to pass it in just to get it right back, I could save that last function call.

[00:18:19] And again the performance difference would be almost irrelevant especially at scale. This is really just something that more bugs me that if I already know that I've got this list of numbers, I kinda already know that addition always takes two numbers. I could change this algorithm to say, why don't I list off the first two items of the list?

[00:18:43] Cuz I'm always gonna be able to put those two together or at least take off the first two items in the list and if the list is empty then I know all I need to to do is add them together. If the list is not empty, put one of the items back on the list and send it back in.

[00:18:58] Cuz either I'll do those two, or it'll do however many are left. So let me just tweak the expression of this algorithm just slightly again. And now I've got as you see on line 1 I've got the sum parameter and the num parameters. So I've listed the first two items.

[00:19:20] So it's kind of like I'm peeking ahead at the tail. I'm naming the first item of what we would normally consider to be the tail and I'm peaking at it, just to see if I am really done yet or not. Just eliminating one recursive step here. If I'm at the base case where the numbs is equal to zero, that let's me know for sure that I've passed in two numbers, the sum and the num, so I just returned sum plus num.

[00:19:50] But if nums has more in it, let me just put that item kind of back on the tail if you will. So on line 3, I call sum plus and when I pass the list I add num back in. So I just put it back on the stack to be considered on the next iteration.

[00:20:08] I'm really only reducing my list by one each time but I'm doing a look ahead to avoid that last unnecessary call. And I fully understand that looking at this you would say that never occurred to me, why would I ever do that? It's just a little bit more noise.

[00:20:24] Why would I ever do that? There is a reason for that. You won't fully understand that until a little bit later. But there is a reason why I might choose to go that route with the expression.
>> Speaker 3: What if you already passed in one number?
>> Kyle Simpson: I'm glad you asked that question.

[00:20:42] I was just about to say. There is a subtle point here, which is that we've eliminated one of the potential base cases, or at least we're not covering one of the potential base cases, which is calling it with only one number. You can obviously solve that problem by adding in another if statement.

[00:21:00] If sum is a number and num is undefined then you know you're in that base case. I'm leaving out those kinds of more trivial details but certainly there's lots of other things you could do. You could do validation to make sure that every item is actually a number.

[00:21:20] There's a bunch of details that we're sort of glossing over. And that is one of them, is that in choosing to go this direction, I've implied now that one of the preconditions to use this utility correctly is you need to give it at least two numbers.