Iteration vs Recursion

[00:00:00]
>> Anjana Vakil: The next topic we're gonna need in our functional programming toolkit in addition to purity is recursion. This is a functional programmer's best friend. Can anybody tell me what a recursive function is, have you encountered this term before, a recursive function? Yeah, okay, we've heard heard it.
>> Speaker 2: A function that calls itself.

[00:00:22]
>> Anjana Vakil: It is a function that calls itself as part of what it does. It could also be, for example, a function that indirectly calls itself by calling another function that calls it, let's say. But in today's [LAUGH] functional land, we're going to talk about recursion as a recursive function is a function that uses itself as part of its own computation.

[00:00:53]
>> Anjana Vakil: And in functional programming, we're gonna use recursion whenever we need to do something multiple times. Instead of what we're typically used to in imperative programming loops, so for loops, while loops, all those kind of loops. Those are things that don't even exist in some purely functional languages, and that even though we were using them in some of our pure functions earlier, because it was all right since we were wrapping them up in the deterministic pure function.

[00:01:20]
We're gonna try to avoid from now on to get ourselves into the functional mindset. And in functional programming, we don't change the value of A in each loop of a four, instead, what we'll do is recursively call the function again with a new value of A. So we're gonna get a lot of practice with this today.

[00:01:46]
And it is one of the more mind bending things in functional [LAUGH] programming, I think, recursion, it's just, sometimes it gets. So let's take a moment to really think about it. Okay, we said before that imperative code and functional code are kinda in contrast to one another. So, inside of the imperative programming paradigm where we're saying do this, do that, do this other thing.

[00:02:15]
The way that we execute code multiple times is with Iteration, right? Some kind of loop where we say, on each run through this loop, change the value of this let a of array, or what have you. So that the first time that loop executes a is gonna be one thing, and the second time it's going it's gonna be another thing, and so on and so forth.

[00:02:41]
That means we have a value a, in this case, inside of the loop, that changes over time, and that is what we call state in a program. When we have a value that could change over time or does change over time, we are dealing with a stateful program.

[00:02:59]
The values at that particular point in time matter to the execution of this program. And that is a no-no for a functional programmer. Because if you have state, if you have values changing over time, that means you might not accurately predict what the state is at any given point of your function execution.

[00:03:23]
And that might lead to surprising effects, right? If anyone has ever had the situation where you thought that this method from this library was gonna return one thing, but then surprise, they changed the API and now it returns a totally different thing. And so now the value of that thing is, it has changed from a month ago, when your tests all passed, to today, when they don't, and your boss is mad.

[00:03:50]
That is why we wan to avoid state, it gives us headaches. So functional programs are stateless as much as possible, and how do we do something multiple times if I can't change the value of a variable in a for loop? That's what our friend recursion is here to help us do.

[00:04:09]
So, in recursion, we're still taking a computation, and executing it multiple times with different values, but instead of doing it in a stateful way with assignment to variables that the value of which changes, we're doing it in a functional way. And instead of imperatively saying on each run of this function, do this and do that and do this other thing, we are giving this self reference.

[00:04:36]
The recursive function is referencing itself to execute that same function code another time, but with different inputs. So this is the imperative, this is sort of like the imperative functional divide in one small domain area of how do we execute code multiple times? How do we do stuff over and over again?

[00:04:58]
Okay, so as we said, we wanna avoid iteration, we wanna focus on recursion. All right, let's take a look at a typical, this is a little bit old school JavaScript, but this really makes clear how stateful a for loop is in JavaScript. So here we have a function sum, where we start out with a total of 0, and then we enter a for loop.

[00:05:22]
And this is using the traditional syntax, [LAUGH] where we define the initial value of a variable. We define a stopping condition where when the state of the program, when the state of this variable, the value of this variable has reached a particular condition we wanna stop. So in this case, as long as i is less than the length of the numbers array, keep going, and then on each run, increment the value of i.

[00:05:56]
>> Anjana Vakil: So here, for each index in the array, we're pulling out the number at that index, and we're updating the total. Now this plus plus here, this is really illustrating, and it's a little bit clearer to see than in the newer for of syntax, this is really illustrating how do this, then that, how imperative a for loop is.

[00:06:20]
We're telling JavaScript exactly what to do, saying, first run this line of code with i equals 0, then increment i, then check if the condition is met. Are we still satisfied? Then run this block of code again with the incremented value. So, this is just to illustrate, there's a lot of baked in imperativeness in these things that we use every day, that we probably aren't even thinking about, right?

[00:06:51]
Just think for let a of array whatever, but really what's happening under the hood is a whole bunch of imperative values changing. And when we mess up in thinking about, okay, at this run of the for loop, I think I have the right values, blah, blah, blah, it becomes very easy to introduce unexpected bugs in our code.

[00:07:15]
>> Anjana Vakil: Let's look at the alternative here, so this is a recursive sum function. Same API, we take in an array numbers.
>> Anjana Vakil: And then,
>> Anjana Vakil: We make some decisions. [LAUGH] Every recursive function needs two things unless you want to crash your computer. [LAUGH] One is a recursive case because if it didn't have a time where it was calling itself, we wouldn't call it a recursive function.

[00:07:48]
But especially important, don't forget, every recursive function needs what we call a base case, meaning a non-recursive case. Because if we only had the recursive case, we would keep recursing over and over, and over, and over, and over, and over, and over again until?
>> Speaker 3: You end up in the void in inception.

[00:08:14]
>> Speaker 4: Stack overflow.
>> Anjana Vakil: Yes, and we get what's called a stack overflow, In JavaScript, it even says too much recursion. Sorry, in Firefox's implementation, the error is too much recursion, bad functional programmer. [LAUGH] So that's why we need the base case. It's sort of the bottom to our dream within a dream within a dream, the spinning top, if you will, or the fallen over I don't know, I haven't seen that movie a long time, anyway.

[00:08:41]
So in this case, we need a base case in which we are not gonna call ourself the sum function again. And in this case, it's, okay, if we just have one number, hooray, we're done. If I give you an array with one number and I ask you for the sum, you're just gonna give me back the value of the one thing in the array, right?

[00:09:03]
Everything else, longer arrays, is going to fall into the recursive case. So we're gonna pull out the first element and then we're gonna recursively do this operation again on a smaller array over and over and over again until we get a single number. And then we're gonna pop out of the recursive call and add it to the previous number and pop out, and add that to the previous number and pop out, and add that to the previous number until we get our sum.

[00:09:32]
All right, so if you're used to writing recursive functions, great, fabulous, you're gonna feel awesome. If you're not, your brain might hurt a little bit when you start thinking about how to implement stuff that you're used to doing with imperative iteration, with functional recursion instead. And that's why we're here to practice together, yay.