Performance of Iterative vs Recursive

[00:00:00]
>> Anjana Vakil: Let's see if this works.
>> Anjana Vakil: Okay, so,
>> Anjana Vakil: Let's try if we call imperative Fibonacci with like a really high number. Anybody have a favorite multiple digit number? No, okay, I'm going to give it a bunch of randomly typed integers. This is probably too big of a number.

[00:00:32]
Let's give it a three digit number, okay, it's not doing anything to be.
>> Anjana Vakil: I don't know, 5, it's not going to be but this should make it fail. Okay, so now at least we know that it's doing something, and let's find out. Good, it's some ridiculously long number here, cool.

[00:00:55]
Let's see if anything happens when I do the recursive Fibonacci.
>> Anjana Vakil: Come on, Blaze work.
>> Anjana Vakil: Yeah, so it could be that this is just not loading the test. But I think it actually might be running properly, because this is what I wanted to happen. There is a performance implication to recursion, and that is because in the way JavaScript is implemented and many languages, every time we make a new function call,
>> Anjana Vakil: We're adding something to JavaScript's memory of all of the functions that we're calling at the moment called the call snack.

[00:01:53]
So every time we call a function anywhere in our program, a new frame gets added to the call stack in JavaScript memory, and that means new memory is allocated. And what happens, essentially, is that JavaScript recursive function builds up a bunch of stack frames until it gets to the base case that pops out of the recursion and starts returning from all of those function calls.

[00:02:24]
And so, that means that it is possible to have too much recursion. We can crash the JavaScript engine. We can crash the browser window. You can do not attempt at home. [LAUGH] But the other thing is that we might get, even if we don't crash, we might get a really slow value returned, because we have to allocate all this memory and create all these new stack frames and do all of the meta level stuff that JavaScript is doing under the hood.

[00:02:56]
So often you will hear people say that recursion is not performant, and there is some truth to that. And there are solutions to that as well, which we won't super get into, but there are some links about in the epilogue. Which, in this case, a way that we can make a lot more performant recursive functions is something called tail recursion.

[00:03:25]
Which we're not going to define, but that if the language implements a particular optimization called tail call optimization, and we've written our recursive function in a particular style that makes it a tail recursive function. Then, under the hood, JavaScript can basically move a lot faster through all of that stuff because it doesn't need to keep allocating new stack frames.

[00:03:54]
I'm not gonna say any more about that today, but I have a musical talk that I gave that's on You tube that you can watch if you're curious about what tail call optimization is, and especially if you like 90s Disney musicals, because that is how it works. So [COUGH] there are solutions to these performance problems.

[00:04:15]
A lot of the time they rely on the implementation of the language and not like the features that we would use as the programmer. So we don't have control. I mean, unless you're writing a new browser engine or a new JavaScript engine inside of your browser. We don't have control over the JavaScript engine that we're using usually.

[00:04:31]
So we're gonna kinda only gloss over the performance application, but suffice it to say there are ways to make sure that you don't get so many call stack size exceeded errors or too much recursion or what have you.