怎么把递归改成循环

就是这个Fib什么单词我忘记了  数列是这样的 1  1  3  4  7  11  18  29  ....
本来是用的递归f(n-1)+ f(n-2)    ,

我前天去面试的时候，题目要求先递归然后改成循环，我想了很久没想明白，脑子进水了

while  和for

18 个解决方案

#1

递归都有3个条件，你找出开始条件，再找到终止的条件，还有累计条件，不就成了循环结构了嘛！
希望帮到你！

#2

我终于弄出来了 先前真是脑子进水了

public static int fib(int n){
		int f[] =new int[10];
		for(int i=1;i<=n;i++){
			if(i==1 || i==2){
				f[i]=1;
			}
			else{
				f[i]=f[i-1]+f[i-2];
			}
		}
		return f[n];
	}

#3

呵呵，斐波拉契数列

#4

	public static int fibw(int n){
		int i=1;
		int f[] =new int [n+1];
		while (i<=n){
			if(i==1 || i==2){
				f[i]=1;
			}
			else{
				f[i]=f[i-1]+f[i-2];
			}
			i++;
		}
		return f[n];
	}

#5

路过

#6

能用循环替代的递归不是好递归 

#7

/**
 * dinghun8leech
 * @param args
 */
public static void main(String [] args) {
		int count = 10;//这里填写所需输出的斐波拉契数列的长度
		int [] fibonacci = new int[count];
		for (int i=0;i<count;i++) {
			if (i < 2) {
				fibonacci[i] = 1;
			} else {
				fibonacci[i] = fibonacci[i-2] + fibonacci[i-1];
			}
		}
		System.out.println(java.util.Arrays.toString(fibonacci));
	}

这个么？？

#8

等下，6楼的意思是？？？不明白，能解释下么？

#9

引用 8 楼 dinghun8leech 的回复:

等下，6楼的意思是？？？不明白，能解释下么？

递归很耗性能，能不用就不用，

#10

帅！

#11

用数组来做啊
s=0;//和
 for (i=1;i<n;i++){
if(i<2){
 a[i]=1;
 }
if(i==2){
a[i]=3;
}
if(i>2){
a[i]=a[i-1]+a[i-2];
}
s+=a[i];
}
while循环
int i=1;
while(i<n){
if(i<2){
 a[i]=1;
 }
if(i==2){
a[i]=3;
}
if(i>2){
a[i]=a[i-1]+a[i-2];
}
s+=a[i];
i++;
}

#12

呵呵，睡了一觉，再回来一看已经到了11楼了

#13

循环的效率高呀！

#14

不知道大家注意没有啊,第三项是3哦;所以递归要从第三项开始:
static int[] fib(int n){
int[] f = new int[n];
for( int i=0;i<f.length;i++){
if(i==0||i==1){
f[i]=1;
}else if(i==2){
f[i]=3;
}else{
f[i]=f[i-1]+f[i-2];
}
}
return f;
}

#15

实际上递归差不多都能改造成循环 用栈的话就能实现(BUT数据结构讲那一段的地方我没看)

#16

请教下传说中的15楼，可以被改成循环的递归确实如9楼说的那样性能糟糕么？为什么？

#17

引用 16 楼 dinghun8leech 的回复:

请教下传说中的15楼，可以被改成循环的递归确实如9楼说的那样性能糟糕么？为什么？

递归方法的特别之处在于他是调用自身进行循环 这能做到一些其他方式做不到的事情 但是跟循环比的话会有一些额外开销。控制必须从这个调用位置转移到方法开始处。而且还要在栈中保存这个方法的参数以及返回地址为的是这个方法可以访问参数值和知道返回到哪里。而且系统内存空间存储的中间参数以及返回值,如果有大量的数据需要存储,就会引起栈溢出。
采取递归的原因是因为它从概念上简化了问题,而不是因为它更有效率

------Java数据结构和算法中文第二版

我有地方也看不懂 不过你可以尝试下 递归不是效率糟糕 问题是怎么用 为什么用 他能做到普通循环做不到的事情 这是用他的原因 但是需要耗费资源（但绝对值得）

#18

多谢楼上的解答！！！！！！！