Recursion

[00:00:00]
>> So, let's talk about our old friend recursion. I imagine many of you, whether you've gotten to a CS program or not have had to deal with recursion. Just by virtue like, it shows up somewhat frequently when coding. When I say somewhat frequently, I mean it rarely shows up but it does show.

[00:00:17]
Let's go with that. So the idea with recursion is, what happens if you have a problem that's just really too big to solve, right? You're asked to sorta an array with a million numbers in it. Well, what you can do is, you can break that problem down into two problems, right?

[00:00:35]
So you can solve one for 500,000 and one for 500,000. Then you can continue splitting that down until eventually, you will end at a problem that you do know how to solve. And then you can re-stitch the solutions back together again. That's kinda the idea of recursion is like, break a big problem into two smaller problems, until eventually you have a small enough problem that you know how to solve.

[00:00:57]
The entire gist of it. So, in English, if you recursively define something in English. Like here's my example here, what is a seafarer? It's one who fares the sea. Which is the most pointless definition of the word seafarer ever, right? But notice that I'm using the word seafare in the definition of seafarer, right?

[00:01:23]
It's something that's defined in terms of itself. Which in English doesn't really serve you too much, but in computer science it actually ends up being fairly useful. So, let's look at like the dumbest most pointless version of a recursive function encoding. I have this function here that all does is it logs out.

[00:01:47]
This actually should be current, doesn't matter. In any case Notice that count To calls count To in and of itself, right? So, this function count To, is defined in terms of itself. So let's actually, I can even just copy and paste this, I'm gonna bring up my console here.

[00:02:14]
And I'm gonna say function and I'm actually gonna modify this to say current, cuz that's actually what I meant. And I say count To (10). What do you expect this to do? I wanna think I have to give it a 0 or 1, something like that. What do you expect us to do?

[00:02:39]
>> [INAUDIBLE]
>> Yep, it's going to go count 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, right? There's no for loop in here though, how did that work? Well calls count To, and then eventually, it calls count To again. And it goes through this over and over again until I realize that this case right here if, and then it stops calling count To.

[00:03:06]
So again, this is not a useful recursive function, but this is a recursive function in that, it's a function that calls itself. Now, I imagine most of you can imagine a better way of writing this, right. A simple for loop, a forereach, a map, any one of those things would have been clearer than this, abomination of code right here.

[00:03:31]
But I wanted to demonstrate to you just basically that, you can make basically anything recursive if you really try hard enough. And, if you've ever written code or in languages like racket, or scheme, or Lisp. Or basically any Lisp, sort of oriented language, this is actually the only way of doing a for loop.

[00:03:54]
Which is with recursion. Definitely not a scheme class. Though, I'll just toss out a recommendation. Not that I'm gonna teach you how to write scheme, but it made me a better programmer to go and learn a little bit of how to write scheme. So, and it's a fun weekend project.

[00:04:13]
It's because it's a pretty simple language
>> Isn't map. You had a map function usually recursive by definition.
>> The map function is recursive by definition. I don't think so, am I missing something?
>> I mean I've been dabbling with functional languages a lot recently, so I might be stuck in that space but

[00:04:40]
>> I mean it's more iterative, right? Cuz with a map function, you provided mapping which is then call on every single item the array. and function isn't calling itself, right? So that map is undefined in terms of itself. Which is what a recursive function is.
>> I think since in functional languages, you don't have iteration.

[00:05:04]
I mean, maybe that's the only way to make a map function in a functional language.
>> Yeah, I guess if you're gonna implement map in something like Lua. Or not Lua, but Lisp, inherently because those languages model loops as recursion, then I guess it would have to be.

[00:05:25]
So the question is, there's a couple of questions there. That's unpack it just a little bit. The first thing is, if I put in max as infinity. Yeah cuz it's never gonna stop counting, right. So, with normal recursion, this says this actually would just get tail called optimize it probably would, okay?

