JavaScript斐波纳契数列非递归算法

一般斐波纳契数列采用递归或是数组缓存的方式，这里的方法不考虑重复计算斐波纳契数列的情况。

n = 1,2 时，fib(n) = 1
n > 2 时，fib(n) = fib(n-2) + fib(n-1)

1、递归

<script type="text/javascript">
	function Fib(n) {
		return n < 2 ? n : (Fib(n - 1) + Fib(n - 2));
	}
</script>

2、数组缓存

<script type="text/javascript">
	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];
		}
	}();
</script>

3、直接使用加法

<script type="text/javascript">
	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;
	}
</script>

对比：

如果只使用一次运算，第三种方法速度最快；

如果多次使用，第二种方法明显优于其它两种；

在n较大的情况下不推荐使用第一种；n为10*10000的时候递归就已经报内存溢出了

下面是在IE8下测试的结果(n为100W)：

JavaScript斐波纳契数列非递归算法-编程知识网

如果只需要计算一次，第三种方法应该是最优的，而且当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>

转自：http://www.cnblogs.com/meteoric_cry/archive/2010/11/29/1891241.html