斐波那契数列解决上台阶的问题

斐波那契数列（Fibonacci sequence）因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。

数列的特征：第1项是0，第2项是第一个1，从第3项开始，每一项都等于前两项之和。

1、基本的斐波那契数列

function getNthFibonacci(count) {
    if(count==0||count==1) return 1;
    return getNthFibonacci(count-2)+getNthFibonacci(count-1);
}    //递归实现，但是当count值特别大的时候不建议使用递归

　　迭代实现的代码如下：

function getNthFibonacci(count) {
    if(count<0) return 0;
    if(count<=1) return 1;
    var first = 1;
    var second = 1;
    var third = 0;
    for(var i = 2; i <= count; i++) {
        third = first + second;
        first = second;
        second = third;
    }
    return third;
}

　　补：这里解释一下递归和迭代的区别，在知乎上找到的一种解释，很清晰明确。

迭代是逐渐逼近，用新值覆盖旧值，直到满足条件后结束，不保存中间值，空间利用率高。

递归是将一个问题分解为若干相对小一点的问题，遇到递归出口再原路返回，因此必须保存相关的中间值，这些中间值压入栈保存，问题规模较大时会占用大量内存。

 

2、斐波那契数列变形应用——题目描述：

有一楼梯共n级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第n级，共有多少走法？

注：规定从一级到一级有0种走法。

function taijie(n){

        var arr=[];
        arr[0]=0;
        arr[1]=0;
        arr[2]=1;
        arr[3]=2;
        for(var i=4;i<=n;i++)
        {
            arr[i] =arr[i-1]+arr[i-2];
        }
        return arr[n];
    }