第七章 迭代

这一章我们讲迭代，简单说就是指重复去运行一部分代码。在5.8的时候我们接触了一种迭代——递归。在4.2我们还学了另外一种迭代——for循环。在本章，我们会见到新的迭代方式：whie语句。但我要先再稍微讲一下变量赋值。

7.1 再赋值

你可能已经发现了，对同一个变量可以多次进行赋值。一次新的赋值使得已有的变量获得新的值（也就不再有旧的值了。）

（译者注：这个其实中文很好理解，英文当中词汇逻辑关系比较紧密，但灵活程度不如中文高啊。）

  1. >>> x = 5
  2. >>> x
  3. 5
  4. >>> x = 7
  5. >>> x
  6. 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里面，赋值语句可以让两个变量相等，但可以不始终都相等，如下所示：

  1. >>> a = 5
  2. >>> b = a    # a and b are now equal a和b相等了
  3. >>> a = 3    # a and b are no longer equal 现在a和b就不相等了
  4. >>> b
  5. 5

第三行改变了a的值，但没有改变b的值，所以它们就不再相等了。

对变量进行再赋值总是很有用的，但你用的时候要做好备注和提示。如果变量的值频繁变化，就可能让代码难以阅读和调试。

Figure 7.1: State diagram. Figure 7.1: State diagram.

7.2 更新变量

最常见的一种再赋值就是对变量进行更新，这种情况下新的值是在旧值基础上进行修改得到的。

  1. >>> x = x + 1

上面的语句的意思是：获取x当前的值，在此基础上加1，然后把结果作为新值赋给x。如果你对不存在的变量进行更新，你就会得到错误了，因为Python要先进行等号右边的运算，然后才能赋值给x。

  1. >>> x = x + 1
  2. NameError: name 'x' is not defined

在你更新一个变量之前，你要先初始化一下，一般就是简单赋值一下就可以了：

  1. >>> x = 0
  2. >>> x = x + 1

对一个变量每次加1也可以叫做一种递增，每次减去1就可以叫做递减了。

7.3 循环：While语句

计算机经常被用来自动执行一些重复的任务。重复同样的或者相似的任务，而不出错，这是计算机特别擅长的事情，咱们人就做不到了。在一个计算机程序里面，重复操作也被叫做迭代。

我们已经见过两种使用了递归来进行迭代的函数：倒计时函数countdown，以及n次输出函数print_n。Python还提供了一些功能来简化迭代，因为迭代用的很普遍。其中一个就是我们在4.2中见到的for循环语句。往后我们还要复习一下它。另外一个就是while循环语句。下面就是一个使用了while循环语句来实现的倒计时函数countdown：

  1. def countdown(n):
  2.     while n > 0:
  3.         print(n)
  4.         n = n - 1
  5.     print('Blastoff!')

while循环语句读起来很容易，几乎就像是英语一样简单。这个函数的意思是：当n大于0，就输出n的值，然后对n减1，到n等于0的时候，就输出单词『Blastoff』。

更正式一点，下面是一个while循环语句的执行流程：

  1. 判断循环条件的真假。

  2. 如果是假的，退出while语句，继续运行后面的语句。

  3. 如果条件为真，执行循环体，然后再调回到第一步。

这种类型的运行流程叫做循环，因为第三步会循环到第一步。循环体内要改变一个或者更多变量的值，这样循环条件最终才能变成假，然后循环才能终止。

否则的话，条件不能为假，循环不能停止，这就叫做无限循环。计算机科学家有一个笑话，就是看到洗发液的说明：起泡，冲洗，重复；这就是一个无限循环。

在倒计时函数countdown里面，咱们能够保证有办法让循环终止：只要n小于等于0了，循环就不进行了。否则的话，n每次就会通过循环来递减，最终还是能到0的。

其他一些循环就不那么好描述了。比如：

  1. def sequence(n):
  2.     while n != 1:
  3.         print(n)
  4.         if n % 2 == 0:            # n is even
  5.             n = n / 2
  6.         else:                    # n is odd
  7.             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值都能终止循环。目前为止，没有人能够证明或者否定这个命题。

参考维基百科 做一个练习，把5.8里面的那个n次打印函数print_n用迭代的方法来实现。

7.4 中断

有时候你不知道啥时候终止循环，可能正好在中间循环体的时候要终止了。这时候你就可以用break语句来跳出循环。 比如，假设你要让用户输入一些内容，当他们输入done的时候结束。你就可以用如下的方法实现：

  1. while True:
  2.     line = input('> ')
  3.     if line == 'done':
  4.         break
  5.         print(line)
  6.     print('Done!')

