不好意思，在这里占一楼抱怨一句！
刚刚接触数据结构与算法，所以请有一些动不动就装13骂人的就不要来了！

额,楼上的意思是?

不就是Fibonacci吗

int a=1, b=1, c=1;
for(int i=2; i<=n; i++)
{
  c=a+b;
  a=b;
  b=c;
}
return c;

long int
Fib(int n)
{
int a=1,b=1;
int ret = 0;
    if (n <= 1)
        return 1;
for (int i=1; i<n; i++)
{
ret = a + b;
a = b;
b = ret;
}
return ret;
}

将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。 
前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论 
这两种方法。 
　　1. 直接转换法 
　　直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。 
　　尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法： 
　　long fact(int n) 
　　{ 
　　if (n==0) return 1; 
　　else return n*fact(n-1); 
　　} 
　　当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以 
，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法 
可以写成如下循环结构的非递归算法： 
　　long fact(int n) 
　　{ 
　　int s=0; 
　　for (int i=1; i 
　　s=s*i; //用s保存中间结果 
　　return s; 
　　} 
　　单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归 
调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下： 
　　int f(int n) 
　　{ 
page: 2 
The Home of jetmambo - 递归算法转换为非递归算法 
　　if (n= =1 | | n= =0) return 1; 
　　else return f(n-1)+f(n-2); 
　　} 
　　对于单向递归，可以设置一些变量保存中间结构，将递归结构用循环结构来替代。例如求斐波那契数列的算 
法中用s1和s2保存中间的计算结果，非递归函数如下： 
　　int f(int n) 
　　{ 
　　int i, s; 
　　int s1=1, s2=1; 
　　for (i=3; i { 
　　s=s1+s2; 
　　s2=s1; // 保存f(n-2)的值 
　　s1=s; //保存f(n-1)的值 
　　} 
　　return s; 
　　} 
　　2. 间接转换法 
　　该方法使用栈保存中间结果，一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下： 
　　将初始状态s0进栈 
　　while (栈不为空) 
　　{ 
　　退栈，将栈顶元素赋给s; 
　　if (s是要找的结果) 返回; 
　　else { 
　　寻找到s的相关状态s1; 
　　将s1进栈 
　　} 
　　} 
　　间接转换法在数据结构中有较多实例，如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实 现等等，请读者参考主教材中相关内容。 


你这里的递归只需用到 直接转换法  ，同时保存一下中间临时变量即可。

先写为尾递归的形式，FP编程常用，尾递归其实就是可以转为递推的

typedef long long int64;

int64 fib(int64 n,int64 a=0,int64 b=1) {

	if (n==0) return a;

	return fib(n-1,b,a+b);

}

现在转为递推不用说了吧，下面来看一段log(n)的算法，执行1000次就可以看出效率差别

int64 fibonacci(int64 n) {

	int64 ra,rb,a,b,x,y;

	if (n<2) return n;

	ra=rb=a=b=1;

	n-=2;

	while (n) {

		if (n&1) {

			x=ra*a+rb*b;

			y=ra*b+rb*(a-b);

			ra=x;rb=y;

		}

		n>>=1;

		x=a*a+b*b;

		y=2*a*b-b*b;

		a=x;b=y;

	}

	return ra;

}

另外，我的fibonacci数列是从0开始的 0 1 1 2 3 ...

引用 6 楼 budtang 的回复:

将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。 
前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论 
这两种方法。 
　　1. 直接转换法 
　　直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。 
　　尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后……

ok

这个就是那个非那波契数列
递归效果不高，用循环，

for(i++;i<t)//t是循环次数，自己设
{
n2=n0+n1
//每个循环都是往后移动一位
//于是
n0=n1;n1=n2;n2=array[i+1];
}

要效率，请看7楼第二段代码

引用 9 楼 zzz9413 的回复:

这个就是那个非那波契数列
递归效果不高，用循环，

for(i++;i<t)//t是循环次数，自己设
{
n2=n0+n1
//每个循环都是往后移动一位
//于是
n0=n1;n1=n2;n2=array[i+1];
}

moonck同michael122的解决了实际方案，
budTang提供了很好的思路，
fanster28_的方法是对本例的几种方法中最效率的了！（还在深入理解中）只微测试了下，N = 30，这种方法就比moonck的快了0。5倍(log(N)就是不同呀,比moonck的O(N)效率高很多)。
呵，以前走入了误区，想用一个起始为N的递减循环来解决！如果这样，应该是无解的吧！
 

这么小看不出差别，计算N＝10000看看
当然这要溢出，对每个结果都按mod 100007(任取)取结果，你就可以看出差别了

引用 11 楼 gkathere 的回复:

moonck同michael122的解决了实际方案，
budTang提供了很好的思路，
fanster28_的方法是对本例的几种方法中最效率的了！（还在深入理解中）只微测试了下，N = 30，这种方法就比moonck的快了0。5倍(log(N)就是不同呀,比moonck的O(N)效率高很多)。
呵，以前走入了误区，想用一个起始为N的递减循环来解决！如果这样，应该是无解的吧！

引用 7 楼 fanster28_ 的回复:

先写为尾递归的形式，FP编程常用，尾递归其实就是可以转为递推的
C/C++ code
typedef long long int64;
int64 fib(int64 n,int64 a=0,int64 b=1) {
    if (n==0) return a;
    return fib(n-1,b,a+b);
}

现在转为递推不用说了吧，下面来看一段log(n)的算法，执……

不明白~~mark~有空再慢慢研究

高手如云啊！

mark & tune