Functional JavaScript First Steps

Iteration vs Recursion Solution

Anjana Vakil

Anjana Vakil

Software Engineer & Educator
Functional JavaScript First Steps

Check out a free preview of the full Functional JavaScript First Steps course

The "Iteration vs Recursion Solution" Lesson is part of the full, Functional JavaScript First Steps course featured in this preview video. Here's what you'd learn in this lesson:

Anjana demonstrates the solution to the Iteration vs Recursion exercise.

Preview
Close

Transcript from the "Iteration vs Recursion Solution" Lesson

[00:00:00]
>> So let's take a look at these exercises. Did everybody have a chance to get to the bottom of the notebook as it were? I'm seeing some nods. Okay, great. And obviously for folks following along at home, hope you could spend whatever time you needed. So all right?

[00:00:16]
Let's talk about readability. Now, this is a very subjective question. Everyone is gonna have a different answer for it. But between these two versions, the iterative factorial and the recursive factorial, which one do people find easier to read and understand what it's doing just by looking at the code?

[00:00:42]
Who thinks the iterative factorial is easier to read? I don't see any hands being raised. I don't see anybody nodding. I see maybe one hand being raised, okay? Couple people, okay? What about the recursive version? Three, four, okay? A few more people, find this recursive version a little bit easier to read.

[00:01:06]
Would anybody like to share? And again, this is a totally subjective question because programming is pretty subjective in the sense that style and organization of code. And how easy it is to work with a particular style or program paradigm is something that's gonna vary based on the programmer based on their background.

[00:01:25]
Based on the languages that they've worked in before based on the types of programs that they've read before. So who would like to share their perspective on either of these functions and what they thought about the difference in readability. I think that the iterative one is very clear in the sense that it does step by step, but the recursive fracture is more like elegant.

[00:01:55]
I don't know, it seems to me.
>> Okay, so I heard that the iterative factorial implementation seems very clear, because we can read step by step what it's doing, because again, it's imperative. So it's all these commands, these kind of steps, but that the recursive factorial seems a bit more elegant.

[00:02:13]
That's something, that's a word that you often hear people use when they are describing recursion or when they are describing functional code. We'd love to hear more about what makes this function look elegant to us. What does elegant mean to us? Again, it's a subjective question. Just maybe you want to expand a little bit.

[00:02:30]
>> I think that the fate that the fact that.
>> It doesn't need to hold on state, it doesn't need state. It doesn't need to keep state. We don't have that product value changing over time.
>> Because we don't have a state, we don't have to hold on keeping that state on your mind.

[00:02:51]
If you are debugging something that doesn't have a stated way, it's way more easier to reason about. But if you don't understand recursive equations, then is very hard to understand. For someone that is starting on programming or if you have a lot of juniors in your company, it may get to the point that it starts to become hard to maintain this recursive code.

[00:03:26]
>> Okay, so just to recap the absence of state in the recursive factorial function and feels nice or seems like a positive addition, but for somebody who doesn't have a lot of experience with working with recursive functions. Or perhaps is really new to programming and especially, and I think a lot of introductory programming courses really take an imperative approach.

[00:03:53]
So if someone is less experienced with thinking about solving problems in a recursive way, the recursive implementation might be a little harder to wrap your head around, a little harder to understand. I totally agree, and I think again, this is subjective because for example, if we have been working with an imperative programming language like C, or C++.

[00:04:16]
Or one of these languages that forces us to do everything in kind of imperative commands, we might be so used to thinking in that mode. That might be like really where our mindset our paradigm, our worldview, is that mentally and that might make it easier to take in that imperative code.

[00:04:36]
But again, that's why it's so important to get a lot of practice and spend a lot of time, kind of wrapping your head around the functional approach. Because once you've wrapped your head around the concepts of recursion, the concepts of solving problems by breaking them down recursively, then that will no longer feel so strange or so weird.

[00:05:01]
And then, you'll be able to decide for yourself whether you want to take a recursive approach because it let's say allows you to write a much quicker, shorter function where there's less than code to check in. Less code to worry about or whether you prefer the imperative style.

[00:05:20]
Because perhaps, you're working on a team with lots of people who are more comfortable with imperative code and that is what's best for the maintainability of the project and the team. So again, there's no hard and fast answers here. It's a question of what works best for you what works best for your team and what works best for the journey that you're trying to take.