循环条件就是true，意味条件总是真的，所以循环就一直进行，一直到触发了break语句才跳出。

每次循环的时候，程序都会有一个大于号>来提示用户。如果用输入了done，break语句就会让程序跳出循环。否则的话程序会重复用户输入的内容，然后回到循环的头部。下面就是一个简单的运行例子：

  1. >>>not done
  2. >>>not done
  3. >>>done
  4. Done!

这种while循环的写法很常见，因为这样你可以在循环的任何一个部位对条件进行检测，而不仅仅是循环的头部，你可以确定地表达循环停止的条件（在这种情况下就停止了），而不是消极地暗示『程序会一直运行，直到某种情况』。

7.5 平方根

循环经常被用于进行数值运算的程序中，这种程序往往是有一个近似值作为初始值，然后逐渐迭代去改进以接近真实值。

比如，可以用牛顿法来计算平方根。加入你要知道一个数a的平方根。如果你用任意一个估计值x来开始，你可以用下面的公式获得一个更接近的值：

y = \frac{x + \frac{a}{x}}{2}

比如，如果a是3，x设为3：

  1. >>> a = 4
  2. >>> x = 3
  3. >>> y = (x + a/x) / 2
  4. >>> y
  5. 2.16666666667

得到的结果比初始值3更接近真实值（4的平方根是2）。如果我们用这个结果做新的估计值来重复这个操作，结果就更加接近了：

  1. >>> x = y
  2. >>> y = (x + a/x) / 2
  3. >>> y 
  4. 2.00641025641

这样进行一些次重复之后，估计值就几乎很准确了：

  1. >>> x = y
  2. >>> y = (x + a/x) / 2
  3. >>> y 2.00001024003
  4. >>> x = y
  5. >>> y = (x + a/x) / 2
  6. >>> y
  7. 2.00000000003

一般情况下，我们不能提前知道到达正确结果需要多长时间，但是当估计值不再有明显变化的时候我们就知道了：

  1. >>> x = y
  2. >>> y = (x + a/x) / 2
  3. >>> y
  4. 2.0

当y和x相等的时候，我们就可以停止了。下面这个循环中，用一个初始值x来开始循环，然后进行改进，一直到x的值不再变化为止：

  1. while True:
  2.     print(x)
  3.     y = (x + a/x) / 2
  4.     if y == x:
  5.         break
  6.     x = y

对大多数值来说，这个循环都挺管用的，但一般来说用浮点数来测试等式是很危险的。浮点数的值只能是近似正确：大多数的有理数，比如1/3，以及无理数，比如根号2，都不能用浮点数来准确表达的。

相比之下，与其对比x和y是否精确相等，倒不如以下方法更安全：用内置的绝对值函数来计算一下差值的绝对值，也叫做数量级。

  1. if abs(y-x) < epsilon:
  2.     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的函数来输出以下这样的表格： 第七章 迭代 - 图2

第一列是数a；第二列是咱们自己写的函数mysqrt计算出来的平方根，第三行是用Python内置的math.sqrt函数计算的平方根，最后一行是这两者的差值的绝对值。

练习2

Python的内置函数eval接收字符串作为参数，然后用Python的解释器来运行。例如：

  1. >>> eval('1 + 2 * 3')
  2. 7
  3. >>> import math
  4. >>> eval('math.sqrt(5)')
  5. 2.2360679774997898
  6. >>> eval('type(math.pi)')
  7. <class 'float'>

写一个叫做eval_loop的函数，交互地提醒用户，获取输入，然后用eval对输入进行运算，把结果打印出来。

这个程序要一直运行，直到用户输入『done』才停止，然后输出最后一次计算的表达式的值。

练习3

传奇的数学家拉马努金发现了一个无穷级数（1914年的论文），能够用来计算圆周率倒数的近似值：

第七章 迭代 - 图3

（译者注：这位拉马努金是一位非常杰出的数学家，自学成才，以数论为主要研究内容，可惜33岁的时候就英年早逝。他被哈代誉为超越希尔伯特的天才。）

写一个名叫estimate_pi的函数，用上面这个方程来计算并返回一个圆周率π的近似值。要使用一个while循环来计算出总和的每一位，最后一位要小于10的-15次方。你可以对比一下计算结果和Python内置的math.pi。

样例代码