黑马程序员技术交流社区

标题: java题--所有的递归实现都可以用循环的方式实现，请描述... [打印本页]

作者: suihs11 时间: 2015-3-11 22:17
标题: java题--所有的递归实现都可以用循环的方式实现，请描述...
本帖最后由 suihs11 于 2015-3-11 22:56 编辑

求解答...所有的递归实现都可以用循环的方式实现？请描述一下这两种实现方式各自的优劣。并举例说明在什么情况下可以使用递归，而在什么情况下只能使用循环而不能使用递归？

作者: tianlin 时间: 2015-3-11 22:17
RE：
递归算法：
优点：代码简洁、清晰，并且容易验证正确性
缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，那将是极端难看的代码。

循环算法：
优点：速度快，结构简单。
缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。

总结：
1. 一般递归调用可以处理的算法，也通过循环去解决常需要额外的低效处理。
2. 现在的编译器在优化后，对于多次调用的函数处理会有非常好的效率优化，效率未必低于循环。
3.递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环替换，而不影响程序的阅读，那么替换成递归往往是好的。（例如：求阶乘的递归实现与循环实现。）

作者: FFleo 时间: 2015-3-11 22:39
没有绝对的答案，使用递归还是循环根据情况而定。

递归的实现最大的优势是简单，但是函数递归调用可能会很深，每多一层递归都会多一些栈空间，当然会占用更多内存。
循环的实现相对递归最大的优势是节省内存，但是实现可能会复杂好几倍。

作者: Mr.南郭 时间: 2015-3-12 10:09
就以计算阶乘为例来说循环和递归吧。
功能：实现n的阶乘。
-------------------------------------------------------------------------
循环：
class Circulate
{
private static int circulate (int n)
{
int circulate = n;
while (n>0)
{
System.out.println(n);
circulate *=n;
n--;
}
return circulate;
}

public static void main (String [] args)
{
// 计算10的阶乘
System.out.println(circulate(10));
}
}
---------------------------------------------------------------------------
递归简单来说就是指函数在运行过程中不断的调用自己的一种现象。如下：
class Recursion
{
private static int n;
private static int recursion = 1;
private static int recursion ( int n)
{
if (n>0)
{
System.out.println(n);
recursion *=n;
n--;
// 调用自身
recursion(n);
}
return recursion;
}
public static void main (String [] args)
{
// 计算10的阶乘
System.out.println(recursion(10));
}
}
结论：递归结构可读性差，使用较少。循环效率高，可靠性好。故一般情况下用循环代替递归。

作者: zooooolk 时间: 2015-3-12 10:12
看情况吧

作者: 罗晓飞 时间: 2015-3-12 10:59
如果方法比较多的话，建议用循环，比如想重复这个方法，用
boolean  flag=true;
do{
   重复的的类容

if(判断一下是否要循环){
      flag=false;
}

}while(flag);

用这种方式比递归要好的很多。。。。。。。。

作者: 路文龙 时间: 2015-3-12 15:53
递归占的内存多，一层一层的叠加，循环就相对少一点，但是用循环就麻烦了，就像二叉树的遍历，递归用的代码行数少，但是运行麻烦，循环用的代码复杂但是运行简单

作者: 林吉前 时间: 2015-3-12 20:00
递归耗资源，如果用循环麻烦，用递归简单，就用呗

作者: 右手年华 时间: 2015-3-12 20:47
话说递归层次比较深的话容易造成stack overflow,还被认为效率不高，而且有人表示所有的递归都可以改写成循环，这是真的吗？

林锐博士的书中曾表示：所有的递归都可以改写成循环，而且认为递归的效率不高。
而王垠博士则认为递归比循环强。
“递归的数据总是需要递归的程序来处理。虽然递归有时候表现为另外的形式，比如循环(loop)，但是“递归”这个概念比“循环”更广泛一些。有很多递归程序不能用循环来表达”
http://blog.sina.com.cn/s/blog_5d90e82f01018ge9.html

“而其实递归比循环表达能力强很多，而且效率几乎一样。有些程序比如解释器，不用递归的话基本没法完成。”
http://blog.sina.com.cn/s/blog_5d90e82f01015271.html
王垠写解释器可是很在行的啊，对循环，递归的理解也应该不错吧。

作者: Sou男人 时间: 2015-3-12 20:57
递归耗资源，如果用循环麻烦，用递归简单，用呗

作者: 呐拽 时间: 2015-3-24 21:43
我是进来学习一下的

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2