Writing a function to find the Fibonacci number, given n in F(n) is a popular JavaScript algorithm interview question, yet many developers find it challenging. In this article, I’ll demonstrate how to find the Fibonacci number using both iterative and recursive methods (with memoization).

First let’s start by understanding what the Fibonacci sequence is and the typical interview question about Nth Fibonacci Number.

What is Fibonacci sequence?

The Fibonacci sequence is a progression of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. This series appears as follows:

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

To determine the next number in the sequence, sum the two preceding numbers. For instance,

the number 5 is obtained by adding 2 and 3 together.
the number 34 results from the sum of 13 and 21.

Thus, the formula F(n) = F(n-1) + F(n-2) applies when n > 1 plus F(0) = 0 and F(1) = 1.

During a technical interview, you might be asked:

Can you write a function that returns the n-th number in the Fibonacci sequence? (0 <= n <= 30)

Given the problem, we need to write a function that takes an entry number, such as 7, and returns its corresponding Fibonacci sequence number, which in this case would be 13 (Note: n starts from 0 as described in the constraints: 0 <= n <= 30).

This challenge is also available on LeetCode for further practice.

In this article, we will write the algorithm both in iterative and recursive solutions. First, let’s take a look at the iterative solution.

Iterative solution

The iterative solution employs an array to hold the two preceding numbers in the sequence, continuously updating these values until it reaches the desired index.

This approach gives us the linear runtime and constant space complexity, making it highly efficient.

Let’s first dive into a detailed walkthrough to thoroughly understand this approach.

Walkthrough

First of all, let’s revisits the formula again.

F(n) = F(n-1) + F(n-2) applies when n > 1 plus F(0) = 0 and F(1) = 1. The constraints are 0 <= n <= 30.

So if n is less than or equal to 0, we simply return 0. Similarly, if n equals 1, we return 1.

Moving forward, we set up for the iteration by initialising an array containing two elements, [0, 1].

Now, we proceed to loop through until we reach n. Inside the loop, we’ll first calculate the next Fibonacci number. Then, we’ll update the array by shifting the second item to the first position, and placing the next number in the second position. Upon completing the loop, the second item in our array will represent the target value, which we will then return.

Let’s visualise this process within the loop. In this example, we aim to get the 5th Fibonacci number.

1st loop

Array (starting) = [0, 1]
Index = 2
Next value = 1 (0 + 1 from starting array)
Array (updated) = [1, 1]

In the first iteration, starting from the 2nd index, the next value is calculated by summing the two numbers in the array [0, 1], resulting in 1. After determining the next value, the array is updated by shifting the second element to the first position and setting the second element as the newly computed next value. Consequently, the array becomes [1, 1]. This process is repeated in subsequent iterations, updating the array and computing new Fibonacci numbers until the desired index is reached, at which point the second element of the array is returned. Let’s continue to see the subsequent iterations.

2nd loop

Array (starting) = [1, 1]
Index = 3
Next value = 2 (1 + 1)
Array (updated) = [1, 2]

In the second iteration, the next value is calculated as 2. We then shift the second element, 1, to the first position and update the second element with the new next value, 2. As illustrated in the image above, the number in the green box aligns with the second element of the updated array, which is now 2.

3rd loop

Array (starting) = [1, 2]
Index = 4
Next value = 3 (1 + 2)
Array (updated) = [2, 3]

In the third iteration, using the same method, the array updates to [2, 3].

4th loop (final)

Array (starting) = [2, 3]
Index = 5
Next value = 5 (2 + 3)
Array (updated) = [3, 5]

In this final iteration, we get the [3, 5] as the updated array. And we exit out of the loop and return the second item from the array which is 5.

With this walkthrough in mind, let’s write the code.

Implementation

Here is the complete code.

function fib(n) {
  if (n <= 0) return 0;
  if (n === 1) return 1;

  const prevTwo = [0, 1];

  for (let i = 2; i <= n; i++) {
    const next = prevTwo[0] + prevTwo[1];
    
    prevTwo[0] = prevTwo[1];
    prevTwo[1] = next;
  }

  return prevTwo[1];
}

