题目名称：斐波那契数列
解法一：暴力
function Fibonacci(n)
{
// write code here
if (n === 0) {
return 0;
} else if (n === 1) {
return 1;
} else return Fibonacci(n - 1) + Fibonacci(n - 2);
}缺点：有大量重复的递归运算，比如 f(n)和 f(n - 1)向下递归需要各自计算 f(n - 1)、f(n−2) 的值，以此类推，很容易超时，为了防止重复计算，就有了解法二
面试的时候有被问到，为什么暴力解法会超时，以上就是原因。
解法二：加缓存
function Fibonacci(n)
{
// write code here
let result = 0;
if (n === 0) {
Fibonacci.result = [0];
return 0;
} else if (n === 1) {
Fibonacci.result = [0, 1];
return 1;
} else {
result = Fibonacci(n - 1) + Fibonacci.result[n - 2];
Fibonacci.result.push(result);
return result;
}
}给函数Fibonacci添加属性result用以存放计算结果，防止重复计算
解法三：动态规划
function Fibonacci(n)
{
// write code here
let i = 0, j = 1, sum = 0;
for (let a = 0; a < n; a++) {
sum = i + j;
i = j;
j = sum;
}
return i;
}从第一个数开始算起，到n截止，可以保证没有重复计算
解法四：尾调用优化
function Fibonacci(n){
return fibImp(0,1,n);
};
function fibImp(a,b,n){
if(n===0){
return a;
}
return fibImp(b,a+b,n-1);
}尾调用优化的条件就是确定外部栈帧真的没有必要存在了。涉及的条件如下：
1）代码在严格模式下执行；
2）外部函数的返回值是对尾调用函数的调用；
3）尾调用函数返回后不需要执行额外的逻辑；
4）尾调用函数不是引用外部函数作用域中*变量的闭包。
参考：
《JavaScript高级程序设计（第4版）》