使用循环实现斐波那契数列

递归中比较常见的例子是斐波那契数列、汉诺塔。

使用递归实现斐波那契数列其实很浪费,f(n) = f(n-1) + f(n-2)。在进一步计算 f(n-1) = f(n-2) + f(n-3),会发现 f(n-2) 被重复计算。

下面是通过循环实现的斐波那契数列:

function Fibonacci(number) {
	var i, list = new Array();

	list[0] = 0;
	list[1] = 1;

	for (i = 1; i < number; i++) {
		list[i + 1] = list[i] + list[i - 1];
	}

	return list[number];
}

获取完整的斐波那契数列:

function Fibonacci(number, full) {
	var i, list = new Array();

	list[0] = 0;
	list[1] = 1;

	for (i = 1; i < number; i++) {
		list[i + 1] = list[i] + list[i - 1];
	}

	if (full) {
		return list;
	}

	return list[number];
}

作者: 袖之欢

科技改变生活,编程改变世界。

发表评论

电子邮件地址不会被公开。 必填项已用*标注