Fibonacci Functional Programming — A Walkthrough
Today, I wanted to share an exercise that I particularly enjoyed. This was inspired from an easier coding challenge that you might encounter during a technical interview. It involves the fibonacci sequence. Don’t remember precisely what that is? No sweat, you’re prompted with the logic.
Here’s the challenge: “Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.”
If you’re like me, your first thought might go something like this,
The new file window can feel daunting but you’ve got this. You’re a programmer! The question remains, what do you do next? Make sure you understand what is being asked of you. Examine the prompt and reverse engineer it. In the spirit of functional programming, let’s identify our unique tasks and create specific functions for them.
By considering the terms in the Fibonacci sequence 1 (whose values do not exceed four million), find the sum 2 of the even-valued terms. 3
- Considering the terms in the Fibonacci sequence: In order to do anything, we’ve got to work with fibonacci sequenced numbers. Note: the value not exceeding 4,000,000 isn’t something that we’re going to call but rather pass as a parameter in our fibonacci number generating function later.
- Find the sum: Pretty straight forward. We’ll want to create a function that is able to produce the sum of whatever numbers we pass it.
- Even-valued terms: With one last request, we create a function to determine whether or not the numbers we’ll be adding together are even numbers.
Let’s walk through each of these steps.
First, I create a function named fibonacci to pass my logic through that adjusts to a parameter that represents a maximum value.
Because I know that I am going to be working with specific numbers generated from my fibonacci function, I know that I will need to store and access those numbers later. For that reason, I create an empty array that I have called, fibArray.
Now, to begin the sequence that is going to make fibonacci numbers, I need three variables. I decided to call them “a”, “b”, and “c” to keep our reasoning nice and tidy. Zero doesn’t add very well onto itself so we know that we’ll need to start at one. For that reason, I declare my variable “a” equal to one. While “a” is equal to one, that means no number lies ahead of “a” to add onto itself, so “b” begins as zero. These are the only two real numbers we’re dealing with. A third variable is created to simulate the temporary value necessary to carry out our logic. Because this third variable is not a true number, but a temporary value, it is initiated as null.
Now, we need to create a condition where our sequence will run until a specified threshold is met. This calls for a while loop. Here, we end up running the logic below while “a” is less than the determined maximum. What makes all the fibonacci magic possible comes next.
Our temporary value “c” is reassigned the value of “a”, this stores our first number. “a” is then reassigned the value of “b” + itself which represents the number in the sequence we are indexed at being added to the following number. “b” is then set to the temporary value of “c”, which was the previous “a” or index value. Because “a” is the value we have added together to create the next number in our fibonacci sequence, we push that number to be stored in our array. Lastly, we return our array to be able to call this function in the future!
If you’ve made it this far, the hardest part is over! Now it’s time for our considerable smaller and simpler unique functions.
This sum function takes two parameters (total and number) and returns their being added together. That completes our second task!
Before we can add our fibonacci numbers together, we pass any given number (num) and see if its remainder is zero after dividing it by two, aka, even.
Now that we have our three distinctive functions, it’s time to call them! In order to invoke our these functions, we’ll want to place them into one last main function. This is a great habit to create clean and reusable code and a tenant of functional programming. You can see we begin by returning our fibonacci numbers, which we pass our maximum value of 4,000,000 to, that have been stored in an array. We then filter that array and pass our filter method with our isEven function. This updates the array to only return the fibonacci sequence numbers that are even. To perform our final task of summing those numbers together we pass our sum function to our reduce method. What is returned now, is our final answer.
If you’ve followed along and are dying to know wether you successfully passed this coding challenge, the correct answer is 4613732.
Thanks for stopping by and, as always, code on!