递归和迭代的区别

所谓递归，简而言之就是应用程序自己调用自己来实现对层次数据结构的查询和访问。递归的使用可以让代码更加简洁易读(对于初学者来说不一定)，但是由于递归需要系统堆栈，所以空间消耗比非递归代码大很多，如果递归深度过大，可能会导致系统资源不足。

经常有这样一种观点，认为递归是可以避免的，递归可以用迭代来代替。

诚然，理论上递归和迭代在时间复杂度上是等价的(不考虑函数调用开销和函数调用产生的栈开销)，但实际上递归确实不如迭代高效。在这种情况下，递归没有任何优势，所以没有必要使用递归，递归的意义何在？万物的存在都需要时间来检验。递归不是被历史埋没的，就是有它存在的理由。

理论上所有的递归函数都可以转化为迭代函数，反之亦然，但是成本通常比较高。但在算法结构上，递归声明的结构并不总是能转化为迭代结构，因为结构本身的扩展属于递归概念，在设计初期无法通过迭代的方法实现，就像动态多态并不总是能通过静态多态实现一样。

这也是结构设计中通常采用递归法而不是迭代法的原因。一个典型的例子类似于链表，使用递归定义，非常简单，但是它对内存定义(数组方法)的定义和调用处理指令变得非常晦涩，特别是遇到环链、图、网格等问题时，从描述到实现都使用迭代的方法变得不现实。所以实际来说，所有的迭代都可以转化为递归，但是递归不一定能转化为迭代。

采用递归算法的前提条件是，只有当且仅当一个人具有期望的收敛性时，才能采用递归算法，否则，递归算法就不能使用。

递归对于程序员来说其实是很方便的，递归可以很容易的通过数学公式转换成程序。其优点是易于理解和编程。而递归是通过堆栈机制实现的，每深入一步就要占用一个堆栈数据区。对于一些嵌套层比较深的算法，递归会不够用，空间会以内存崩溃告终，递归也会带来大量的函数调用，也有很多额外的时间开销。所以深度大了，它的时空就不好了。

虽然迭代是高效的，只是通过增加循环次数来增加运行时间，没有额外的开销，也没有增加空间，但是缺点是不容易理解，很难写出复杂的问题。

所以“递归可以避免，递归可以用迭代代替”的理解还是辩证的，不能一棍子打死。