Home  >  Article  >  Web Front-end  >  JS implements Fibonacci sequence

JS implements Fibonacci sequence

黄舟
黄舟Original
2017-02-10 09:49:182235browse

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);
}

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();

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;

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;
}

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)!


Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn