本文主要是介绍JavaScript斐波纳契数列非递归算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一般斐波纳契数列采用递归或是数组缓存的方式，这里的方法不考虑重复计算斐波纳契数列的情况。
fibonacci 数列定义，查看百度百科的解释>>
n = 1,2 时，fib(n) = 1
n > 2 时，fib(n) = fib(n-2) + fib(n-1)
1、递归
function Fib(n) {
return n < 2 ? n : (Fib(n - 1) + Fib(n - 2));
}
2、数组缓存
var IterMemoFib = function() {
var cache = [1, 1];
return function (n) {
if (n >= cache.length) {
for (var i = cache.length; i < n ; i++ ) {
cache[i] = cache[i - 2] + cache[i - 1];
}
}
return cache[n - 1];
}
}();
3、直接使用加法
function fib(n) {
if (n < 2) {
return 1;
}
var a = 1, b = 1;
for (var i = 2; i < n - 1 ;i++ ) {
b = a + b;
a = b - a;
}
return a + b;
}
对比：
如果只使用一次运算，第三种方法速度最快；
如果多次使用，第二种方法明显优于其它两种；
在n较大的情况下不推荐使用第一种；n为10*10000的时候递归就已经报内存溢出了
下面是在IE8下测试的结果(n为100W)：
如果只需要计算一次，第三种方法应该是最优的，而且当n越大的时候，数组占有的内存空间也将越大。
完整代码：
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html><head><title> new document </title><meta name="generator" content="editplus" /><meta name="author" content="" /><meta name="keywords" content="" /><meta name="description" content="" /><meta http-equiv='content-type' content='text/html;charset=utf-8' /></head><body><script type="text/javascript">function Fib(n) {return n < 2 ? n : (Fib(n - 1) + Fib(n - 2));
}var IterMemoFib = function() {var cache = [1, 1];return function (n) {if (n >= cache.length) {for (var i = cache.length; i < n ; i++ ) {cache[i] = cache[i - 2] + cache[i - 1];}}return cache[n - 1];}
}();function fib(n) {if (n < 2) {return 1;}var a = 1, b = 1;for (var i = 2; i < n - 1 ;i++ ) {b = a + b;a = b - a;}return a + b;
}var num = 10000*100;function test(fn, n) {var date = +new Date(); fn(n);return new Date().getTime() - date;
}//document.write('第一种方法，运算时间：' + test(Fib, num) + '<br/>');
document.write('第二种方法，运算时间：' + test(IterMemoFib, num) + '<br/>');
document.write('第三种方法，运算时间：' + test(fib, num));document.write('<br/><br/><br/>');document.write('第二种方法，运算时间：' + test(IterMemoFib, num) + '<br/>');
document.write('第三种方法，运算时间：' + test(fib, num));
</script></body>
</html>这篇关于JavaScript斐波纳契数列非递归算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
