漫谈递归:循环与迭代是一回事吗?

理清递归、迭代、循环的概念
服务器君一共花费了1001.410 ms进行了7次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

先摘抄“为之漫笔”对这几个概念的一段理解

loop、iterate、traversal和recursion这几个词是计算机技术书中经常会出现的几个词汇。众所周知,这几个词分别翻译为:循环、迭代、遍历和递归。乍一看,这几个词好像都与重复(repeat)有关,但有的又好像不完全是重复的意思。那么这几个词到底各是什么含义,有什么区别和联系呢?下面就试着解释一下。

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

有了以上定义,这几个概念之间的区别其实就比较清楚了。至于它们之间的联系,严格来讲,它们似乎都属于算法的范畴。换句话说,它们只不过是解决问题的不同手段和方式,而本质上则都是计算机编程中达成特定目标的途径。

迭代

迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。

利用迭代算法解决问题,需要做好以下三个方面的工作:

  1. 确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。
  2. 建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。
  3. 对迭代过程进行控制。在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。

可以用迭代的算法有很经典的问题,比如兔子产子问题:假定你有一雄一雌一对刚出生的兔子,它们在长到一个月大小时开始交配,在第二月结束时,雌兔子产下另一对兔子,过了一个月后它们也开始繁殖,如此这般持续下去。每只雌兔在开始繁殖时每月都产下一对兔子,假定没有兔子死亡,在一年后总共会有多少对兔子?

还有上楼梯的走法问题:有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?

这两个问题可以参看以前写的一篇文章:趣味算法之兔子产子问题

迭代与循环

先从字面上看:

  • 迭代:“迭”:轮流,轮番,替换,交替,更换。“代”:代替。所以迭代的意思是:变化的循环,这种变化就是轮番代替,轮流代替。
  • 循环:不变的重复。

个人认为迭代是循环的一种,循环体代码分为固定循环体,和变化的循环体。

固定的循环举例:

for($i=0; $i < 8; $i++){
	echo 'Welcome to NowaMagic';
}

实现迭代:

$sum = 0;

for($i = 1; $i <= 1000; $i++ ){
	$sum = $sum + i;
}

上面的迭代是常见的递增式迭代。类似的还有递减式迭代,递乘式迭代。

迭代的好处:迭代减少了冗余代码,提高了代码的利用率和动态性。

循环、迭代与递归

1. 递归算法与迭代算法的设计思路区别在于:函数或算法是否具备收敛性,当且仅当一个算法存在预期的收敛效果时,采用递归算法才是可行的,否则,就不能使用递归算法。

当然,从理论上说,所有的递归函数都可以转换为迭代函数,反之亦然,然而代价通常都是比较高的。但从算法结构来说,递归声明的结构并不总能够转换为迭代结构,原因在于结构的引申本身属于递归的概念,用迭代的方法在设计初期根本无法实现,这就像动多态的东西并不总是可以用静多态的方法实现一样。这也是为什么在结构设计时,通常采用递归的方式而不是采用迭代的方式的原因,一个极典型的例子类似于链表,使用递归定义及其简单,但对于内存定义(数组方式)其定义及调用处理说明就变得很晦涩,尤其是在遇到环链、图、网格等问题时,使用迭代方式从描述到实现上都变得很不现实。

2. 递归其实是方便了程序员难为了机器。它只要得到数学公式就能很方便的写出程序。优点就是易理解,容易编程。但递归是用栈机制实现的,每深入一层,都要占去一块栈数据区域,对嵌套层数深的一些算法,递归会力不从心,空间上会以内存崩溃而告终,而且递归也带来了大量的函数调用,这也有许多额外的时间开销。所以在深度大时,它的时空性就不好了。

循环其缺点就是不容易理解,编写复杂问题时困难。优点是效率高。运行时间只因循环次数增加而增加,没什么额外开销。空间上没有什么增加。

3. 局部变量占用的内存是一次性的,也就是O(1)的空间复杂度,而对于递归(不考虑尾递归优化的情况),每次函数调用都要压栈,那么空间复杂度是O(n),和递归次数呈线性关系。

4. 递归程序改用循环实现的话,一般都是要自己维护一个栈的,以便状态的回溯。如果某个递归程序改用循环的时候根本就不需要维护栈,那其实这个递归程序这样写只是意义明显一些,不一定要写成递归形式。但很多递归程序就是为了利用函数自身在系统栈上的auto变量记录状态,以便回溯。

原理上讲,所有递归都是可以消除的,代价就是可能自己要维护一个栈。而且我个人认为,很多情况下用递归还是必要的,它往往能把复杂问题分解成更为简单的步骤,而且很能反映问题的本质。

递归其实就是利用系统堆栈,实现函数自身调用,或者是相互调用的过程。在通往边界的过程中,都会把单步地址保存下来,知道等出边界,再按照先进后出的进行运算,这正如我们装木桶一样,每一次都只能把东西方在最上面,而取得时候,先放进取的反而最后取出。递归的数据传送也类似。但是递归不能无限的进行下去,必须在一定条件下停止自身调用,因此它的边界值应是明确的。就向我们装木桶一样,我们不能总是无限制的往里装,必须在一定的时候把东西取出来。比较简单的递归过程是阶乘函数,你可以去看一下。但是递归的运算方法,往往决定了它的效率很低,因为数据要不断的进栈出栈。

但是递归作为比较基础的算法,它的作用不能忽视。

纯粹个人见解,如有不同看法,欢迎联系我讨论。

延伸阅读

此文章所在专题列表如下:

  1. 漫谈递归:递归的思想
  2. 漫谈递归:递归需要满足的两个条件
  3. 漫谈递归:字符串回文现象的递归判断
  4. 漫谈递归:二分查找算法的递归实现
  5. 漫谈递归:递归的效率问题
  6. 漫谈递归:递归与循环
  7. 漫谈递归:循环与迭代是一回事吗?
  8. 递归计算过程与迭代计算过程
  9. 漫谈递归:从斐波那契开始了解尾递归
  10. 漫谈递归:尾递归与CPS
  11. 漫谈递归:补充一些Continuation的知识
  12. 漫谈递归:PHP里的尾递归及其优化
  13. 漫谈递归:从汇编看尾递归的优化

本文地址:http://www.nowamagic.net/librarys/veda/detail/2324,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2324

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《高性能JavaScript》 Nicholas C. Zakas (作者), 赵泽欣 (合著者), 丁琛 (译者)

《高性能JavaScript》揭示的技术和策略能帮助你在开发过程中消除性能瓶颈。你将会了解如何提升各方面的性能,包括代码的加载、运行、DOM 交互、页面生存周期等。雅虎的前端工程师 Nicholas C. Zakas 和其他五位 JavaScript 专家介绍了页面代码加载的最佳方法和编程技巧,来帮助你编写更为高效和快速的代码。你还会了解到构建和部署文件到生产环境的最佳实践,以及有助于定位线上问题的工具。如果你使用 JavaScript 构建交互丰富的 Web 应用,那么 JavaScript 代码可能是造成你的Web应用速度变慢的主要原因。

更多计算机宝库...