And the runtime of this algorithm beats 97.71% and also 99.24% for the memory of the submissions on LeetCode.

Let’s go through the code line by line.

Initially, we’ll handle the first two scenarios as outlined earlier in the walkthrough (lines 2 and 3).

Then, we initialise prevTwo with [0, 1] (line 5). This array will keep track of the Fibonacci numbers as described in the walkthrough. Let's take a closer look at the loop (line 7 - 12).

The loop starts with i = 2 because the first two Fibonacci numbers (0 and 1 for fib(0) and fib(1), respectively) are already initialised in the prevTwo array. The loop will continue as long as i is less than or equal to n, the desired position we are trying to get. In the loop, we calculate the next Fibonacci number by summing the two most recent numbers stored in prevTwo. Once we get the next number, we move the second element of the array (the most recent Fibonacci number) to the first position and also set the second element to the newly calculated Fibonacci number (next).

Once it reaches n, eventually, we’ll return prevTwo[1] as the final result (line 14).

Big O

Time complexity: O(n)

The time complexity is O(n), which means it takes linear time relative to the size of the input n. This is because the function only loops once through the numbers from 2 to n, performing a constant amount of work in each iteration to calculate the next number in the Fibonacci sequence.

Space complexity: O(1)

The space complexity is O(1), indicating that the amount of memory used by the function does not increase with the size of the input. This efficiency comes from using only a small, fixed amount of space (a two-element array) to hold the last two numbers of the Fibonacci sequence, regardless of how large n is.

Recursive solution

The recursive solution might seem more complex at first, but there's no need to worry - we'll break it down together step by step.

We'll begin with the basic approach and understand its time complexity and identify potential inefficiencies. Following that, we'll enhance the algorithm using a technique known as memoization, a concept frequently asked in technical interviews.

As a side note, since recursion plays a central role in this approach, grasping how recursion functions is crucial. If you're not yet familiar with recursion, I highly recommend checking out this article, which provides a detailed explanation of how it operates.

Let's dive into the walkthrough to get started.

Walkthrough - Basic approach

Let's review the formula once more:

F(n) = F(n-1) + F(n-2) applies when n > 1 plus F(0) = 0 and F(1) = 1. The constraints are 0 <= n <= 30.

Similar to the iterative approach, our goal is to calculate the 5th Fibonacci number and we can express the formula as follows:

F(5) = F(5-1) + F(5-2)

and this is equivalent to:

F(5) = F(4) + F(3)

Observing F(4), its value is derived from:

F(4) = F(3) + F(2)

And if we want to get F(3), it will be:

F(3) = F(2) + F(1)

So if we illustrate it in a tree (fib is the function name we are going to use in our code):

This tree chart shows the breakdown of each F(n) into its components, showing how each Fibonacci number is derived from the sum of the two preceding numbers. This tree will start with F(5) at the root and split into F(4) and F(3) on the next level. Each of those will further break down until reaching the base cases of F(1) and F(0).

This visualisation helps understand the recursive nature of the Fibonacci sequence and how each call stacks upon the previous ones to reach the final value.

Let's identify the conditions for recursion:

Base case: if n equals 1, we return 1 and and if it equals 0, we return 0 begin popping off the call stack.
Different input: we decrement n by either 1 or 2 at each step.

To better understand how this recursion works, let’s demonstrate its execution within the call stack.

Call Stack

Initial

fib(5)
n = 5
return: fib(4) + fib(3)

Current call stack:

fib(5)

Initially, we call fib(5), where n is set to 5. As illustrated in the chart, to compute fib(5), we add fib(4) and fib(3). This sum represents the value returned by fib(5).

1st recursion

fib(4)
n = 4
return: fib(3) + fib(2)

Current call stack:

fib(4)
fib(5)

