Recursion Performance & Proper Tail Calls

[00:00:00]
>> Okay, now let's come back to that performance question. I'm sorry were there questions?
>> When you using I mean with any function with especially with, with, with recursive functions. Do you need to have more that your base cases if somebody were to provide a negative number, would you need something to check for that?

[00:00:24]
>> Great question. What about error handling? What about, if somebody passes a maybe a negative number or a mad they could pass a string or some other thing? That's not right. And I have not handled that. And these are reference implementations of sort of assuming that we're getting the right kind of value coming in, and this is maybe, opens up another can of worms that we're not gonna talk about today.

[00:00:49]
But something else that goes hand in hand with functional programming a lot is types, strongly typed data, so data where we have a guarantee in the way the function is declared that it will only take in, a certain type of data. And sometimes, maybe that's a type of data that could be one of several types, or sometimes it's, really restrictive, it has to be a positive integer, or something like that.

[00:01:18]
And so a lot of the times in functional programming, you will see types. Used to kind of guarantee that that determinism because I'm not going to get an error because I, I tried to add to, I don't know custom objects together that don't work with the plus operator, or, or because I'm not handling a particular case a negative number or something like that.

[00:01:43]
So a lot of the times you will see in functional, free or functional languages like Haskell, let's say you will see types used as a way of doing that. And also you will see in JavaScript, a lot of folks that like to write code in a functional style using some of these more typed versions like type script to help them not worry about that and have that guarantee going in that whatever we're operating on, we know exactly what it's going to look like.

[00:02:14]
And the the language or the type system is gonna kind of figure that out for us but in the absence of that in a vanilla JavaScript framework like this where we don't have strongly typed data and n could really be anything and JavaScript doesn't care. It could be undefined, it could be whatever.

[00:02:33]
We would wanna handle that the same way we would in any JavaScript code. Great question. Okay, so now, the question of performance came up a lot before or a couple of times before. What are the performance considerations? Is recursion and iteration, do they give the same performance? Will there be any problems?

[00:02:55]
So did folks have fun trying to break their notebooks here with the different inputs to these functions. I saw somebody had somebody had fun crashing their, notebook I think, sorry there is a small bug here but yes okay. So if we use, let's say we just change the values here.

[00:03:18]
So, the iterative one, 40 seems to work 50 seems to work okay, let's try recursive. So four seems to work. 14 seems to work 20 seems to work 40, it's real slow, it's real slow. It worked, but it was real slow. But if I were to go up to something like 100 and what was it?

[00:03:49]
104, it's thinking, it's thinking, it's thinking, it's thinking, it's thinking. It's still thinking. It's taking it a very long time. Okay, well while we're talking about this, clearly we can see that the iterative of Fibonacci one did not seem to be struggling as much as the recursive Fibonacci one.

[00:04:19]
Anybody have ideas about what is going on here with this performance difference?
>> The recursive function is calculating the values again and again. For 40 it will calculate. I mean it's a recursive tree right. So it will calculate 14 many times and under those 40 values it will calculate 20 many times and 10 many times and also like each recursion is I mean, it calls a new function on the stack.

[00:04:52]
So it also wastes memory.
>> Okay, so I heard a couple of things. So we have on the one hand we have that this recursive function here is actually making two recursive calls. So it's doing a lot of work. And it's going to be making the same call.

[00:05:15]
So it's going to make let's say it's a, we pass in four. It's going to call recursive Fibonacci on two and then recursive Fibonacci on three. And then when we call it on three, it's going to call it again on one and then again on two. So we've got kind of like multiple times that we're making the same call with the same arguments.

[00:05:37]
So that's one issue. And then the other thing that was mentioned was the call stack. So you may have seen a minute ago we had something called a too much recursion error or an internal error. And I think I'm going to need to, so FYI folks if you ever get into a sticky situation like this in observable.

[00:06:02]
You can reload the page with what's called Safe Mode. So if I put safe on the end of this and I reload the page, I will get a version of my notebook. That allows me to see just the code, it's not going to actually run any of it so that I can fix something that might crash or hang the page.

[00:06:26]
And so in this case, I'm just gonna, put this value back down. To four so that we're not crashing the page anymore so that we can talk about it and then I'm gonna reload not in safe mode and now things work again. Okay, great. But we did see we saw it was really struggling, right.

[00:06:47]
And so, [COUGH] We may have seen earlier a, too much recursion error. Let me see if I can get it to do it again. So you may have seen something like this internal error too much recursion. This is the message you'll get. I'm in Firefox right now, you might see call stack size exceeded in some other browsers, or Stack Overflow might be another message.

[00:07:10]
So this is another problem that we're running into, which is a tricky thing for recursion as well. So to recap, we've got two problems with recursion. One is that in a function like recursive Fibonacci where I've got this double recursive call here, I, I'm kind of doing work multiple times doing the same work multiple times and one solution to that that we're not going to get into but you might want to look up on your own is something called memoization.

