JS implements Fibonacci sequence-JS Tutorial-php.cn

JS implements Fibonacci sequence

黄舟

Release： 2017-02-10 09:49:18

Original

2283 people have browsed it

Input n, find the nth term of the Fibonacci sequence

function fibonacci(n) {
  if (n < 0) {
throw new Error('输入的数字不能小于0');
  }
  if (n == 0) {
return 0;
  } 
  if (n == 1) {
return 1;
  }
  return fibonacci(n-1) + fibonacci(n-2);
}

Copy after login

This is actually not a very good method
For example, when finding fibonacci(10), it is decomposed into fibonacci(9) and fibonacci( 8), but fibonacci(9) will be decomposed into fibonacci(8) and fibonacci(7), in which fibonacci(8) is repeatedly calculated, and so on. There are many repeated calculations. The simplest way is to record what has been done. Calculated value:

function fibonacci2(n) {
  if (n < 0) throw new Error('输入的数字不能小于0');
  let arr = [0, 1];
  function calc(n) {
  if (n<2) {
      return arr[n];
  }
  if (arr[n] != undefined) {
      return arr[n];
  }
  let data = calc(n-1) + calc(n-2);
  arr[n] = data;
  return data;
  }
  return calc(n);
}

function fibonacciFunc() {
  let arr = [0, 1];
  function calc(n) {
    if (n < 0) throw new Error('输入的数字不能小于0');
    if (n<2) return arr[n];
    if (arr[n] != undefined) {
      return arr[n];
    }
    let data = calc(n-1) + calc(n-2);
    arr[n] = data;
    return data;
  }

  return calc;
}   
let fibonacci3 = fibonacciFunc();

Copy after login

The above two methods use closures

The disadvantage of fibonacci3 is that as long as fibonacci3 is not released, the arr array will always exist in the memory. Especially after calculating relatively large numbers; but when a large number of fibonacci numbers need to be calculated, fibonacci3 will be more advantageous, but remember to release fibonacci3 at the end, that is:

fibonacci3 = null;

Copy after login

Another way is not to use recursion , directly loop

function fibonacci4 (n) {
  if (n < 0) throw new Error('输入的数字不能小于0');
  let dataMinusTwo= 0,
    dataMinusOne = 1,
    data;
  if (n == 0) return dataMinusTwo;
  if (n == 1) return dataMinusOne;
  for (var i=2;i<=n;i++) {
    data = dataMinusOne + dataMinusTwo;

    dataMinusTwo = dataMinusOne;
    dataMinusOne = data;
  }
  return data;
}

Copy after login

The above is the content of js to implement the Fibonacci sequence. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!