A Look At The Fibonacci Sequence: A Recursive and Iterative Solution

In mathematics, Fibonacci numbers form a sequence. The sequence commonly starts at 0 and 1. To get the next digit in the sequence, you simply add the previous two numbers together. For example, 0 + 1 = 1, thus the sequence begins: 0, 1, 1. If we continue this pattern, we’ll get the first few values of the sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Fibonacci numbers were first described in Indian mathematics by Acharya Pingala. However, they’re named after the Italian mathematician Leonardo of Pisa (later known as Fibonacci), who introduced the numbers in his book, Liber Abaci (The Book of Calculation).

That’s enough history for now. If you would like to learn more about the subject, Professor Keith Devlin from Stanford has an excellent lecture on YouTube, The Golden Ratio & Fibonacci Numbers: Fact versus Fiction.

In this article, we’re going to explore ways in which to solve an algorithmic interview question based on the Fibonacci sequence in JavaScript.

Fibonacci Interview Question

The Fibonacci sequence appears commonly as a coding challenge. It’s mostly to get a glimpse of your strengths as a developer and to see if you’re familiar with recursion. Surely, if you were to implement this algorithm iteratively, you would most likely be asked to rewrite it with a recursive solution.

Nonetheless, the challenge is quite simple. The directions are as follows:

• Print out the n-th entry in the fibonacci series.

For example, fib(0) should return 0, fib(2) should return 1, and so on.

Let’s explore the first solution.

Iterative Solution

function fib(n) {
  const result = [0, 1];

  for (let i = 2; i <= n; i++) {
    const a = result[i - 1];
    const b = result[i - 2];

    result.push(a + b);
  }

  return result[n];
}

console.log(fib(0)); // 0
console.log(fib(2)); // 1

Runtime: O(n) or linear runtime.

The trick in the code above is to declare a variable with two elements within: 0, 1. We’re doing this because we know they’re always going to be needed. It’s why we’re initializing the for loop at i = 2, skipping over the process of adding those two elements. Then we’re declaring two variables, a and b. Evidently, these variables will keep track of where we are within the sequence. They will be added together and pushed into the result array.

Recursive solution

The topic of recursion confuses many new developers (and experienced ones as well). Let’s take a quick look at a description from Wikipedia:

Recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code.

Put simply, recursion is a function that calls itself from within itself. Confusing, we know. Nonetheless, if your interviewer is asking you a question regarding the Fibonacci sequence, chances are they’re going to ask you for a recursive solution. Let’s study the solution and explore it a bit more in-depth to see how it works.

function fib(n) {
  if (n < 2) {
    return n;
  }

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

console.log(fib(0)); // 0
console.log(fib(2)); // 1

It looks rather simple, no? Just a few lines of code. But what is happening here?

First, we’re declaring a conditional to check if n < 2. This is the base case, which is necessary. If n is less than 2, then there’s no need to continue, n will be returned.

Although the base case is important, it isn’t so interesting. The line after is what we want to know about.

To put it into better perspective, let’s explore what happens if we were to call fib(3). If we call fib(3), the pass case will check if 3 < 2. It’s not, so the next step is return fib(3 - 1) + fib(3 - 2);, resulting in fib(3) + fib(1). Well, now we have fib(2) and fib(1), which will then be ran again and again until we’re left with a total of 2.

To get a better idea of this, study the diagram below.

The fib() function will recursively call itself until it reaches the base case.

You can clearly see that the only time the code isn’t getting passed the base case is when fib(2), which will then be ran again as fib(0) and fib(1), and we’ve already passed a case of fib(1), so fib(1) + fib(1) will return our result, 2.

Runtime: O(2^n) or exponential.

Conclusion

In this article, we explored a common interview question, the Fibonacci sequence and explored an iterative solution and a recursive solution in JavaScript. In the next article, we’ll explore a topic called memoization, and show how to optimize the recursive fib() function above.

Happy hacking!