JavaScript implementation of the NTH term Fibonacci sequence of seven solutions

Writing in the front

The code of this article is in fact as early as the beginning of 2020 a night on a whim has been achieved, and in his own blog wfk007. Making. IO / 2020/03/28 /… However, if you look back now, it’s mostly code with little explanation, which is one of the reasons I wrote this article. In addition, since the blog was built with Hexo and the comment system used Diaqus, it couldn’t be used on the domestic website, which was very messed up. The data of the blog’s reading volume was set at the beginning, but later I stopped it due to the inexplicable bug that the reading volume would automatically decrease after refreshing. That’s why I wanted to move from blogging to nuggets, learning + documenting + sharing. Finally, because of the reason of personal ability, the error in the article is inevitable, welcome the big guy criticism and correction ~

What are Fibonacci numbers

$1,1,2,3,5,8,13,21…$

The sequence above is a Fibonacci sequence, and the pattern is obvious: the first two terms are 1, and starting with the third term, each term equals the sum of the first two terms. (For a more detailed explanation, please refer to Wikipedia or Baidu Encyclopedia.)

The mathematical definition is:

• 
  $F(1) = 1, F(2) = 1$
• 
  $F(n) = F(n-1) + F(n-2) (n ≥ 3, n ∈ n *)$

solution

Following the above mathematical definition, we can logically write the first solution as follows: recursion

const fibs = n= > {
  if (n === 1 || n === 2) return 1;
  else return fibs(n - 1) + fibs(n - 2);
};
Copy the code

Write the recursive exit first, return 1 when n === 1 or 2 (the first two terms), otherwise add the results of the first two terms and return.

After writing the code, we randomly tested several data points and found that we got the correct result

However, when we input a relatively large n, such as 100, the program can not print the result after running. Is there something wrong with our code?

To see what’s going on, let me draw a simple recursive call when n === 100:

The time complexity can also be calculated very simply :(the time complexity of recursive calls equals the sum of the time complexity of all recursive subroutines)

$O(n) = 1 + 2^1 + 2^2 + … + 2^{n-1}$

The calculation result is actually the sum of the first n terms of a geometric sequence with the first term being 1 and the common ratio being 2. The formula for the sum of the first n terms of a geometric sequence is given as follows:

$S_n = \frac{a_1(1-q^n)}{1-q} (q \neq 1)$

Calculation:

$O(n) = 2^n – 1$

Remove the constants and coefficients, and you get O(n)=2nO(n) =2 to the nO(n)=2n

It is concluded that the time complexity of the above recursive calls is exponential. As n increases, the time complexity increases exponentially, which also explains why the program is slow to produce results when a large n is entered.

An important reason for the time-consuming recursive process mentioned above is repeated calculation. Fibs (98) was calculated once when FIBS (100) was calculated, and FIBS (98) was calculated again when FIBS (99) was calculated. We can optimize the recursive process mentioned above from this point and write the second solution: Recursion + memo method:

const dict = {};
const fibs = n= > {
  if (n === 1 || n === 2) {
    return 1;
  }
  if(! dict[n]) { dict[n] = fibs(n -1) + fibs(n - 2);
  }
  return dict[n];
};
Copy the code

The processing is simple, introducing a dict (or map) to store the results of the intermediate state, sacrificing space for time. If the result is already in the dict cache before performing a recursive operation, it is fetched directly from the cache, otherwise the recursive call is performed. When n === 100, the program recursively calls:

Time complexity settlement results are as follows:

$O(n) = 1 + 2 + 2 + 2 + … + 2 = 2(n – 1) + 1 = 2n – 1 = n$

Calculate n === 100 as follows:

Because the calculation result exceeds Number.MAX_SAFE_INTEGER, the accuracy problem is omitted. The calculation result cannot represent the correct result, but it has made a qualitative leap in execution efficiency compared with recursion.

In addition, in addition to using the memo method to optimize the recursive process, we can also use tail recursion to optimize the process, so we have the following third solution:

const fibs = n= > fibsTailRecursion(1.1, n);

const fibsTailRecursion = (ppre, pre, n) = > {
  if (n === 1) {
    return ppre;
  }
  return fibsTailRecursion(pre, pre + ppre, n - 1);
};
Copy the code

The difference between tail recursion and normal recursion above is: The last step of tail recursion is to call a fibsTailRecursion function (pre, pre + ppre, n-1). The last step of normal recursion above is to call two functions and add their results fiBS (n-1) + FIBS (n-2).

