Data Structures and Algorithms in JavaScript

# Factorial with Recursion

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Factorial with Recursion" Lesson is part of the full, Data Structures and Algorithms in JavaScript course featured in this preview video. Here's what you'd learn in this lesson:

## Bianca now looks at the implementation of the factorial algorithm with recursion. The recursive computeFactorial(num) function continues to call itself while decrementing the num parameter. Once num is equal to one, the function returns and the results of all the calls on the stack are multiplied together.

Get Unlimited Access Now

Transcript from the "Factorial with Recursion" Lesson

[00:00:00]
>> Bianca: But then that leads us to question, and this is something we haven't answered yet in our examples, where do we do the work? And where do we even approach that base case? So let's check out an example here. You guys ready for this? I'm just jumping to the example.

[00:00:17] I'm not even making you come up with your own first. I'm just gonna tell you. Awesome, so let's say computeFactorial, and we're gonna pass it to 5, yeah?
>> Bianca: And this is a countdown inversion here. So we have our base case, if num equals 1, could also be 2, that also works.

[00:00:42] Else, you're going to return this. So our base case is when it's 1. Otherwise, it's gonna be num times whatever everything else computed to. Yeah, at this point, it might still sound like magic. And so I'm gonna do our little stack exercise with this, so we can track the numbers in our head.

[00:01:06] Ready? Any questions? All right, here we go.
>> Bianca: All right, so actually, I'm just gonna do 3 cuz it's gonna be easier,
>> Bianca: Let's do 4 for good measure, okay. So we're gonna call our function, computeFactorial,
>> Bianca: And we're gonna put it on our stack, here look, STACK.

[00:01:39] Look at that, perfect. Great, so we passed in 4. Can someone tell me what num equals right now at this point?
>> Speaker 2: 4.
>> Bianca: It equals 4, exactly. So then also in those brackets I'm just gonna put the number, since they all have the same name, I'm mapping it to a certain number.

[00:01:59] So this call created this function. Okay, and in our num equals 4. So we jump in, does the num equal 1? No, so we skip over. Otherwise, we're gonna run this expression and then we are gonna return it. So the first thing that happens in this expression is we are gonna compute this function.

[00:02:28] So nothing happens until we jump inside here. Actually, the very first thing that happens is this is gonna be calculated. So what's num minus 1?
>> Speaker 2: 3.
>> Bianca: So, that'll be 3. And we're gonna call our function, and that is gonna be the second time that we call our function.

[00:02:45] Here we are, so num === 3.
>> Bianca: Great, and then we are going to keep track here.
>> Bianca: All right, still doesn't work, not very interesting.
>> Bianca: So this is 2. I'm just gonna skip a couple steps, is that okay with you guys, following here? Cuz it doesn't get interesting until we get to the bottom.

[00:03:12] So num at this point is what? 2, and then we have our 4.
>> Bianca: [SOUND] 1, 4, 1, [SOUND], we've found it. We've found the one, yay. So this is true, and this is where the magic happens at this return statement. So we have hit our base case.

[00:03:41] This is when we want our recursion to stop. You see how it's working? We go down, [NOISE], we find it, and here we are. Return 1, okay? So when we return, we return up to the next stack. So this is 4, so we need to find our matching one.

[00:03:57] And it's gonna return 1 here
>> Bianca: Do you see how I did that? Okay, so now we're gonna return num times 1. What's num in this case?
>> Speaker 2: 2.
>> Bianca: 2, great. So this is the third one. Oops, sorry, I forgot to pop you off. This is gonna be 2, I almost said 3, that would've been wrong.

[00:04:30] If I'm ever wrong, just say, Bianca, you're wrong. So we pop this off cuz we're returning, whenever we return, we pop. Popping this off, num in this case is 3. We're gonna pop that.
>> Bianca: And that is 6. Okay, num in this case is 4. This is 24, yes.