[00:07:42]
So memoization is a sort of way of caching the results of those functions. So that when I call recursive Fibonacci of two, twice, once in the first recursive call, and then in the second one, I don't have to repeat the computation, I can actually just use the value from the first time I called it.

[00:08:05]
So if you're curious about how that works, you can look up Memoization in recursive functions. And then the other problem we saw was this too much recursion or Stack Overflow error, which is because every time I call a function in JavaScript and it mostly. Languages, I have to add a new frame for that exact call of the function to what's called the functions to the call stack.

[00:08:30]
And the call stack is on my computer and my computer has a finite amount of memory. So we're trying to do a operation recursion which could theoretically go on forever. There's nothing conceptually or mathematically preventing that recursion from going, going, going, going, going, going, going, going going, however, we're doing that potentially infinite operation in a finite resource environment, so how does that work?

[00:09:05]
So we keep adding frames to the stack. And eventually if I have a really, really deep recursion because I've got a big input number or I've got a large array I'm operating on or something like that. I'm gonna run out of room and so I'm gonna get this error call stack size exceeded or too much recursion or whatever my browser tells me.

[00:09:21]
The solution to that or a solution to that is something called tail recursion and tail call optimization. Now we're not gonna get into the details of how that works, but TLDR the quick version is that tail call optimization is a feature of some runtimes like my JavaScript engine, where it can perform an optimization on my recursive code.

[00:09:50]
If, if Importantly, I write that recursive code in a particular way. So instead of writing a regular recursive function, I write something that's called a tail recursive function. Now again, we're not going to talk about exactly what that means, but a year or so ago, my friend Natalia Margolis, and I wrote a musical tech talk about it.

[00:10:16]
So if you're bored one day and want to learn through song how tail call optimization works, you can check out that video. Or you can look it up for yourself in JavaScript. In es six or es 2015. JavaScript introduced a feature called Proper tail calls that allows you to in certain engines, like Safari, for example, you can take advantage of this tail call optimization thanks to the language feature proper tail calls that was added in ES6.

[00:10:49]
So those are some terms you can look up if you want to read more about how to get around these performance issues, and in functional languages, you would see that kind of thing often built into the language so that you don't have to worry about it. You don't have to jump through hoops with it.

[00:11:04]
But in JavaScript because it's a multipurpose language, we have to think a little bit more deliberately about it. And in fact, JavaScript itself had to change in order to make those work around as possible. So, that is I will leave you with and answer to some of the questions that came up earlier about, what about the performance?

[00:11:22]
Aren't we gonna blow the call stack? Yes, yes, these are concerns for functional programming there are workarounds. But honestly, this was a huge problem for the functional programming community to solve. It took a really long time to figure out how to combine this recursive way of thinking about solving problems and this pure functional mindset.

[00:11:45]
With the constraints of working on a computer architecture that is just limited in its resources. So that was one of the reasons that functional programming kind of took a long time to develop and kind of hit the mainstream of software development. So these are some really interesting things to dig into, in my opinion, once you start learning about like, what are the implications of working with functional code.

[00:12:09]
What does that mean for everything that has to change in our way that we even think about computing on a processor like this. So I hope you all will have a lot of fun after this course digging into some of the resources that I'm going to leave you with at the end of the day.

[00:12:24]
To find out more. Okay, so the question is, is tail call optimization a feature of JavaScript engines? Yes, it is something that you as a programmer can't implement the language itself has to implement it. And so then the second part of the question is do all JavaScript engines support it?

[00:12:43]
Do all JavaScript engines have this implemented the answer to that is No. For example, I am in, in Firefox right now, which does not implement tail call optimization. So, even if I write my code in a way that could work with tail call optimization, if I run this code in Firefox, we won't see it work.

[00:13:03]
But if I run it in Safari, Safari does implement tail call optimization. So we would be able to take advantage of that. If I write my code the right way, I would be able to take advantage of that in Safari node and V eight. So V eight the engine that powers chrome and node.

[00:13:21]
V eight did implement it. In a few years back in the version that was accessible through node six, it was behind a feature flag. You could use the harmony feature flag, but there are some. Drawbacks to doing tail call optimization, which we'll get into a little bit in the talk that I linked and which you'll also find out if you read more about some of the resources that I've linked in some of the terms that I mentioned that you can go Google or DuckDuckGo or use your search engine of choice.

[00:13:55]
Suffice it to say that when you do tail call optimization, you're messing with the call stack. You're messing with the, engines history, of what has been what is being called. And so one problem for example, is that then, if you're trying to. Trying to debug that, or if you're trying to debug, exactly where in the call stack, something went wrong.

[00:14:19]
That introduces complications because you're kind of like rewriting history a little bit. In any case, this is a reason why those features in VA never really hit the mainstream. So we don't have tail call optimization in Chrome. We don't have tail call optimization in the latest versions of node.

[00:14:38]
So Safari WebKit engine is is the the safari engine is the only browser engine that I'm aware of that actually implements this