黑马程序员技术交流社区

标题: 关于递归和循环的效率 [打印本页]

---

作者: 何明辉    时间: 2012-8-13 23:00
标题: 关于递归和循环的效率
class DiGui
{
    public static void main(String[] args)
{
  int n=100;
     int sum=0;
  for(int i=1;i<=n;i++)
  {
   sum=sum+i;
  }
  System.out.println(sum);
  System.out.println(sum1(n));
    }
static int sum1(int n)
{
  if(n==1)
   return 1;
  else
    return n+sum1(n-1);
}
}
上面程序中分别用递归和循环实现1到100的求和，循环和递归的那个效率会更高一些，我感觉貌似循环的效率高些，因为每次递归还要开辟新栈来运算。
那什么样的情况下递归会高于循环

---

作者: 黄珊珊    时间: 2012-8-13 23:15


做上面那个求1到100的和的算法用循环当然要比递归快了。
但循环的效率不一定就比递归高。循环和递归是两种不同的思路。

一般递归比较慢是因为要调用函数本身，调用时要做地址保存、参数传递等，这些是通过递归工作栈实现的。每次调用函数本身要保存的内容包括：局部变量、形参、调用函数地址、返回值。那么，如果递归调用n次，就要分配n*局部变量、n*形参、n*调用函数地址、n*返回值。这当然会影响效率。

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

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

---

作者: 于启会    时间: 2012-8-14 00:06
1.求n!时,n!=n*(n-1)!,而(n-1)!=(n-1)*(n-2),依此类推,直到1!=1为止,就是个递归问题.
2.一个循环如:while(a<0){……}.
递归和循环有些相似的地方，递归问题都可以用循环来代替，但是在程序的篇幅上和复杂程序上就有一定增加了递归和循环一样都是需要一个口停止这个“循环”的过程。递归在事先不知道第一个值得时候用，进而一步一步推出要输出的值，而循环式用重复的方法一个个往下执行，一个个得出值，是顺序得出，递归是倒序得出。

一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
注意：
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。

递归算法一般用于解决三类问题：
(1)数据的定义是按递归定义的。(Fibonacci函数)
(2)问题解法按递归算法实现。(回溯)
(3)数据的结构形式是按递归定义的。(树的遍历，图的搜索)

---

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

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