[00:05:42]
Are you trying to bend your mind and solve problems a different way than you usually do? Or are you trying to stick with the same mental models that you've been using? So this is what I wanted you all to think about with, with this exercise. Again is like really, it's a very individual thing here, okay?

[00:06:01]
Now, how about writing these functions? How did this go? Were people able to implement both of these versions, the iterative and recursive Fibonacci functions?
>> Yes.
>> I see some some folks were great. And I see someone made a comment about the recursive implementations being a little bit closer to how we were taught in math class.

[00:06:30]
And yes, I agree, I think for certain of these problems, especially these operations like the factorial and the Fibonacci number calculation. When you learn in math class, when a human is explaining to another human, here's how you do it, you take the factorial of this number. And that gives you the number of times the factorial of the next smaller number that is the way you might explain it to another human.

[00:06:57]
Because when we think about things like that, that is us thinking in a kind of recursive way. So, that also has a big impact on which of these will be easier to read and write, all right? So there are plenty of ways stylistically and syntactically in JavaScript to implement these two versions.

[00:07:20]
I have one option here in another in a kind of a solved version of this notebook, which you can see by going at the top of the notebook. It shows there's a fork iteration versus recursion. So if you open that up, and please let me know if anybody is having trouble again with finding anything here on observable.

[00:07:44]
You'll find a version of the notebook with some of this code filled out. And so again, once you've got that implementation done with the correct output you should see these little tatas. Now, I'm trusting you all that you're forcing yourself to use an imperative style, an iterative style with a loop, or forcing yourself to use recursion wiki, wiki.

[00:08:08]
We're not programmatically determining that to do these little test cells down here. But here's one way you could have done the Fibonacci Is a sort of with a couple of just caveats of this is by definition, that's the answer. Zero gives zero and one gives one. And then, you could use a for loop to kind of keep changing the values of counters called previous and current that allow you to keep tracking where you are at in the process.

[00:08:38]
So sort of to remember how far you've come in the sequence, and then finally return the most current value. Folks might have different solutions for this that are also iterative and also perfectly valid. This is just one way you could do it. So moving on to the recursive version, this is where there's probably fewer ways that you would be able to solve this in a recursive way.

[00:09:10]
But again, there's some flexibility here. Everybody might have a slightly different version. But here is one way. So again, we start out with those kinds of default, just by definition these are the first two values of the Fibonacci sequence. And by the way, I hope everyone was able to find that link in the exercise to read up about the Fibonacci sequence and what Fibonacci numbers are in case you haven't encountered them before.

[00:09:33]
Check out the Wikipedia article. It's pretty good. [COUGH] And again, we have some test cases, so we know when it's working. So in our recursive version, we start out the same way as we did in the iterative one with these two kind of non-recursive return statements. Does anybody remember which part of the recursive function this is called?

[00:09:57]
>> Base case.
>> Base case, thank you, yes. So in this case, I have two base cases, or I have a two part base case. And again, we need that base case so that we don't end up getting into an infinite recursive loop. And then, I have my recursive case where I am applying this recursive Fibonacci function actually twice.

[00:10:19]
I'm getting the Fibonacci number 2 before, and the Fibonacci number 1 before, so that I can add those together and get the current Fibonacci number. And this is probably gonna look quite similar to how again on the Wikipedia article it describes what Fibonacci sequences are, how it's calculated, or maybe what you would have learned in math class.

[00:10:42]
And you will see a lot of overlap between those kind of problems in math that are solved by these kind of recursive operations and functional programming examples like this one. So which one was easier to write? Same question and again, again, super subjective, but who found the imperative iterative version easier to write?

[00:11:08]
I see a hand, okay? What about the recursive version? I see two hands, three hands, okay? So again, there's no right answer. It's a function of a lot of different things, function. It's a function of how much time you've spent writing recursive implementations. Perhaps, whether or not you looked at the Wikipedia article which would maybe nudge you in a functional recursive way.

[00:11:41]
Or whether maybe you are just starting out in JavaScript after decades in an imperative language like C or something like that. All those things will affect which one is easier to read and write. So again, when people say, recursive programming or functional programming is absolutely the best and absolutely the most elegant and the most wonderful to write, to read.

[00:12:05]
That may be true for them, but it might not be true for everyone. So keep that in mind when listening to folks about how much they love functional programming and recursion, even me.

Learn Straight from the Experts Who Shape the Modern Web

  • In-depth Courses
  • Industry Leading Experts
  • Learning Paths
  • Live Interactive Workshops
Get Unlimited Access Now