[00:05:50]
So you'd actually get an infinite loop and not a stack overflow, right? Because if it's tail call optimized, you'd be modeled as a loop and not a recursive function. So you'd actually end up in an infinite loop, which is maybe mildly better than a stack overflow. But, let's actually define both of those things.

[00:06:08]
Infinite iteration, is when you have a loop that never ends, right? So, if I do a while loop like while true, right, that's an infinite loop. Something like this, while true, something like that, this would be an infinite loop cuz this would never end. Whereas if I count to here a max of positive infinity.

[00:06:32]
That would also never finish, right? And that would be a stack overflow. Because eventually JavaScript engine just kinda gives up, like hey, you've taken all of my stack memory. I'm just gonna go puke in the corner basically. Now, let's talk about tail call optimization for just a second.

[00:06:53]
One, it's still kind of a murky proposition in JavaScript, that it is part of ES 5 or ES 2015. But I don't think every engine implements tail call optimization yet. So in other words, don't rely on tail call optimization. And what tail call optimization is, if you make the last line of your recursive function, a return of your recursive call.

[00:07:21]
Then technically a programming language can automatically turn that into a loop. Which is inherently faster and more memory efficient than a recursive call. So, I don't know if this does because it lacks return. That, if it would happen, I think it would. But it also depends on the engine, right?

[00:07:45]
I don't know if spider monkey does it, I don't know if he does it. Because there was always controversy of how to implement that. Anyway, that whole last part about tail call optimization, not something you really need to care about for the sake of this course. But it's something interesting, you can go read up on yourself on how to do it and what it is.

[00:08:04]
>> What is the purpose of the list parameter, looks unused in this case?
>> It is, yeah. I was gonna have to populate that array there with the counted numbers and I did not take it out. So yeah, the list thing here is, pointless for the moment. When is recursion useful?

[00:08:25]
Well, when you find yourself in the definition of your problem. Modeling it in terms of smaller versions of the same problem, that's a good indication that your problem could be solved recursively. So one of the classic examples that people like to talk about with recursion, is something called the Fibonacci sequence.

[00:08:47]
Now, again, I don't wanna veer too mathy here. But the idea of the Fibonacci sequences is, the Fibonacci(3) is the Fibonacci(2) + the Fibonacci(1). All right. And the definition of the Fibonacci (100) is, Fibonacci + 99 + the Fibonacci(98) + the Fibonacci(97)+ the Fibonacci(98). So on and so forth.

[00:09:12]
That you can generalize as the Fibonacci(n), is the Fibonacci(n-1) + Fibonacci(n-2), right. And what is the Fibonacci(n-1)? Well, that's the Fibonacci(n-2) + Fibonacci(n-3), right? And you can kind of expand that out, to eventually you arrive at what the Fibonacci(2) is defined to be 1 and the Fibonacci(1) is defined to be 1 and the Fibonacci(0) is defined to be 0.

[00:09:41]
Those are like kind of like the givens. So, as you might imagine the Fibonacci(3)= Fibonacci(2)+ Fibonacci(1). So the Fibonacci(3) = 2. The Fibonacci(4) would be the Fibonacci(3), which we just found out as 2+ Fibonacci(2)=1. What I just say, 3, 4. Anyway, it's kinda hard to keep all this in your head, right [LAUGH].

[00:10:18]
So, there are negative Fibonacci numbers, we're ignoring them. Please for the sake of this course, we're just talking about positive Fibonacci numbers. So, the first thing is, when you're talking about recursion is, always, always, always just define your base case first. The base case is when your your recursion stops, right?

[00:10:43]
Cuz if you don't ever stop your recursion, then you get stack overflows. So, for example up here in our count To, this if statement right here, is your base case. So, if current is greater than max, then return, right. That's when we've decided like, okay, we've satisfied all the conditions, we're now done, we're not recursing anymore.

[00:11:07]
So, this is our base case that if n=2, look at this one, equal to 2 or equal to 1, then return 1, otherwise return 0. So we have the n=2 or the n=1. Don't click on it. So the base case here is that we return 1 and if we somehow end up on 0, we shouldn't end up on 0.