[00:05:02] So this is 2, I'm sorry, this is the first one, here, so this is going to return 24. This has been popped,
>> Bianca: Cool?
>> Bianca: Really fast, over again. [SOUND] That's too much. So,
>> Bianca: I'm being really precise and specific, and maybe driving this in too much for some people, but the reason is, I think I've said this already four times, this is really important for tomorrow.

[00:05:49] Cool, any questions about what is going on here?
>> Speaker 2: This might be off topic, but I have a question about style I would tend to leave off the else because we already have a return in the if. Is that confusing or it doesn't matter?
>> Bianca: Yeah, it doesn't matter, not to me.

[00:06:22]
>> Bianca: Cool, yeah, sometimes for my examples, I make them more verbose to just show a point, I think for this one, I don't know, I'm not-
>> Speaker 2: Yeah, it makes sense.
>> Bianca: Doesn't really matter.
>> Speaker 3: Some people who aren't super familiar with JavaScript might not realize that if you do it, like some languages aren't like that.

[00:06:39] You know how like you can do return and if it doesn't hit this, then you can also return? It's a stylistic choice.
>> Bianca: Yeah, okay, yeah.
>> Speaker 2: A question from the channel.
>> [SOUND]
>> Speaker 2: What does the 3 in curly brackets represent?
>> Bianca: The 3? The 3 represents the, it's like a name for the function, I gave each function a number.

[00:07:03] So this first function is number one. And here we are in our stack, this is not actually happening, this is happening all under the hood. We're first calling this function one, and so it's just mapping so that we can keep track of which function is which. So for example, when this function returns, we know that it returns from this call.

[00:07:25] So it's just keeping track. Yeah, mm-hm?
>> Speaker 2: I do wanna offer a clarification that you're right. Simplistically, it's the position in the stack trace for that call.
>> Bianca: Yeah, absolutely, that's a good way to put it for sure. Cool, all right, were we are, factorial.
>> Bianca: How we feeling about factorial?

[00:07:58] Feeling good about it? Great, it's one of those things, I'm gonna talk about it, then when you get to it, then you're like, crap, what's my base case and what's the work that I'm trying to do? That's gonna be the challenge and that's the challenge to work through and that's okay.

[00:08:17] All right, so I have some more examples here, but I feel like we're good. So I just wanna have a vote from the audience. First one is, we will keep talking about these different examples of recursion that are simple. Or the second one is we can just hop into the exercises.

[00:08:43] In like a few minutes, I have a couple of more slides. So hands up if you want me to keep talking about these examples because you could use the further clarification.
>> Bianca: And then keep your hands down if you wanna do your exercises. Okay, I think we have a unanimous vote, awesome, great.

[00:09:05] So they're here for your reference if you want different ones.
>> Bianca: Let's see, so recursion versus loops. Loops, as it stands, are more performant than recursion because of something called tail-call optimization, which appears for us magically in ES6. If you wanna learn about that, here are some links.

[00:09:32] There are lots of different, there's certain ways that you need to go about that to utilize ES6 tail-call optimization. But we're not gonna talk about that today cuz it's kind of beyond our scope here, cool. Common patterns for recursion, so we have wrapper functions and passing memos or accumulators.

[00:09:56] [SOUND], failed to save. That's okay. So wrapper function is when you just have a function inside of another function. So we can call recurse here, pass the start time. And again, these are all just loops. And so that's one way. You could save stuff in here.
>> Bianca: Bye.

[00:10:28] You can save stuff in here, you can do work onto a variable saved here. That's a better way of doing it than how we were doing before with the tracker, remember we were using the tracker before? So this is one example. I call this a wrapper function, I don't think that's a technical term for it though.

[00:10:47] And then memo or accumilator, you can pass, just as we were doing in the factorial, we can pass it along.
>> Bianca: So every time we recurse, we can pass along whatever value that we want that's getting closer to our base case, or whatever result we're looking for. You can just pass it through.

[00:11:07] Just be mindful of the order in which it's being evaluated cuz that might change how you're gonna do things.