# 第七章 迭代 这一章我们讲迭代，简单说就是指重复去运行一部分代码。在 5.8 的时候我们接触了一种迭代——递归。在 4.2 我们还学了另外一种迭代——for 循环。在本章，我们会见到新的迭代方式：whie 语句。但我要先再稍微讲一下变量赋值。 ## 7.1 再赋值 你可能已经发现了，对同一个变量可以多次进行赋值。一次新的赋值使得已有的变量获得新的值（也就不再有旧的值了。） >（译者注：这个其实中文很好理解，英文当中词汇逻辑关系比较紧密，但灵活程度不如中文高啊。） ```py >>> x = 5 >>> x 5 >>> x = 7 >>> x 7 ``` 第一次显示 x 的值，是 5，第二次，就是 7 了。 图 7.1 表示了再赋值的操作在状态图中的样子。 这里我就要强调一下大家常发生的误解。因为 Python 使用单等号（=）来赋值，所以有的人会以为像 a=b 这样的语句就如同数学上的表达一样来表达两者相等，这种想法是错误的！ 首先，数学上的等号所表示的相等是一个对称的关系，而 Python 中等号的赋值操作是不对称的。比如，在数学上，如果 a=7，那么 7=a。而在 Python，a=7 这个是合乎语法的，而 7=a 是错误的。 （译者注：这里就是说 Python 中等号是一种单向的运算，就是把等号右边的值赋给等号左边的变量，而 Python 中其实也有数学上相等判断的表达式，就是双等号（==），这个是有对称性的，就是说 a==b，那么 b==a，或者 a==3，3==a 也可以。） 另外在数学上，一个相等关系要么是真，要么是假。比如 a=b，那么 a 就会永远等于 b。在 Python 里面，赋值语句可以让两个变量相等，但可以不始终都相等，如下所示： ```py >>> a = 5 >>> b = a # a and b are now equal a 和 b 相等了 >>> a = 3 # a and b are no longer equal 现在 a 和 b 就不相等了 >>> b 5 ``` 第三行改变了 a 的值，但没有改变 b 的值，所以它们就不再相等了。 对变量进行再赋值总是很有用的，但你用的时候要做好备注和提示。如果变量的值频繁变化，就可能让代码难以阅读和调试。 ________________________________________  Figure 7.1: State diagram. ________________________________________ ## 7.2 更新变量 最常见的一种再赋值就是对变量进行更新，这种情况下新的值是在旧值基础上进行修改得到的。 ```py >>> x = x + 1 ``` 上面的语句的意思是：获取 x 当前的值，在此基础上加 1，然后把结果作为新值赋给 x。如果你对不存在的变量进行更新，你就会得到错误了，因为 Python 要先进行等号右边的运算，然后才能赋值给 x。 ```py >>> x = x + 1 NameError: name 'x' is not defined ``` 在你更新一个变量之前，你要先初始化一下，一般就是简单赋值一下就可以了： ```py >>> x = 0 >>> x = x + 1 ``` 对一个变量每次加 1 也可以叫做一种递增，每次减去 1 就可以叫做递减了。 ## 7.3 循环：While 语句 计算机经常被用来自动执行一些重复的任务。重复同样的或者相似的任务，而不出错，这是计算机特别擅长的事情，咱们人就做不到了。在一个计算机程序里面，重复操作也被叫做迭代。 我们已经见过两种使用了递归来进行迭代的函数：倒计时函数 countdown，以及 n 次输出函数 print_n。Python 还提供了一些功能来简化迭代，因为迭代用的很普遍。其中一个就是我们在 4.2 中见到的 for 循环语句。往后我们还要复习一下它。另外一个就是 while 循环语句。下面就是一个使用了 while 循环语句来实现的倒计时函数 countdown： ```py def countdown(n): while n > 0: print(n) n = n - 1 print('Blastoff!') ``` while 循环语句读起来很容易，几乎就像是英语一样简单。这个函数的意思是：当 n 大于 0，就输出 n 的值，然后对 n 减 1，到 n 等于 0 的时候，就输出单词『Blastoff』。 更正式一点，下面是一个 while 循环语句的执行流程： 1. 判断循环条件的真假。 2. 如果是假的，退出 while 语句，继续运行后面的语句。 3. 如果条件为真，执行循环体，然后再调回到第一步。 这种类型的运行流程叫做循环，因为第三步会循环到第一步。循环体内要改变一个或者更多变量的值，这样循环条件最终才能变成假，然后循环才能终止。 否则的话，条件不能为假，循环不能停止，这就叫做无限循环。计算机科学家有一个笑话，就是看到洗发液的说明：起泡，冲洗，重复；这就是一个无限循环。 在倒计时函数 countdown 里面，咱们能够保证有办法让循环终止：只要 n 小于等于 0 了，循环就不进行了。否则的话，n 每次就会通过循环来递减，最终还是能到 0 的。 其他一些循环就不那么好描述了。比如： ```py def sequence(n): while n != 1: print(n) if n % 2 == 0: # n is even n = n / 2 else: # n is odd n = n*3 + 1 ``` 这个循环的判断条件是 n 不等于 1，所以循环一直进行，直到 n 等于 1 了，条件为假，就不再循环了。 每次循环的时候，程序都输出 n 的值，然后检查一下是偶数还是奇数。如果是偶数，就把 n 除以 2。如果是奇数，就把 n 替换为 n 乘以 3 再加 1 的值。比如让这个函数用 3 做参数，也就是 sequence(3)，得到的 n 的值就依次为：3, 10, 5, 16, 8, 4, 2, 1. 有时候 n 在增加，有时候 n 在降低，所以没有明显证据表明 n 最终会到 1 而程序停止。对于一些特定的 n 值，我们能够确保循环的终止。例如如果起始值是一个 2 的倍数，n 每次循环过后依然是偶数，直到到达 1 位置。之前的例子都最终得到了一个数列，从 16 开始的就是了。 真正的难题是，我们能否证明这个程序对任意正数的 n 值都能终止循环。目前为止，没有人能够证明或者否定这个命题。 参考[维基百科](http://en.wikipedia.org/wiki/Collatz_conjecture) 做一个练习，把 5.8 里面的那个 n 次打印函数 print_n 用迭代的方法来实现。 ## 7.4 中断 有时候你不知道啥时候终止循环，可能正好在中间循环体的时候要终止了。这时候你就可以用 break 语句来跳出循环。 比如，假设你要让用户输入一些内容，当他们输入 done 的时候结束。你就可以用如下的方法实现： ```py while True: line = input('> ') if line == 'done': break print(line) print('Done!') ``` 循环条件就是 true，意味条件总是真的，所以循环就一直进行，一直到触发了 break 语句才跳出。 每次循环的时候，程序都会有一个大于号>来提示用户。如果用输入了 done，break 语句就会让程序跳出循环。否则的话程序会重复用户输入的内容，然后回到循环的头部。下面就是一个简单的运行例子： ```py >>>not done >>>not done >>>done Done! ``` 这种 while 循环的写法很常见，因为这样你可以在循环的任何一个部位对条件进行检测，而不仅仅是循环的头部，你可以确定地表达循环停止的条件（在这种情况下就停止了），而不是消极地暗示『程序会一直运行，直到某种情况』。 ## 7.5 平方根 循环经常被用于进行数值运算的程序中，这种程序往往是有一个近似值作为初始值，然后逐渐迭代去改进以接近真实值。 比如，可以用牛顿法来计算平方根。加入你要知道一个数 a 的平方根。如果你用任意一个估计值 x 来开始，你可以用下面的公式获得一个更接近的值： $$y = \frac{x + \frac{a}{x}}{2}$$ 比如，如果 a 是 3，x 设为 3： ```py >>> a = 4 >>> x = 3 >>> y = (x + a/x) / 2 >>> y 2.16666666667 ``` 得到的结果比初始值 3 更接近真实值（4 的平方根是 2）。如果我们用这个结果做新的估计值来重复这个操作，结果就更加接近了： ```py >>> x = y >>> y = (x + a/x) / 2 >>> y 2.00641025641 ``` 这样进行一些次重复之后，估计值就几乎很准确了： ```py >>> x = y >>> y = (x + a/x) / 2 >>> y 2.00001024003 >>> x = y >>> y = (x + a/x) / 2 >>> y 2.00000000003 ``` 一般情况下，我们不能提前知道到达正确结果需要多长时间，但是当估计值不再有明显变化的时候我们就知道了： ```py >>> x = y >>> y = (x + a/x) / 2 >>> y 2.0 ``` 当 y 和 x 相等的时候，我们就可以停止了。下面这个循环中，用一个初始值 x 来开始循环，然后进行改进，一直到 x 的值不再变化为止： ```py while True: print(x) y = (x + a/x) / 2 if y == x: break x = y ``` 对大多数值来说，这个循环都挺管用的，但一般来说用浮点数来测试等式是很危险的。浮点数的值只能是近似正确：大多数的有理数，比如 1/3，以及无理数，比如根号 2，都不能用浮点数来准确表达的。 相比之下，与其对比 x 和 y 是否精确相等，倒不如以下方法更安全：用内置的绝对值函数来计算一下差值的绝对值，也叫做数量级。 ```py if abs(y-x) < epsilon: break ``` 这里可以让 epsilon 的值为 like 0.0000001，差值比这个小就说明已经足够接近了。 ## 7.6 算法 牛顿法是算法的一个例子：通过一系列机械的步骤来解决一类问题（在本章中是用来计算平方根）。 要理解算法是什么，先从一些不是算法的内容来开始也许会有所帮助。当你学个位数字乘法的时候，你可能要背下来整个乘法表。实际上你记住了 100 个特定的算式。这种知识就不是算法。 但如果你很『懒』，你就可能会有一些小技巧。比如找到一个 n 与 9 的成绩，你可以把 n-1 写成第一位，10-n 携程第二位。这个技巧是应对任何个位数字乘以 9 的算式。这就是一个算法了！ 类似地，你学过的进位的加法，借位的减法，以及长除法，都是算法。这些算法的一个共同特点就是不需要任何智力就能进行。它们都是机械的过程，每一步都跟随上一步，遵循着很简单的一套规则。 执行算法是很无聊的，但设计算法很有趣，是智力上的一种挑战，也是计算机科学的核心部分。 有的事情人们平时做起来很简单，甚至都不用思考，这些事情往往最难用算法来表达。比如理解自然语言就是个例子。我们都能理解自然语言，但目前为止还没有人能解释我们到底是怎么做到的，至少没有人把这个过程归纳出算法的形式。 ## 7.7 调试 现在你已经开始写一些比较大的程序了，你可能发现自己比原来花更多时间来调试了。代码越多，也就意味着出错的可能也越大了，bug 也有了更多的藏身之处了。 『对折调试』是一种节省调试时间的方法。比如，如果你的程序有 100 行，你检查一遍就要大概 100 步了。而对折方法就是把程序分成两半。看程序中间位置，或者靠近中间位置的，检查一些中间值。在这些位置添加一些 print 语句（或者其他能够能起到验证效果的东西），然后运行程序。 如果中间点检查出错了，那必然是程序的前半部分有问题。如果中间点没调试，那问题就是在后半段了。 每次你都这样检查，你就让你要检查的代码数量减半了。一般六步之后（远小于 100 次了），理论上你就差不多已经到代码的末尾一两行了。 在实际操作当中，程序中间位置并不是总那么明确，也未必就很容易去检查。所以不用数行数来找确定的中间点。相反的，只要考虑一下程序中哪些地方容易调试，然后哪些地方进行检验比较容易就行了。然后你就在你考虑好的位置检验一下看看 bug 是在那个位置之前还是之后。 ## 7.8 Glossary 术语列表 reassignment: Assigning a new value to a variable that already exists. >再赋值：对一个已经存在的有值变量赋予一个新的值。 update: An assignment where the new value of the variable depends on the old. >更新：根据一个变量的旧值，进行一定的修改，再赋值给这个变量。 initialization: An assignment that gives an initial value to a variable that will be updated. >初始化：给一个变量初始值，以便于后续进行更新。 increment: An update that increases the value of a variable (often by one). >递增：每次给一个变量增加一定的值（一般是加 1） decrement: An update that decreases the value of a variable. >递减：每次给一个变量减去一定的值。 iteration: Repeated execution of a set of statements using either a recursive function call or a loop. >迭代：重复执行一系列语句，使用递归函数调用的方式，或者循环的方式。 infinite loop: A loop in which the terminating condition is never satisfied. >无限循环：终止条件永远无法满足的循环。 algorithm: A general process for solving a category of problems. >算法：解决某一类问题的一系列通用的步骤。 ## 7.9 练习 ### 练习 1 从 7.5 复制一个循环，然后改写成名字叫做 mysqrt 的函数，该函数用一个 a 作为参数，选择一个适当的起始值 x，然后返回 a 的平方根的近似值。 测试这个函数，写一个叫做 test_suqare_root 的函数来输出以下这样的表格：  第一列是数 a；第二列是咱们自己写的函数 mysqrt 计算出来的平方根，第三行是用 Python 内置的 math.sqrt 函数计算的平方根，最后一行是这两者的差值的绝对值。 ### 练习 2 Python 的内置函数 eval 接收字符串作为参数，然后用 Python 的解释器来运行。例如： ```py >>> eval('1 + 2 * 3') 7 >>> import math >>> eval('math.sqrt(5)') 2.2360679774997898 >>> eval('type(math.pi)') <class 'float'> ``` 写一个叫做 eval_loop 的函数，交互地提醒用户，获取输入，然后用 eval 对输入进行运算，把结果打印出来。 这个程序要一直运行，直到用户输入『done』才停止，然后输出最后一次计算的表达式的值。 ## 练习 3 传奇的数学家拉马努金发现了一个无穷级数（1914 年的论文），能够用来计算圆周率倒数的近似值：  （译者注：这位拉马努金是一位非常杰出的数学家，自学成才，以数论为主要研究内容，可惜 33 岁的时候就英年早逝。他被哈代誉为超越希尔伯特的天才。） 写一个名叫 estimate_pi 的函数，用上面这个方程来计算并返回一个圆周率π的近似值。要使用一个 while 循环来计算出总和的每一位，最后一位要小于 10 的-15 次方。你可以对比一下计算结果和 Python 内置的 math.pi。 >[样例代码](http://thinkpython2.com/code/pi.py)