Home > Article > Web Front-end > JS implements Fibonacci sequence
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)!