递归、循环和迭代

今天在项目中遇到了无限循环和递归，我不经思考一个问题。所有的递归都能用循环实现吗？递归和循环有本质上的区别吗？？

function log () {
…
}

function loop () {
log();
loop();
}

for ( ; ; ) {
log();
}

上面这段代码看上去好象所有递归都可以用循环的方式实现，那么他们本质上是一样的吗？

首先看一下这几个概念的概念：

• 循环（loop），指的是在满足条件的情况下，重复执行同一段代码。比如，while语句。
• 迭代（iterate），指的是按照某种顺序逐个访问列表中的每一项。比如，for语句。
• 遍历（traversal），指的是按照一定的规则访问树形结构中的每个节点，而且每个节点都只访问一次。
• 递归（recursion），指的是一个函数不断调用自身的行为。比如，以编程方式输出著名的斐波纳契数列。

有了以上定义，这几个概念之间的区别其实就比较清楚了。至于它们之间的联系，严格来讲，它们似乎都属于算法的范畴。换句话说，它们只不过是解决问题的不同手段和方式，而本质上则都是计算机编程中达成特定目标的途径。 循环和递归最主要的区别就是效率上的区别，大家都知道递归比循环慢，那这是为什么呢？ 大家都知道递归的实现是通过调用函数本身，函数调用的时候，每次调用时要做地址保存，参数传递等，这是通过一个递归工作栈实现的。具体是每次调用函数本身要保存的内容包括：局部变量、形参、调用函数地址、返回值。那么，如果递归调用N次，就要分配N*局部变量、N*形参、N*调用函数地址、N*返回值。这势必是影响效率的。 递归与循环是两种不同的解决问题的典型思路。当然也并不是说循环效率就一定比递归高，递归和循环是两码事，递归带有栈操作，循环则不一定，两个概念不是一个层次，不同场景做不同的尝试。 递归其实是方便了程序员难为了机器。它只要得到数学公式就能很方便的写出程序。优点就是易理解，容易编程。但递归是用栈机制实现的，每深入一层，都要占去一块栈数据区域，对嵌套层数深的一些算法，递归会力不从心，空间上会以内存崩溃而告终，而且递归也带来了大量的函数调用，这也有许多额外的时间开销。所以在深度大时，它的时空性就不好了。 循环其缺点就是不容易理解，编写复杂问题时困难。优点是效率高。运行时间只因循环次数增加而增加，没什么额外开销。空间上没有什么增加。局部变量占用的内存是一次性的，也就是O(1)的空间复杂度，而对于递归（不考虑尾递归优化的情况），每次函数调用都要压栈，那么空间复杂度是O(n)，和递归次数呈线性关系。 递归程序改用循环实现的话，一般都是要自己维护一个栈的，以便状态的回溯。如果某个递归程序改用循环的时候根本就不需要维护栈，那其实这个递归程序这样写只是意义明显一些，不一定要写成递归形式。但很多递归程序就是为了利用函数自身在系统栈上的auto变量记录状态，以便回溯。