In recursion, we need to first complete all recursive calls from fib(4) before moving on to resolve fib(3). The return value of fib(4) will be fib(3) + fib(2).

2nd recursion

fib(3)
n = 3
return: fib(2) + fib(1)

Current call stack:

fib(3)
fib(4)
fib(5)

Again we need to resolve all recursive calls from fib(3) before coming back and resolving fib(2) and it will return fib(2) + fib(1).

3rd recursion

fib(2)
n = 2
return: fib(1) + fib(1)

Current call stack:

fib(2)
fib(3)
fib(4)
fib(5)

fib(2) returns fib(1) + fib(0).

4th recursion

fib(1)
n = 1
return 1

Current call stack:

fib(1)
fib(2)
fib(3)
fib(4)
fib(5)

We reach the base case, so we return 1, which removes fib(1) from the call stack.

fib(2) => return 1
fib(3)
fib(4)
fib(5)

5th recursion onwards

fib(0)
n = 0
return 0

Current call stack:

fib(0)
fib(2) => return 1
fib(3)
fib(4)
fib(5)

fib(0) reaches the base case too, returning 0 and removed from the call stack.

fib(2) => return 1 + 0
fib(3)
fib(4)
fib(5)

Because we now also resolved the fib(2) which is popped off from the call stack, we move onto the other fib(1).

fib(1)
fib(3) => return 1
fib(4)
fib(5)

fib(1) hits the base case so returns 1:

return 1
fib(3) => return 1
fib(4)
fib(5)

and fib(3) will return fib(2) + fib(1):

fib(3) => return 1 + 1
fib(4)
fib(5)

and move onto the next fib(2) which will require to call fib(1) and fib(0) recursively.

I think you're starting to see the pattern here. We use recursion to split the task into smaller steps until we hit the base case. Then, we start coming back up by popping off the call stack, step by step, until we finally arrive at the Nth Fibonacci number.

Let’s implement the code.

Implementation

Here is the complete code.

