黑马程序员技术交流社区

标题: 递归与迭代的区别 [打印本页]
作者: touch_world    时间: 2014-11-9 07:23
标题: 递归与迭代的区别
  1. //以下以一个斐波那契数列的例子说明：

  3. //----------------------------------

  5. //1.迭代方法：

  7. public class Fab_iterate
  8. {
  9.     public static void main(String[] args)
  10.   {
  11.    System.out.println("结果是："+Fab(8));   //求第八个位置的数
  12.   }
  13.   public static long Fab(int index)   //斐波那契数列
  14.   {
  15.         if(index == 1 || index == 2)
  16.        {
  17.             return 1;
  18.        }
  19.       else
  20.       {
  21.            long f1 = 1L;
  22.            long f2 = 1L;
  23.            long f3 = 0;
  24.            for(int i = 0;i < index-2;i ++)  //迭代求值
  25.            {      
  26.             f3 = f1 + f2;
  27.                f1 = f2;
  28.                f2 = f3;
  29.             }
  30.            return f3;
  31.        }
  32.    }
  33. }


  36. //2.递归方法：

  38. public class Fab_recursion
  39. {
  40.    public static void main(String[] args)
  41.   {
  42.    System.out.println("结果是："+fab(8));    //求第八个位置的数
  43.   }
  44.    public static long fab(int index)    //斐波那契数列
  45.   {
  46.       if(index == 1 || index == 2)
  47.      {
  48.        return 1;
  49.       }
  50.      else
  51.      {
  52.        return fab(index-1)+fab(index-2);    //递归求值
  53.      }
  54.     }
  55. }
复制代码


所谓递归，简而言之就是应用程序自身调用自身，以实现层次数据结构的查询和访问。 递归的使用可以使代码更简洁清晰，可读性更好（对于初学者到不见得），但由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多，而且，如果递归深度太大，可能系统资源会不够用。      往往有这样的观点：能不用递归就不用递归，递归都可以用迭代来代替。      诚然，在理论上，递归和迭代在时间复杂度方面是等价的（在不考虑函数调用开销和函数调用产生的堆栈开销），但实际上递归确实效率比迭代低，既然这样，递归没有任何优势，那么是不是就，没有使用递归的必要了，那递归的存在有何意义呢？      万物的存在是需要时间的检验的，递归没有被历史所埋没，即有存在的理由。从理论上说，所有的递归函数都可以转换为迭代函数，反之亦然，然而代价通常都是比较高的。但从算法结构来说，递归声明的结构并不总能够转换为迭代结构，原因在于结构的引申本身属于递归的概念，用迭代的方法在设计初期根本无法实现，这就像动多态的东西并不总是可以用静多态的方法实现一样。这也是为什么在结构设计时，通常采用递归的方式而不是采用迭代的方式的原因，一个极典型的例子类似于链表，使用递归定义及其简单，但对于内存定义(数组方式)其定义及调用处理说明就变得很晦涩，尤其是在遇到环链、图、网格等问题时，使用迭代方式从描述到实现上都变得不现实。 因而可以从实际上说，所有的迭代可以转换为递归，但递归不一定可以转换为迭代。        采用递归算法需要的前提条件是，当且仅当一个存在预期的收敛时，才可采用递归算法，否则，就不能使用递归算法。      递归其实是方便了程序员难为了机器，递归可以通过数学公式很方便的转换为程序。其优点就是易理解，容易编程。但递归是用栈机制实现的，每深入一层，都要占去一块栈数据区域，对嵌套层数深的一些算法，递归会力不从心，空间上会以内存崩溃而告终，而且递归也带来了大量的函数调用，这也有许多额外的时间开销。所以在深度大时，它的时空性就不好了。      而迭代虽然效率高，运行时间只因循环次数增加而增加，没什么额外开销，空间上也没有什么增加，但缺点就是不容易理解，编写复杂问题时困难。      因而，“能不用递归就不用递归，递归都可以用迭代来代替”这样的理解，还是辩证的来看待，不可一棍子打死。
作者: Paul_Chang    时间: 2014-11-9 10:55
已学习...
作者: zhangyangLengen    时间: 2014-11-9 14:27
讲的不错
作者: greatcp3    时间: 2014-11-9 14:36
个人觉得，递归是由结果导向条件，迭代是由条件导向结果。
          新人第一次回帖，混眼熟，求带求照顾:)。
作者: likeermei    时间: 2014-11-9 16:49
我顶！！！！



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