Recursion with Fibonacci numbers

The problem

I got this puzzle from the great math website projecteuler.net: Find the sum of the even Fibonacci numbers that are less than 4000000.

Fear not if you don’t know anything of Fibonacci or his numbers, the next section will explain what you need to know to succeed in this challenge.

Background

Fibonacci was an Italian mathematician, who lived in the 13th century. He was very talented and created a famous number sequence we will be working with below. Fibonacci numbers make up a sequence. A sequence is nothing else but a series of numbers coming after each other by some rule. The members of the sequence are called terms. The rule for the Fibonacci sequence is that each term equals the sum of the previous two terms.

Obviously, the sequence needs to start somewhere; otherwise we wouldn’t have anything to add. It’s agreed that the first two terms are equal to 1. So the third member of the sequence is going to be 1 + 1 = 2, the 4th term is 1 (2nd term) + 2 (3rd term) = 3, the 5th term equals 2 (3rd term) + 3 (4th term) = 5 and so on. Let’s list the first few terms then: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Breaking down the problem

One way of solving the problem is to get a pen and a paper, write down the terms of the sequence until 4000000, and then add them together. You don’t want to do that, if so, good luck with it.

Instead, let’s create an algorithm for the problem. As always, it’s a good idea to sit back and think about the problem first, then break it down into smaller, more manageable parts.

Repeating the same process

First, notice that we always create the next term by adding the last two terms. It’s a repeating process. So if we had something (a function) that calculates the sum of two numbers and then we could somehow keep repeating and applying it on the next two numbers, we would get the terms of the sequence one by one. The process of repeatedly invoking a function is called recursion.

Upper limit

We also need a threshold, in our case it’s 4000000. At this stage it could be an argument to our function to make it configurable and reusable.

Find even members

Once we have found the Fibonacci numbers (or even during the process?), we need to find the evens, so some kind of filtering will be necessary.

Add them up

This is probably the easiest part. The even numbers should be marked and be added up.

Edge cases

It’s always a good idea to think about the extremes. Edge cases can often act as source of bugs in applications. Still, it’s not always easy to find all possibilities for an error, but one should strive to cover as many as possible. Life (and users particularly) are very creative and bugs will occur however good you do (goodbye, perfectionism!). What can be some edge cases for this problem? The terms of the sequence must be all positive integers. Or the user enters a string instead of a number. We need to handle these when we write the code.

Assigning each part to JS

Creating Fibonacci sequence is a separate task, sort of a component, so I would create a function just for this part. Because the given definition of the Fibonacci sequence is recursive, I will invoke the function in itself.

I will also handle some of the edge cases here.

The upper limit will be the argument of the function, so it’s going to be reusable. If I change my mind and want to solve the same problem for Fibonacci terms less than 1000 instead of 4000000, I can easily do so.

I also need to know when I reach the upper limit; iteration over positive integers will be of use here.

Finally, I need to find the even Fibonacci numbers, using the remainder (%) operator and have to add them together.

Solving the problem

Let’s do it!

Creating the Fibonacci function

First, we create the function that generates the Fibonacci numbers and surprisingly call it fibonacci:

const fibonacci = (n) => {
  if (n === 1) return 1;
  if (n === 2) return 2;

  return fibonacci(n - 1) + fibonacci(n - 2);
};

This function will return the nth Fibonacci number.

Let’s have a closer look at it! Because the definition of the sequence is to add the previous two terms to get the next one, we need to define the first two terms. They must be hardcoded so that we can calculate the Fibonacci numbers from the third term onwards. (Note: The original problem defines 2 as the second term, so I’ll stick with this. Many resources define both the first and the second term as being equal to 1. This small difference won’t influence either the end result or the way the terms are calculated.)

The return statement is the recursion part. We add the last and the second last terms here.

If you log fibonacci(5), you’ll get 8, which is the 5th Fibonacci term. Indeed: 1, 2, 3, 5 and 8.

The function doesn’t seem to do any magic, so how come that it still works? When the function invoked with the parameter of 5, the two conditions will not trigger any actions. So we’ll get fibonacci(4) + fibonacci(3) invoked, since this is what we return when we call the function.

When fibonacci(3) is invoked, again, fibonacci(2) + fibonacci(1) gets returned and invoked, and the conditions set in the if statements will trigger the actions here. fibonacci(2) equals 2 and fibonacci(1) equals 1, so add them up to get 3.

The fiboancci(4) part of the addition returns fibonacci(3) + fibonacci(2), and we have seen this before: fibonacci(3) is equal to 3, fibonacci(2) evaluates to 2. If we add them up, we’ll get 3 + 3 + 2 = 8.

So the magic is that when we call a function recursively, it will “breed” more of the same functions, they get invoked again and they will “breed” even more functions and so on. Eventually these functions will get down to the default 1 and 2 values. If we add these many 1s and 2s, we’ll get our Fibonacci term.

This wasn’t easy!

Adding up the Fibonacci numbers

We create a function called addEvenFibNumbers for this part. The function will accept one argument, and this will be the threshold (the number the user enters, which is 4000000 in the original example.)

