斐波那契数列的定义为它的第1页和第2页均为1以后各项为其前两项之和,设斐波那契第n项f（n）则有：n=1或n=2,f（n）=1 n>2,f（n）=f（n-1）+f（n-2）试写出求第n项f（n）的递归和非递归算法并分

斐波那契数列的定义为它的第1页和第2页均为1以后各项为其前两项之和,设斐波那契第n项f（n）则有：
n=1或n=2,f（n）=1 n>2,f（n）=f（n-1）+f（n-2）试写出求第n项f（n）的递归和非递归算法并分析它们的
时间复杂度及空间复杂度

递归很简单：描述如下
f（n）
if(n==1 || n==2)
return 1;
return f(n-1)+f(n-2);
非递归用循环就可以做到：
a=b=1;
for (i=3; i

dgs