This course has been updated! We now recommend you take the Functional-Light JavaScript, v3 course.
Transcript from the "Recursion" Lesson
[00:00:04]
>> Kyle Simpson: Recursion's one of those things that tends to bend people's brains. I find that sad. It's kind of like, if we look at state of most adults. Now I know in a developer crowd we have some selection bias here if I ask most developers, what do you think about math?
[00:00:22] Probably not gonna get a lot of negative reactions from things. Some people are probably very pro math. I certainly as a computer scientist, I took a whole bunch of math classes. So, math doesn't scare me but if you ask the general populus about math, well, some people will just have a visceral reaction.
[00:00:41] And I find that so sad, that math is not just something that some people, that many people would say, math's fine, but I don't really care that much about it. That would be fine to me. What's sad is that math has this negative connotation in somebody's mind. I think recursion is similar.
[00:01:01] Recursion is often times one of those things kinda like regular expression as another example. It's a very polarizing topic, some developers will say yeah, I'm okay with regular, maybe I don't use them after, but I'm okay with them and some people like, no. Absolutely not, regular expressions are way too confusing and recursion seems to be similar.
[00:01:22] It's another one of those things we want to try to practice wrapping our brains around. So put simply recursion means a function that you define, it's going to perform some action and you want for that function to stop calling itself, it's going to call itself as part of the solution but you want for it to stop calling itself when it reaches what we call a base case.
[00:01:47] So the two characteristics of a recursive function are, that there is a base case which stops the recursion and there is a recursive call. Meaning, the function is literally using it's same name to call itself, to invoke itself from inside of itself. Now, a closely related concept is something called mutual recursion.
[00:02:07] If recursion is a single function calling itself recursively until it reaches a base case, mutual recursion is two or more functions calling each other until they reach a base case. Same principle. Just whether there's one or more. Recursion is incredibly important and incredibly useful. Make a little side note about recursion for a moment.
[00:02:30] One of the reasons I think programmers don't really spend much time, at least programmers in the JavaScript community, don't spend much time thinking about recursion. One of those, of course, is it can be hard to wrap your brains around. But another reason is because many people have observed that even if you understand recursion, it may not be very practical to use in your programs for certain types of problems, because there are physical limitations applied to our programs because of the nature of how recursion works.
[00:02:58] Recursion is one of those great, great, great examples of works in theory sometimes doesn't work in practice. What is that practice? Well in theory, you write a recursive program assuming unlimited CPU and unlimited memory, but in practice has anybody in here got unlimited CPU and unlimited memory, absolutely not.
[00:03:20] Doesn't exist, even in the Amazon cloud it's not unlimited, okay? So recursion seems great in theory. I can make every single thing I do recursive, but in practice certain things can be done recursively and other things are gonna fall apart. Now there's a reason for that, and the primary reason for it is not even the CP, the primary reason is memory.
[00:03:43] When one function calls another function, even if that function is itself, when one function calls another function, the first function call allocates in memory what we call a stack frame. I'm trying not to get too complex with it, but a stack frame's a place in memory where all the variables and state are held.
[00:03:59] And the program counter as it's walking through. When it finishes with that stack frame it throws the stack frame away, so when a function finishes, it throws that memory away and it reclaims it and reuses it, okay? So, when one function calls a second function, a second stack frame allocation happens, so if you have A calling B, and B calling C, and C calling D, and D calling E, you now have five stack frames that have been allocated each one taking up a little bit more memory.
[00:04:26] Now, in your programs, you probably have functions calling other functions calling other functions. But I'm willing to guess that you probably at most have, let's just arbitrarily say you've probably at most ten levels deep in a run stack. Even when you factor in your libraries, 10 maybe 15 it's just not very common to go beyond that.
[00:04:48] So back in the day old IE had an actual arbitrary limitation of 13. You could go to 13 but once you went beyond 13 it would just simply cut you off and say the call stack is too deep. Had nothing to do with whether it was recursion or not.
[00:05:03] Just simply you had too many snap frames allocated, and we're just gonna physically cut you off at that point. I don't know where they arrived at that 13 number, I don't know if that was something physically with the way the engine worked, whether they just arbitrarily said, that's too much memory to give away.
[00:05:18] I don't know. But 13 was the arbitrary limit. Now, modern browsers the limit is up like 10 or 20,000. But there has to be a limit because if they didn't have a limit, you could have a runway program that ran out of all the memory. And especially when we're talking about mobile devices, the single worst sin that you can commit is running a device out of memory cuz guess what happens when it completely runs out of memory.
[00:05:43] It shuts off. That's the worst possible user experience. You ever had an app that crashed your phone, and your phone literally restarted as a result of it? You know what they did? They ran out of memory. They didn't have any kind of memory controls and they ran out.
[00:05:57] So JavaScript said that's unacceptable, to just simply run unbounded without memory. Without any kind of memory restrictions. Because programmers can't think about memory restrictions in terms of amount of memory, they had to restrict it in terms of depth of the call stack. So in chrome I think it's 10,000 or 20,000 or something like that.
[00:06:17] Other browsers have different arbitrary ones. You're never gonna write a program that has intentionally 10,000 calls. Right that would be crazy, but it's super easy to get into that case when you're dealing with recursion. If you have a problem size that's a hundred, your call starts gonna maximum be a hundred.
[00:06:36] When your program size grows to a thousand now your call start gonna be a maximum of a thousand. When it grows to 10,000, we're starting to get close to the point where it might fail. The engine might throw an error and say, you went too deep. So that's one of the main reasons why recursion has been this theoretical thing that some people could deal with but in practice doesn't seem terribly easy for us to figure out how do I reason about a problem that has a bounds to it?
[00:07:05] Because as computer scientists we typically like to reason in un-bounded form. We'd like to assume that our function our program would run with regardless so much data in there is. And if we know that there are some arbitrary limit we just simply don't do recursion. That's one of the main reasons why this is been not a technique that has been used.
[00:07:22] It's incredibly powerful, is it powerful from a functionality perspective? Not so much. You know what's it's powerful for? Inexpersivity, it makes more graceful expression of many sorts of problems that we wanna solve. The recursive definition of a problem is often much more graceful to look at and understand and put your wrap your brain around, than the iterative version which has the overhead of a loop or whatever.
[00:07:49] They are isomorphic of each other, the iterative version and the recursive version of solving a problem if they come up with the same result, they are isomorphic, you can transform between the two, and in fact many compilers in non-JavaScript languages do in fact do that. If you write a recursive program they do what's called unrolling.
[00:08:10] They write a loop, basically, and they keep track of the state in a loop so it's not allocating all those stack frames. That's how many of the compilers handle recursion. But JavaScript does not have that sort of technique in it. And so for the longest time we've had this arbitrary limit.
[00:08:26] The reason I bring all this up is to say, recursion is a tool that we ought to have and it's something that we can reclaim back into our scope, back into our mindset of tools available to us as of ES6 because there is an optimization that is required in ES6 and that's actually a unique thing.
[00:08:45] I'm not sure if I know of any other example in JavaScript, and I can't really speak for other languages, but I'm not sure I've ever heard of a case where a language specification requires a particular optimization. Optimizations are typically thought of as purely implementation details that's up to the JavaScript engine developers how to make it happen.
[00:09:08] They very rarely get into discussions about optimization, except for when a browser engine author might say something like they're on TC-39. They may say well, we're not gonna implement that because it would be too difficult to implement based on the way our engine works. That's the sort of feedback they typically get.
[00:09:26] But usually, we never see the specification actually say you are required to do this particular kind of optimization. So this is a very special case, it's one that we ought to pay attention to. Essentially, the optimization goes by the name TCO, tail call optimization. There's another formal term for it, proper tail calls.
[00:09:48] What this says is, if I have a function that calls another function, whether it's recursive or not is irrelevant. If I have one function, function A calling function B if the way that's it's calling function B is at the very last statement of that code path, and it's returning whatever B returns.
[00:10:09] So in other words, if in A, at the very end of that code path, I say return B(whatever; that's what a proper tail call looks like. When there's a return with a function call and nothing else after the function call. That's a proper tail call and what that means is if the JavaScript engine can identify that that's the case, it can say the current stack frame that I'm using I don't need anymore.
[00:10:35] So I don't need to make a new stack frame for B's call I can reuse the stack frame for A. Which means if all of my recursion is done with proper tail calls, then I can do arbitrarily deep recursion with 0 of 1 memory usage, constant memory usage.
[00:10:55] Just one stack frame reused over and over and over again. It's a massively important. It's not new to JavaScript, that's been around for decades. But it's a massively important optimization that reclaims recursion as something that we ought to care about because now it becomes practical to use, if you write with proper tail calls.
[00:11:14] Not all recursion is normally expressed in proper tail calls. Virtually all recursion can be rewritten to use proper tail calls, but that technique is difficult. And we're not gonna really dive into that, but I do cover that in my ES6 book. So, that's why I'm talking about recursion cuz it's something that we should care about, not just theoretically but now practically.
[00:11:35] As engines start to get TCO implemented, it's something that we'll start to be able to revisit and use more practically in our programs. And by the way, I do cover in that ES6 book, I do cover a technique by which you can write a function in a certain pattern, where if TCO is there, we'll just simply run unbounded, relying upon proper tail call recursion for an arbitrary depth.
[00:11:59] But it will detect if an error occurs because you're in a non-TCO engine and it will redo in batches. So there's a pattern for which you can write this code now and that will still run okay in older browsers. It's a little more manual but it is possible to do if you needed to bridge the gap.