This is a good place to handle some edge cases that can lead to errors:

const addEvenFibNumbers = (threshold) => {
  const limit = Number(threshold);
  if (!limit || !Number.isInteger(limit) || limit < 0) {
    return 'Please enter a positive integer!';
  }
};

First, the parameter is converted to a number, using the Number object and is stored in a variable called limit.

We then check for the edge cases. If the entered value (e.g. the string “hello”) cannot be converted to a number, we’ll get Nan, which is a falsy value, so the !limit condition will be true, and our gentle error message is returned. If it can be converted to a number but the number is not an integer, the message will appear again. Similarly, we don’t want to work with negative numbers (we can’t in this context anyway), so let the user know what they should do next time.

Now that we only have positive integers, we can start iterating over the numbers from 1 to the limit and check for even Fibonacci numbers. This is the function itself:

const addEvenFibNumbers = (threshold) => {
  const limit = Number(threshold);
  if (!limit || !Number.isInteger(limit) || limit < 0) {
    return 'Please enter a positive integer!';
  }

  let sum = 0;
  let n = 1;
  while (fibonacci(n) < limit) {
    if (fibonacci(n) % 2 === 0) sum += fibonacci(n);
    n++;
  }
  return sum;
};

We use a while loop here. while loops need to be used with care, as it’s easy to run into infinite loops. Luckily, we have an upper limit (4000000 in this example), so the loop will finish once fibonacci(n) reaches this limit (i.e. when the actual Fibonacci term exceeds 4000000).

We need to filter out the even Fibonacci numbers using the % remainder operator, and when we find one, we simply add that number to the sum, which initially equals 0. We return the sum in the end.

Now, if we log addEvenFibNumbers(4e6) (or addEvenFibNumbers(4000000)), the result is displayed (4613732).

Alternative way of defining Fibonacci function

As you might have noticed, it took some time for your computer to calculate the final answer. It might have even been a noticeable delay between pressing Enter and getting the result. (If you haven’t noticed any delay, try entering a bigger number in addEvenFibNumbers).

The reason for this is your computer needs to take a lot of operations to compute the result.

It means that we are probably better off finding another way of calculating Fibonacci terms, a way that requires less resource and effort from the computer.

Let’s think about it for a second. When we created fibonacci, we “translated” the definition of the sequence into JavaScript.

What if we tried to translate the behavior of the terms?

What do I mean by behavior? Have a look at the first few terms: 1, 2, 3, 5, 8, 13, 21, … If we take for example the 5th term as current term (let’s call this step 1), which is, the last term is 5 and the second last term. When we move on to the 6th term (13) as current (step 2), the last term becomes 8 (the current of step 1) and the second last term becomes 5 (the last term of step 1). So we always “slide” these three elements (second last, last and current) by one to the right as we calculate the terms of the sequence.

Can we use this principle to determine Fibonacci numbers from the point of the current term? Absolutely! Here’s how:

const fibonacciAlternative = (n) => {
  let secondLastTerm = 1;
  let lastTerm = 2;

  if (n === 1) return secondLastTerm;
  if (n === 2) return lastTerm;

  for (let i = 3; i <= n; i++) {
    // the current Fib number becomes the last term as the iteration moves on
    lastTerm = lastTerm + secondLastTerm; // line 1
    // and the second last term will become the PREVIOUS last term
    secondLastTerm = lastTerm - secondLastTerm; // line 2
  }

  return lastTerm;
};

The first term we need to calculate is the 3rd, so we need to define the first two here as well. The first term is 1; this will be the secondLastTerm from the point of the 3rd term. Similarly, if we take the 3rd term as current, the lastTerm will be the 2nd.

We return them if the parameter is 1 or 2, no change in this compared to the previous code.

The magic starts with the for loop. The iteration starts at 3(remember, this is the first term to be calculated) and goes until and including n.

Here comes the hard part. In terms of the current Fibonacci number (which we want to calculate), we need to add the last and second last terms, this is straightforward, it comes from the definition. But at the same time, we prepare lastTerm for the computation of the next Fibonacci number, and make it equal to the current term (line 1), which we return when the iteration finishes. (At this point there will be no need to calculate the next Fibonacci number, so the value of lastTerm will be the actual Fibonacci number.)

Similarly, we need to slide secondLastTerm as well, and give it the value of the previous lastTerm (line 2). The value of lastTerm will be the new value calculated in line 1, so to get the previous value of lastTerm, we simply subtract what we added to it in line 1.

All we have to do now is to replace fibonacci with fibonacciAlternative in addEvenFibNumbers, and compare the computation time. You will see the difference. Well, that wasn’t easy. Reread this section if it wasn’t clear. And again. This is what I do when I come across something new and difficult. It will click.

Conclusion

This is a nice little problem to solve. Recursion is much worse in terms of performance than simple for loops. The greater the number we work with is, the more visible the difference is between each method.

It would be a good challenge to write the addEvenFibNumbers function in a more functional way using filter (instead of the if statement) and reduce (instead of the continuous addition). If you have time, feel free to work on it.

Enjoy coding!