递归优化的斐波那契数列

斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。

该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。如：1 1 2 3 5 8 ..
计算公式：F(N) = F(N - 1) + F(N - 2) (N > 1)

尾递归

尾递归：尾调用的一种特殊情况，特别的是尾递归在最后一步调用自身。

使用递归时，必须给出终止条件，否则代码将无限循环的执行。
我们经常使用诸如递归之类的方法来查找阶乘等，但递归容易发生堆栈溢出的问题。
尾递归优点：由于只存在一个调用栈，所以永远不会出现“栈溢出”错误，节省内存。

尾递归优化的斐波那契数列

非尾递归Fibonacci序列实现如下：

function Fibonacci(n) {
    if (n <= 1) {
        return 1;
    }
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}
for(let i=1; i<10; i++) {
console.log(i, Fibonacci(i));
}

尾递归优化的Fibonacci序列实现如下：

function Fibonacci(n, ac1 = 1, ac2 = 1) {
    if (n <= 1) {
        return ac2;
    }
    return Fibonacci(n - 1, ac2, ac1 + ac2);
}
for(let i=1; i<10; i++) {
console.log(i, Fibonacci(i));
}

function fb(num) {
var first = 1;
var second = 1;
var third;
if(num > 2){
for(var i = 0; i < num-2; i++){
third = first + second;
first = second;
second = third;
}
return third;
}
else{
return first;
}
}
for(let i=1; i<10; i++) {
console.log(i, fb(i));
}
/*
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
*/