菲波那契数列：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年我写的一篇旧文
