菲波那契数列

菲波那契数列：1,1,2,3,5,8,13,21,34,55,89,144,...
求第n个斐波那契数列
JavaScript版：

function fib(n){
            if(n==1||n==2){
                return 1;
            }
            else{
                return fib(n-2)+fib(n-1);
            }
        }

C#版：

int fib(int n)
{
  if(n==1||n==2)
  {
    return 1;
  }
  return fib(n-2)+fib(n-1);
}

都是使用的递归方法进行计算的，每次使用递归的时候都要记住一句话：

任何递归都可以用迭代进行替换

其实就是以牺牲空间效率为代价换取更高的时间效率。
迭代实现：
JavaScript版

function f(n){
            if(n==1||n==2){
                return 1;
            }
            else{
                var pre_pre_result=1;
                var pre_result=1;
                var result=0;
                for(var i=0;i<n-2;i++){
                    result=pre_pre_result+pre_result;
                    pre_pre_result=pre_result;
                    pre_result=result;
                }
                return result;
            }
        }

C#版类似，就不赘述了。

话说，求杨辉三角第n行第m列的数也用到了递归，可是我不知道要怎么改成迭代，求高手指点一二。

另，2015年我写的一篇旧文