标签： Fibonacci

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

使用递归实现斐波那契数列其实很浪费，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];
}