Recursion Practice: Factorials

[00:00:00]
>> Let's hop back over to our recursion. I wanted to give you a couple of examples here. Just because we're about to hop into some really heavy recursion, so I wanted to make sure that I really hammered home that you got recursion done pretty well. So, I'm actually gonna have you do another exercise in recursion.

[00:00:21]
So, we did up here, fibonacci. Right? Which the definition of fibonacci is n-1 + n-2. Of the Fibonacci calls. Factorials are pretty similar, that if you have 5 exclamation point which is how you write factorial. A factorial is defined by n(n- 1) factorial. So, the factorial of 5 is 5 times the factorial of 4.

[00:00:54]
Factorial, right? So what this actually ends up being is, if I have 5 factorial, let's see. 5 factorial is going to be equal to 5x4x3x2x1, right? Because 5 factorial is the 5 times 4 factorial. And he 4 factorial is this right? And then 3 factorial is this. And then 2 factorial is this.

[00:01:44]
Does that makes sense? So again, this would actually be even easier to write as an iterative solution. But I want you to write this in recursive solution that it's the factorial 5 is 5 times factorial 4. And then the factorial of 1 is just defined to be 1.

[00:02:05]
But let's pop over here to the test. Talk about what's going in here. What's your base case?
>> One.
>> Yep. Good call. It's gonna be 1 and that's just, you can return 1. [COUGH] Then on your return call, like whenever you're gonna do the recursion, how many recursive calls you're gonna have?

[00:02:29]
Just one, right? Whereas Fibonacci was the Fibonacci of 5 is the Fibonacci of 4 plus a Fibonacci 3. The factorial 5 is 5 times the factorial 4, right? So you actually have one recursive call as opposed to Fibonacci where you had two. So first thing, base case, if num is greater than 2, sorry, less than 2 rather, less than 2 Return 1.

[00:03:05]
Otherwise, we're just gonna return num times factorial of num minus 1. Or n here. Here we go. Whatever you call it, that there. So let's go back to num cuz I think that's clear. Well, maybe not. Anyway. So let's go ahead and try and run these tests. We'll click play here Play and then down here on recursion factorial, you'll see that we passed our test.

[00:03:48]
So again, this would be 100 times faster if we wrote this in terms of a loop not in terms of a recursive function, but I find this pretty descriptive of what it is right? It's number of times factorial of n-1. These still kind of have to get that like Brainspace have, this is the body of a one part of the function, right?

[00:04:13]
So this factorial function actually does more work than just the two lines inside of it right? Because this is still gonna run several essentially iterations of it several levels of recursion. Cool. Any questions about factorials or recursion or anything like that? So the question is. It can get pretty hard to conceptualize what's happening in the middle of recursion, right?

[00:04:44]
It's hard to keep all that stuff in your brain because our brains don't really think in recursive manners right we think. Think very much in a linear imperative way of thinking. So coming into this more, I would say it's slightly more declarative. This slightly more abstract way of problem solving can be quite difficult.

[00:05:05]
So what kind of tips and tricks do I have? Working through it one, just accept that it's kind of hard and that your brain is not built that way. Right? So, if it feels hard, that's because it just is hard. Okay? That's the first thing. The second thing that I'll tell you is, the first I try when I'm starting to write a recursive function.

[00:05:23]
What's the base case? That's the first question that I asked myself. And where's the recursion happening? Typically at the end, not always. I try and get those kind of pieces down first. And that kind of like, frames my brain in terms of like, okay, here's what I'm done.

[00:05:40]
And here's when I recurs that kind of provides a base level structure of what I'm expecting to get done in any level of recursion. The other thing that kind of helps me is when I'm writing this factorial function on line 15. It's kind of hard to accept that's going to return the right thing because I haven't necessarily completed writing that yet.

[00:06:07]
But what you need to do is think, if I call factorial n-1 I need to assume that what comes back from that is correct. So you need to before you have finished writing the function assume that it's going to give you back correct output. So kind of building that base level assumption into your coding helps me kind of move forward because sometimes I get hung up is like well If I haven't written factorial yet, then how is factorial gonna give me the right answer?

[00:06:37]
And you kind of have to work backwards from okay, assume everything is correct. Now we need to go forward and actually make it correct. So I don't know those are my three best shots of providing you some sort of structure to it. Sometimes it helps to get on a whiteboard and just kind of diagram out the calls, right?

[00:06:58]
Like, model it as a tree. That certainly helps as well. Certainly when I was in college, I had a huge whiteboard my room and I just would just diagram everything out. But you can do that with paper and things like that. That always helps as well. Anything that you can do to make the abstract more concrete in your brain is just gonna help.

[00:07:20]
>> Thank you.
>> Yep.
>> [INAUDIBLE]
>> Yeah, no problem. Any other questions?
>> Yeah, I got a question. So based on your explanation, I guess it's a good idea to think about recursion as a promise like, well, yeah, that'd be correct assumption.
>> Yeah, based on my explanation, it'd be correct to think of recursion as a promise almost.

[00:07:43]
I mean, promise in the sense of you'd get to treat it like something good is going to come back from it. Yeah, definitely. It's not asynchronous. All right.
>> [INAUDIBLE]
>> Yeah, it's a future value for sure. But yeah, I just wanna make sure that people aren't getting caught up that it's not asynchronous, right?

[00:08:04]
So the question is here inside of this nested array, it's const current equals array. And then it's gonna recurs, and call it again. Well, because those are different contexts. It'll be fine.