Recursion

[00:00:00]
>> Now we have hopefully a pretty good intuition of what a pure function is and how to recognize one, or how to recognize a function that's not pure and what some of those red flags are to look for. So now we wanna talk about another technique in a functional programmers toolbox, which is recursion.

[00:00:19]
And how it helps us avoid a more imperative style of looping through iteration. So, okay, iteration and recursion, we could think of as kind of two mini paradigms that sort of go hand in hand with imperative programming for iteration and functional programming for recursion. So, iteration and recursion are two ways of thinking about how to get the computer to do the same operation, lots of different times.

[00:00:57]
And in the iteration mini paradigm or sub paradigm, these don't usually get called paradigms, but I think that they are coz they're kind of like ways of looking at the world. In the iteration mini paradigm, we think about that repetition in terms of loops with for or while usually.

[00:01:17]
And that loop as we go, we're probably going to be changing some variable like a counter like I or when you do like a for let, element of array. We're using this element variable, and we're gonna be changing that as we go. So that means we have some value changing over time, which means that it's stateful.

[00:01:41]
And so when you have a really complex iterative loop, sometimes it can be hard to think about, okay, what's the value of I right now? Where am I in my loop? Which loop am I on? What are the values? And so again, we have that general problem of like it's hard to think about state.

[00:01:58]
It's hard to think about values changing over time. And so in the recursive mini paradigm, we're gonna think about things in a more pure functional way. We're in recursion instead of using for or while and these stateful loops, we're going to use self reference. We're gonna have a function call itself firma within itself.

[00:02:24]
So that we have kind of this functional inception of self reference. And that is how we're gonna execute the same operation or the same chunk of code multiple times. Now what that means is that each call of the function again, all I care about is the input coming in, and all I care about is the output going out.

[00:02:48]
So the idea is that we're no longer changing those values over time. We're getting rid of that state. We've got a more stateless way of repeating the code that we need to repeat. So this is kind of the big picture of the difference between the iteration mode of getting code to execute multiple times and recursion.

[00:03:12]
So as we said iteration doesn't really go that nicely with functional programming like we saw in that example from our pure functions exercise where we had an iterative loop that was changing a table within our function. So instead, when we're writing functional code we're gonna move away from iteration and towards a more recursive mindset.

[00:03:35]
So let's take a look at some iterative code right here. I've got a sum function, it takes in some array of numbers. And then it's using a variable called total with a for loop, so that we're changing the value of total each time we run through this for loop, adding on numbers from the array.

[00:03:57]
And so if I run this code on array of numbers, I'm gonna get out some certain output. And now again, this might be a deterministic function that always gives me the sum if I always give it the same array of numbers. But, again, that looping inside, that changing of that value of total, the fact that total can have different values over time through this code is not super functional.

[00:04:24]
So let's make this even more functional by making it recursive. So now, we have a recursive sum function. It's recursive because it makes a call to itself. So within the body of sum, I'm actually calling sum as well. That is a definition of a recursive function. Now in practice when you're writing recursive functions, you have to make sure you have two parts to the function.

[00:04:57]
On the one hand, I have my recursive case. So, in this recursive case, I'm gonna be taking off the first thing in my numbers array and then, adding it to whatever the result is of this same sum operation on the rest of the array. So I'm using slice here in JavaScript to take the rest of the numbers in the array after that first one.

[00:05:23]
And that is my recursion. However, if I don't stop that recursion at some point am just gonna keep calling myself down and down and down and down and down into an infinite loop and it's gonna be like when Leonardo DiCaprio in inception gets lost in the dream world.

[00:05:42]
If you haven't seen the movie, and you wanna take a study break, it's pretty fun. In any case, we don't want to get lost in an infinite series of loops. So we also need what's called a base case. We need a non recursive case in our function, which we can use if to split that out where in the case that I only have one number in my array, I'm gonna stop recursion, I'm not gonna do any recursive call, and I'm just gonna return that number because the sum of a single number is that number.

[00:06:12]
So when we're thinking about writing recursive functions, this is what I want everybody to remember is make sure that you're writing a base case and you might have more than one cases in which you're not doing that recursion. And then your recursive case, don't forget that base case or else you're gonna run into headaches.

[00:06:30]
And we'll take a look at later what kind of headaches [LAUGH] those will be. Questions? Do we not run into problems when we have really, really large arrays with lots and lots of recursive calls that are necessary? Yes, we do. We totally do. And in a moment we're gonna talk about and we're gonna see [LAUGH] maybe what that problem is gonna look like.

[00:06:54]
And how we can solve it, is a subject that's something we're gonna talk super briefly about. But I'm also gonna send you some resources where you can find out more about how you can get around that problem in functional programming. But great point, yes, there is an issue here and if we're not quite sure what that issue might be, the next exercise we're gonna think about it a little harder.

[00:07:17]
>> I have a question about, I guess it's just a [INAUDIBLE] functional calls. Is it possible to, with your output of data global value that maybe you don't reference but it's like we're building a database or you're building some information from a recursive call. If during the call you're updating a global variable, global value or database does that make it that is not pure function?

[00:07:52]
>> If during your recursive functions execution and during the recursive calls, you are updating something and outside world like a database, does that make it an impure function? Is the question? What does everybody think? I see some thumbs up.
>> Yes.
>> I hear yes. Yes. Yes, exactly.

[00:08:14]
So again, none of the techniques that we're gonna look at that are that are kind of handy ways of thinking about the practice the day to day of doing functional programming. None of these will replace the core concept which is that we need purity, we need determinism, we need to make sure that we're avoiding side effects.

[00:08:32]
So this is all going to be kind of a yes and yes, we need pure functions and we can use recursion to help us avoid state within those functions in iterative loops. But we still don't want to introduce non determinism or introduce side effects into our code, even if it's recursive.

[00:08:55]
So it is totally possible, and in the world of JavaScript happens a lot that you have a recursive function that is not pure. So recursion is not a condition of purity, it is more a consequence of when you're in a world where you have no possibility of changing values over time where you have no such concept as state values changing over time.

[00:09:18]
That recursion ends up being useful for that pure functional world. If that makes sense. Great. Other questions? Are recursive functions more expensive than iterative functions? That is a great question and gets also at this question of are you gonna run into performance or other problems if you have really, really big data that you're operating on?

[00:09:42]
And that is a whole really interesting question that I definitely wanna talk about with all of us. But I think it'll be great if we can take a look at these exercises. And part of the exercise is gonna be actually thinking about that question. What are the performance implications for iteration versus for recursion?