Process will be recursive call in memory formation A recursive call stack, prior to A recursive subroutine call (in A function recursive call A1), will be the current function (A) the context information into the stack, wait until the subroutine (A1) end of the call, will return to the original performing the son call the location of the position of (A call A1), Restore A’s context (input arguments, local variables, call locations of subroutines…) For example, the recursive call in method 1 is as follows :(depth-first)

• With an input parameter of n, callfibs(n - 1)And wait forfibs(n - 1)Returns the result of
• Take the new argument n-1 and continue the callfibs(n - 2)And wait forfibs(n - 2)Results back
• Take the new argument n-2 and continue the callfibs(n - 3)And wait forfibs(n - 3)Results back
• .
• Take the new parameter 3, continue to call fibs(2), ah, finally get the result, back up
• .
• After a very complicated recursive operation, finallyfibs(n - 1)Once it’s done, it’s a nightmarefibs(n - 2)The value of the
• fibs(n - 1) 和 fibs(n - 2)All calculated, add the results of both, function returns, end of execution

However, with tail-recursion optimization, the last step of a function is to call a function without saving the current execution context. When the initial input parameter is 1,1,n, the function is called as follows:

• callfibsTailRecursion(1, 1+1, n - 1)
• Continue calling the function with the new input parameters 1,2,n-1fibsTailRecursion(2, 3, n - 2)
• .
• Finally, n is reduced to 1, and the function is called again with new arguments x,y,1, and the value of x is the final result

Time complexity: O(n)O(n)O(n)

The NTH term of the Fibonacci sequence can also be solved by dynamic programming, so there is a fourth solution.

Before writing the dynamic programming algorithm we need to clarify a few points:

1. The definition of dp [I]
2. What is base case
3. The recursive formula

For the Fibonacci sequence:

1. Dp [I] is the Fibonacci number of the I +1 term, and we find dp[I -1].
2. In base case, dp[0] = 1, dp[1] = 1
3. The recursive formula is: dp[I] = DP [i-1] + DP [i-2];

After everything is ready to start coding, the code implementation is as follows:

const fibs = n= > {
  const dp = [1.1];
  if (n === 1 || n === 2) {
    return 1;
  }
  for (let i = 2; i < n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n - 1];
};
Copy the code

Time complexity: O(n)O(n)O(n)

Alternatively, we can use the median method to solve the problem, going back and forth, exchanging values as we go through the loop, so we have a fifth method, which looks like this:

const fibs = n= > {
  if (n === 1 || n === 2) {
    return 1;
  }
  let ppre = 1;
  let pre = 1;
  let tmp;
  for (let i = 2; i < n; i++) {
    tmp = ppre + pre;
    ppre = pre;
    pre = tmp;
  }
  return tmp;
};
Copy the code

Time complexity: O(n)O(n)O(n)

In addition, we know that the Fibonacci sequence has a general formula, which is as follows:

$a_n = [(\frac{1 + \sqrt 5}{2})^{n} – (\frac{1 – \sqrt 5}{2})^{n}]$

Using the general formula, we can use the sixth method, the code is as follows:

const fibs = n= >
  Math.round(
    (Math.sqrt(5) / 5) *
      (Math.pow((1 + Math.sqrt(5)) / 2, n) -
        Math.pow((1 - Math.sqrt(5)) / 2, n)),
  );
Copy the code

Time complexity: O(1)O(1)O(1)

The final method is to use matrix multiplication of linear algebra, which works as follows: [[0, 1], [0, 0]] ∗ [[0, 1], [1, 1]] n – 1 = [[F (n – 1), F (n)], [0, 0]] [[0, 1], [0, 0]] * [[0, 1], [1, 1]] ^ = {}, n – 1 [[F (n – 1), F (n)], [0, 0]] [[0, 1], [0, 0]] ∗ [[0, 1], [1, 1]] n – 1 = [[F (n – 1), F (n)], [0, 0]]

According to the matrix fast power solution of the Fibonacci sequence of this article, using JS to achieve it. Among them, the matrix multiplication part is relatively rough, and the final code is as follows:

// M *n *k = m*k
const matrixMultiply = (arr1, arr2) = > {
  let result = [];
  for (let i = 0; i < arr1.length; i++) {
    let current = [];
    for (k = 0; k < arr1.length; k++) {
      / / accumulation
      let sum = 0;
      for (let j = 0; j < arr1[i].length; j++) {
        sum = sum + arr1[i][j] * arr2[j][k];
      }
      current.push(sum);
    }
    result.push(current);
  }
  return result;
};

const fibs = n= > {
  let result = [
    [0.1],
    [0.0]];const arr = [
    [0.1],
    [1.1]];for (let i = 0; i < n - 1; i++) {
    result = matrixMultiply(result, arr);
  }
  return result[0] [1];
};
Copy the code