function fib(n) {
  if (n <= 0) return 0;
  if (n === 1) return 1;

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

As explained in the walkthrough, when n is 0 or 1, the function returns 0 or 1 respectively (line 2, 3). For other values of n, the function recursively applies the formula fib(n - 1) + fib(n - 2) to compute the Fibonacci number (line 5).

Now let’s take a look at its runtime and identify its inefficiencies.

Big O

Time complexity: O(2^n)

The runtime is O(2^n) which is significantly inefficient due to the repetitive nature of the calculations.

As you can see from the chart above, each call to the Fibonacci function results in two additional calls, following the formula F(n) = F(n-1) + F(n-2). This pattern creates an exponential growth in the number of calls, specifically following a binary tree structure where each node branches into two further calls.

The depth of this tree corresponds to n, and since each level of the tree has twice as many calls as the level above it, the total number of calls made is approximately 2^n. Therefore, the time complexity of the Fibonacci sequence calculated is O(2^n), which is highly inefficient for large values of n. This exponential time complexity highlights the importance of optimisation techniques to improve the performance of recursive algorithms. In the next section, we will dive into a technique called memoization.

Space complexity: O(1)

You might be thinking it would be O(1) because we are not storing anything in memory. However, it’s actually O(n). It’s because as we saw above, each recursive call to the Fibonacci function requires a new stack taking up the space in the call stack.

Since the function recurses down to the base case before resolving and returning up the call stack, the maximum depth of the call stack at any point directly correlates to n, the position of the Fibonacci number being calculated.

Thus, the space complexity is determined by the height of the recursive call tree, which, in the worst case, is O(n) for the Fibonacci sequence.

Memoization

Let’s revisit the chart and find a pattern.

As you can see, there are repeated recursive calls grouped in each colour. That means if we could store the results of these calls in a readily accessible location (like a hash map) for constant runtime, O(1), we could significantly improve the execution speed. This strategy of caching results to avoid redundant calculations is known as Memoization.

What is Memoization?

Memoization is an optimisation technique that involves storing the results of expensive function calls and returning the cached result when the same inputs occur again. Essentially, it avoids the computation of results that have already been calculated by saving these results to a memory-based data structure (like a dictionary or an array).

Each time the function is called, the memoization mechanism first checks whether the result for the given input is already present in the cache. If it is, the cached result is returned; otherwise, the function is executed, and the result is added to the cache.

Implementing Memoization

Unlike Python, JavaScript does not have a built-in decorator for memoization, but it can be implemented in JavaScript using a simple object to store the results of previously computed values. This method is particularly useful for recursive functions like calculating Fibonacci numbers, where the function is called repeatedly with the same arguments.

Using an object for this purpose is highly effective because it provides constant runtime, O(1) to access results, ensuring that retrieval and storage operations are performed quickly and efficiently.

Let’s take a look at the optimised code with the memoization.

Implementation

Here is the complete code.

function fib(n, memoize = {0: 0, 1: 1}) {
  if (n in memoize) { // or memoize.hasOwnProperty(n)
    return memoize[n];
  }

  memoize[n] = fib(n - 1, memoize) + fib(n - 2, memoize);

  return memoize[n];
}

In LeetCode, this recursive approach outperforms 98.33% of submissions in terms of runtime. We'll discuss further in the Big O section below.

Let’s take a look at each line.

This optimised code accepts an additional parameter, memoize with the default value of {0: 0, 1: 1} (line 1). The memoize parameter initially stores the first two Fibonacci numbers: Fibonacci(0) = 0 and Fibonacci(1) = 1. If no second argument is provided when the function is called, it defaults to this initial object.

And then we have a base case (line 2-4) which checks if the value of n is already a key in the memoize object and if n is found in the memoize object, the function returns the value associated with n. ✨ This check is crucial as it prevents redundant calculations by returning the result immediately if it has been computed previously. We can do another way to check for the presence of a key in an object:

if (memoize.hasOwnProperty(n)) {

And we have recursive calls (line 6). If n is not in the memoize object from the base case above, the function calculates it by recursively calling itself to get the Fibonacci numbers for n-1 and n-2, then adding these two numbers together. The result is then stored in the memoize object under the key n. ✨ This storage is what enables memoization, ensuring each Fibonacci number is computed only once.

Finally, the function returns the computed Fibonacci number for n which is now stored in the memoize object (line 8). This value has either just been calculated or was retrieved from the memoize object.

Now let’s talk about the runtime and space complexity for the recursive memoization Fibonacci function.

Big O

Time complexity: O(n)

The time complexity with the memoization is O(n). With memoization, each Fibonacci number from 0 to n is calculated exactly once. After a Fibonacci number is computed, its value is stored in the memoize object, meaning any subsequent request for that number can be fulfilled in constant time O(1).

Therefore, the function primarily performs n key computations (where n corresponds to Fibonacci numbers from 2 to n, since Fibonacci(0) and Fibonacci(1) are provided initially). This leads to a linear runtime complexity, making the recursive function significantly more efficient compared to its exponential counterpart without memoization.

Space complexity: O(n)

The space complexity of the memoized Fibonacci function is mainly coming from two sources: the memoization hash table and the recursive call stack.

Even though memoization significantly reduces the number of recursive calls by retrieving stored values, there is still a recursive call stack that uses space same as the non-optimised recursive approach above. However, due to the efficient retrieval from the hash table, the depth of the call stack does not exceed n, ensuring that the total space complexity remains linear, O(n).

Additionally the memoize hash table stores each computed Fibonacci number to prevent redundant calculations, growing linearly thus contributing an O(n) space complexity.

Therefore, the total space complexity can be expressed as O(n) + O(n) = 2O(n). However, in Big O notation, constants are not considered, so this simplifies to O(n).

~~~

I hope you enjoyed this article. To stay updated with new posts on algorithms and data structures, please make sure to subscribe below and follow me on LinkedIn. 😃