How to implement JavaScript output of Fibonacci sequence

topic

There is a question that we need to answer:

• Try to output the first 10 terms of the Fibonacci sequence, namely 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.
  

analyze

Some people may be confused when they see the concept of "Fibonacci sequence" in the title, but there is no need to be confused!

For this question, you can ignore this unfamiliar concept. We only need to care about the numerical pattern given later.

We can see that the rule can be summarized in one sentence: starting from the third digit, the value of each subsequent term is equal to the sum of the previous two terms. Expressed in formula, it is: an = an-1 + an-2 (n ≥ 2).

According to the requirements of the topic, we are actually asked to do two things:

1. Generate the value of each item.
2. Print out all values.
   

Basic solution

Solution:

• Create an array to store the values ​​of each item in the sequence.
• The for loop generates each item of the sequence and stores it in an array (in order to calculate the values ​​of the subsequent items), and prints the generated items.
  

The code is implemented as follows:

/**
 * @description Create a method to generate a sequence array * @param {number} n indicates how many items to generate (that is, the array length, not the array subscript)
 */
function createFibArr(n) {
    //Declare an array to store data let fibArr = [];
    // Starting from the third item (subscript 2), each item is equal to the sum of the previous two items for (let index = 0; index < n; index++) {
        index < 2 ? fibArr.push(1) : fibArr.push(fibArr[index - 1] + fibArr[index - 2]);
        console.log(fibArr[index]);
    }
}

//Call method createFibArr(10);

analyze:

This should be the most basic method to solve the problem, and it is easy to achieve.

But if this is an interview question, such an answer can only be said to be mediocre, without any highlights. Most importantly, it does not reflect our unique temperament. Therefore, we should use other means to improve our own style!

Basic recursion

Solution:

• The corresponding value of each position is calculated by recursion (there is a premise here: the first and second items are fixed values, otherwise, recursion will not work well).
• Print the results.
  

The code is implemented as follows:

/**
 * @description Calculate the value of the nth item* @param {number} n represents the subscript value of each item* @returns {number} the value of the position with subscript n*/
function calFibValue(n) {
    console.count("Number of executions:")
    return n < 2 ? 1 : (calFibValue(n - 1) + calFibValue(n - 2));
}

/**
 * @description Print calculation results* @param {number} n represents the number of items to be printed*/
function printRes(n) {
    for (let index = 0; index < n; index++) {
        console.log(calFibValue(index));
    }
}

//Call the print method printRes(10);

// Execution times: 276

analyze:

The use of recursion does improve the quality of the code, but it also brings about another problem: performance.

The value of each item is calculated and accumulated starting from the first item. For example, the process of calculating the value of the fourth item is as follows:

• Returns the value of the first item: 1.
• Returns the value of the second item: 1 .
• The third term is calculated to be 1 + 1 = 2.
• The fourth term is calculated to be 2 + 1 = 3.
  

When calculating the value of the fifth item, the above process must be used to obtain the value of the fourth item, which involves a large number of repeated operations.

In order to impress the interviewer, we still need to make further optimizations!

Recursive Optimization

Solution:

• The logic of the recursive part causes repeated calculations, so the optimization point is here.
• Since there are repeated operations, it means that the subsequent operations can actually use the values ​​​​that have been calculated previously, so we need to introduce a cache to save the results of each calculation.

Code implementation:

/**
 * @description Calculate the value of the nth item* @param {number} n represents the subscript value of each item* @returns {number} the value of the position with subscript n*/

// A Map structure that stores the results of each calculation // An array can also be used here, but in terms of semantics, there is no Map or object directly let fibValueMap = new Map();
function calFibValue(n) {
    console.count("Number of executions: ");
    // If the corresponding value already exists in the cache, return directly if (fibValueMap.has(n)) {
        return fibValueMap.get(n);
    }
    const value = n < 2 ? 1 : (calFibValue(n - 1) + calFibValue(n - 2));
    // After calculating each item, it needs to be stored in Map in time
    fibValueMap.set(n, value);
    return value;
}

/**
 * @description Print calculation results* @param {number} n represents the number of items to be printed*/
function printRes(n) {
    for (let index = 0; index < n; index++) {
        console.log(calFibValue(index));
    }
}

//Call the print method printRes(10);

// Execution times: 26

analyze:

According to the printed count, the number of recursions after optimization is about 1/10 of that before optimization, which is a surprising result.

I think the interviewer will be satisfied this time.

Summarize

No matter how things change, the essence remains the same. As long as you have a clear idea of ​​how to solve the problem, code implementation is just a result. In our daily work and study, we must consciously cultivate our divergent thinking and look at problems from multiple angles. You may discover different scenery! I hope it can be inspiring to everyone!

In an interview, it is understandable that we use some seemingly sophisticated ideas in order to highlight our unique qualities or when the interview questions have specific requirements.

However, in daily work, I still recommend that: when the performance is similar, if the problem can be solved with basic methods, do not use "advanced" methods, because the probability of error with basic methods is much smaller. For example, for today's problem, the basic solution actually has the best performance.

If we write fewer bugs, we will have more time to slack off, right?

This is the end of this article about JavaScript output of Fibonacci sequence. For more relevant JS output of Fibonacci sequence content, please search 123WORDPRESS.COM's previous articles or continue to browse the following related articles. I hope everyone will support 123WORDPRESS.COM in the future!