What are Fibonacci numbers

The Fibonacci sequence refers to a sequence similar to the following:

1, 1, 2, 3, 5, 8, 13,....Copy the code

In pseudocode, the NTH number is the sum of the first two numbers in the sequence: f(n) = f(n-1) + f(n-2). A common way to do this is to translate the Fibonacci definition directly

// The Fibonacci sequence of the definition
function fibonacci(n) {
    if(n === 0 || n === 1)
        return n;
    return fibonacci(n- 1) + fibonacci(n2 -);
}
Copy the code

In this way, there will be a lot of repeated calculations, and the recursion of the deeper and deeper the stack is prone to recursive burst.

Space for time

A layer of cache is added to store previously calculated values. When a new value needs to be calculated, the system searches the cache first. If the cache is hit, the system returns directly. There are two ways to implement caching. The first is closure. The second is the function attribute approach, which is not recommended but can be effective.

Use closures for caching

// Closure + cache array
const fibonacci = (function() {
  const f = [0];
  return function(n) {
    if(f[n] ! = =undefined) return f[n];
    return f[n] = (n===1||n===2 ? 1 : fibonacci(n- 1) + fibonacci(n2 -))}}) ()Copy the code

The problem with the above implementation is that I use arrays for caching. If I don’t compute the Fibonacci sequence in sequence, it will add extra overhead. For example, if you evaluate Fibonacci (1000) directly, you’re going to initialize everything else in the array and call it undefined so it’s going to take a little bit longer, but you’re going to fill up the Fibonacci sequence between 1 and 1000.

One solution on the web is to replace arrays with objects for caching, which saves the time needed to fill undefined

// Closure + cache object
const fibonacci = (function () {
  const f = {}
  return function(n) {
    if(n === 0 || n === 1) {
      return n
    }
    if(f[n2 -= = =undefined) {
      f[n2 -] = fibonacci(n2 -)}if(f[n- 1= = =undefined) {
      f[n- 1] = fibonacci(n- 1)}return f[n] = f[n- 1] + f[n2 -]}}) ()Copy the code

Function property implementation

This approach takes a cue from the JavaScript Ninja Book and makes caching a function property to reduce the need for closures; But cache logic and business logic are generally not mixed, and the way function attributes are added complicates the understanding of the program.

const fibonacci = (n) = > {
  // Create a cache
  if(! fibonacci.f) {fibonacci.f = {}};/ / calculate
  if(n === 0 || n === 1) {
      return n
    }
    if(fibonacci.f[n2 -= = =undefined) {
      fibonacci.f[n2 -] = fibonacci(n2 -)}if(fibonacci.f[n- 1= = =undefined) {
      fibonacci.f[n- 1] = fibonacci(n- 1)}return fibonacci.f[n] = fibonacci.f[n- 1] + fibonacci.f[n2 -]}Copy the code

conclusion

The advantages of using space for time can reuse the previous calculation results, improve the performance and reduce the calculation cost; However, this approach is difficult to do load testing and algorithm complexity estimation because the output depends on the previous input.

Tail recursive optimization

As mentioned earlier, when calculating large values, recursively burst the stack. One solution is tail recursion. But this way needs to rewrite the parameters of the function, the settlement result as a parameter to pass down, in the actual use of the use of no problem to modify the interface, but in the computer programming time can not modify the input will be very passive. Tail recursion optimization may refer to: ruanyifeng.com/blog/2015/0…

function fibonacci(n, n1, n2) {
    if(n <= 1) {
        return n2
    }
    return fibonacci(n - 1, n2, n1 + n2)
}
Copy the code

Collection by other methods

The code is posted directly below

Use deconstruction assignment

const fibonacci = (n) = > {
  let a = 0;
  let b = 1;
  let i = 1;
  while(i++ <= n) {[a.b] = [b, a+b]}return a;
}
Copy the code

Closure implementation

const fibonacci=((s) = >(f=(i) = >s[i]||(s[i]=f(i- 1)+f(i2 -)))) ([0.1.1])
Copy the code

General term formula

General formula baike.baidu.com/item/%E6%96…

function fibonacci(n){
    var sum = 0
    for(let i = 1; i <= n; i += 1) {
        sum += fib(i)
    }
    return sum

    function fib(n) {
      const SQRT_FIVE = Math.sqrt(5);
      return Math.round(1/SQRT_FIVE * (Math.pow(0.5 + SQRT_FIVE/2, n) - Math.pow(0.5 - SQRT_FIVE/2, n))); }}Copy the code