斐波那契数列
斐波那契数列的公式为 Fn = Fn-1 + Fn-2。换句话说，下一个数字是前两个数字的和。
前两个数字是 1，然后是 2(1+1)，然后是 3(1+2)，5(2+3) 等等：1, 1, 2, 3, 5, 8, 13, 21...。
斐波那契数列与黄金分割以及我们周围的许多自然现象有关。
编写一个函数 fib(n)，返回第 n 个斐波那契数。
工作示例
function fib(n) { /* your code */ }
alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757附注：该函数应快速执行。调用fib(77)不应超过一秒钟的几分之一。
我们可以尝试的第一个解决方案是递归方法。
斐波那契数列根据定义是递归的。
function fib(n) {
return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}
alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // will be extremely slow!…但是对于较大的n值，它非常慢。例如，fib(77)可能会使引擎挂起一段时间，消耗所有 CPU 资源。
这是因为该函数进行了太多子调用。相同的值被反复重新计算。
例如，让我们看看fib(5)的计算片段。
...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...在这里我们可以看到fib(3)的值对于fib(5)和fib(4)都是必需的。因此，fib(3)将被完全独立地调用和计算两次。
这是完整的递归树。
我们可以清楚地注意到fib(3)被计算了两次，而fib(2)被计算了三次。计算的总量增长速度远快于n，即使对于n=77，它也变得非常大。
我们可以通过记住已经计算过的值来优化它：如果例如fib(3)的值被计算过一次，那么我们可以在未来的计算中直接重复使用它。
另一种方法是放弃递归，使用完全不同的基于循环的算法。
与其从n向下到较小的值，我们可以创建一个从1和2开始的循环，然后得到fib(3)作为它们的和，然后得到fib(4)作为前两个值的和，然后得到fib(5)，并一直向上，直到得到所需的值。在每一步中，我们只需要记住前两个值。
以下是新算法的详细步骤。
开始
// a = fib(1), b = fib(2), these values are by definition 1
let a = 1, b = 1;
// get c = fib(3) as their sum
let c = a + b;
/* we now have fib(1), fib(2), fib(3)
a b c
1, 1, 2
*/现在我们想要得到fib(4) = fib(2) + fib(3)。
让我们移动变量：a,b将得到fib(2),fib(3)，而c将得到它们的和。
a = b; // now a = fib(2)
b = c; // now b = fib(3)
c = a + b; // c = fib(4)
/* now we have the sequence:
a b c
1, 1, 2, 3
*/下一步将给出另一个序列号。
a = b; // now a = fib(3)
b = c; // now b = fib(4)
c = a + b; // c = fib(5)
/* now the sequence is (one more number):
a b c
1, 1, 2, 3, 5
*/…以此类推，直到我们得到所需的值。这比递归快得多，并且不涉及重复计算。
完整代码
function fib(n) {
let a = 1;
let b = 1;
for (let i = 3; i <= n; i++) {
let c = a + b;
a = b;
b = c;
}
return b;
}
alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757循环从i=3开始，因为第一个和第二个序列值被硬编码到变量a=1，b=1中。
这种方法被称为自底向上动态规划。