[00:11:28]
But if we did, then you return 0. Okay? And then we just define the Fibonacci in terms of what our definition was. So the Fibonacci(5) is the return the Fibonacci(5-1), which is 4, and (5-2), which is 3, right. Which then calls this, until eventually those arrive to their base cases.

[00:11:48]
And then, those return until eventually we kind of add all those numbers up and we end up with the correct answer.
>> So, Fibonacci(2), right. That makes sense. So on and so forth. So you can see here, 2+3= 5, 3+ 5= 8, 5+ 8= 13, 8+13=21. Okay? Let's break this down into what the calls actually break down into, you'll often see recursion modeled as like a tree.

[00:12:35]
Because essentially that's what it's kind of breaking itself down into. So, here if I call Fibonacci(5). This is gonna call this and it's gonna call Fibonacci(4), which is this call. And Fibonacci(3), which is gonna be this call. And that's gonna break down into these various different calls. Fibonacci(4) is gonna call 3 and it's gonna call Fibonacci(2) which is 1, right?

[00:12:59]
And then Fibonacci(3) will break down into 2 and 1, these are both 1. So this is gonna be 1+1, which is gonna return 2+1, which is gonna be 3. So, Fibonacci(4)=3 and then Fibonacci(3) over here, is gonna be 1+1, which is 2. And then these two are gonna add together, which is 3+2, which is gonna be 5.

[00:13:20]
Now, at the end of the day, what did I end up doing? I ended up adding 1 to itself a whole lot, right? This is a whole lot of adding 1 together. So, if I end up doing something like, Fibonacci(15), which is a fairly large number. 610, how many times did I add 1 to itself?

[00:13:42]
610 times, right. 16, right 987. If start getting into really big numbers of Fibonacci, it gets kinda ugly. Notice how long that took, it's not instant. I did 35 there and it took a good worth. 2 seconds of my very good MacBook to compute that, right. So, as you can see here, this is actually super inefficient.

[00:14:18]
But the code here is really quite nice, right? In the sense of like, it's kinda elegant in the sense of like, it's fairly easy to read that the Fibonacci(5) is gonna be the Fibonacci(4) + Fibonacci(3). So, you'll find this is frequently the case with recursive calls is. It might not be the most efficient way of doing things, but you can often end up with fairly elegant looking code.

[00:14:46]
Now, what's the shame about this? We have Fibonacci(3), how many times do we call Fibonacci(3), instead of the Fibonacci(5)? At least twice, right? Well, exactly twice. But imagine when we call Fibonacci (15), how many times do you think we call Fibonacci (3)? A lot. Does the Fibonacci(3) change over time?

[00:15:13]
No, the Fibonacci(3) is always defined to be 2. So, this would actually be pretty effective if we did something called memorialization. Where we could actually say, hey, once you've completed the Fibonacci(4) to be, whatever it is 3, don't compute that anymore, right? It's always gonna be that, so if you ever see that again, just return the same answer that I got last time.

[00:15:36]
So, not necessary the point of this course but I just wanted to call out that this would be a perfect case for a memorization. You can rewrite Fibonacci as in a for loop instead of as a recursion, right. And you end up with code that looks like this, which is just numbers adding itself together, right?

[00:16:05]
It's a little less clear, I might argue that this code might be easier to read, right? But this is, 500 times faster and probably even more than 500 times. So if I call here, let's see, Fibonacci(16) or Fibonacci(35). Notice how much faster this is going, let's do 100.

[00:16:33]
Notice that this is just kicking out huge numbers really quickly. If you did Fibonacci(100), with the previous way that we had defined the Fibonacci sequence, it probably would have crashed my browser. So, it's another one of those things where in this case, the iterative approach is so much better.

[00:16:50]
It's probably almost always going to be the correct answer. And this isn't terrible code. I might read some comments in there, but in general this is gonna be better. But, yeah this is to say that, frequently recursive problems can be rewritten as iterative solutions but not always.