Question

1．高斯求和与数学归纳法

递归是函数调用其自身的操作。在讲解递归之前，先来回顾数学家高斯的一个小故事。据说有一次，老师惩罚全班同学，必须算出1到100的和才能回家。只有7岁的高斯想出了一个聪明的解决办法，后来这个方法被称为高斯求和公式。下面我们用编程的方法来解决高斯求和：

---

sum = 0
for i in range(1, 101):       # range()这样的写法表示从1开始，直到100
sum = sum + i
print(sum)     # 结果为5050

---

正如程序显示的，循环是解决问题的一个自然想法。但这并不是唯一的解决方案，我们还可以用下面的方式解题：

---

def gaussian_sum(n):
    if n == 1:
        return 1
    else:
        return n + gaussian_sum(n-1)

print(gaussian_sum(100))          # 结果为5050

---

上面的解法使用了递归（Recursion），即在一个函数定义中，调用了这个函数自身。为了保证计算机不陷入死循环，递归要求程序有一个能够达到的终止条件（Base Case）。递归的关键是说明紧邻的两个步骤之间的衔接条件。比如，我们已经知道了1到51的累加和，即gaussian_sum(51)，那么1到52的累加和就可以很容易地求得：gaussian_sum(52) = gaussian_sum(51) + 52。

使用递归设计程序的时候，我们从最终结果入手，即要想求得gaussian_sum(100)，计算机会把这个计算拆解为求得gaussian_sum(99)的运算，以及gaussian_sum(99)加上100的运算。以此类推，直到拆解为gaussian_sum(1)的运算，就触发终止条件，也就是if结构中n=1时，返回一个具体的数1。尽管整个递归过程很复杂，但在编写程序时，我们只需关注初始条件、终止条件及衔接，而无须关注具体的每一步。计算机会负责具体的执行。

递归源自数学归纳法。数学归纳法（Mathematical Induction）是一种数学证明方法，常用于证明命题^(1)^{#ch1-back}在自然数范围内成立。随着现代数学的发展，自然数范围内的证明实际上构成了许多其他领域，如数学分析和数论的基础，所以数学归纳法对于整个数学体系都至关重要。

数学归纳法本身非常简单。如果我们想要证明某个命题对于自然数 n 成立，那么：

第一步　证明命题对于 n = 1 成立。

第二步　假设命题对于 n 成立， n 为任意自然数，则证明在此假设下，命题对于 n+1 成立。

命题得证

想一下上面的两个步骤。它们实际上意味着，命题对于 n = 1 成立→命题对于 n = 2 成立→命题对于 n = 3 成立……直到无穷。因此，命题对于任意自然数都成立。这就好像多米诺骨牌，我们确定 n 的倒下会导致 n + 1 的倒下，然后只要推倒第一块骨牌，就能保证任意骨牌的倒下。

2．函数栈

程序中的递归需要用到栈 （Stack）这一数据结构。所谓数据结构，是计算机存储数据的组织方式。栈是数据结构的一种，可以有序地存储数据。

栈最显著的特征是 “后进先出” （LIFO，Last In，First Out）。当我们往箱子里存放一叠书时，先存放的书在箱子底部，后存放的书放在箱子顶部。我们必须将后存放的书取出来，才能看到和拿出最开始存放的书。这就是“后进先出”。栈与这个装书的箱子类似，只能“后进先出”。每一本书，也就是栈的每个元素，称为一个 帧 （frame）。栈只支持两个操作：pop和push。栈用弹出（pop）操作来取出栈顶元素，用推入（push）操作将一个新的元素存入栈顶。

正如我们前面所说的，为了计算gaussian_sum(100)，我们需要先暂停gaussian_sum(100)，开始gaussian_sum(99)的计算。为了计算gaussian_sum(99)，需要先暂停gaussian_sum(99)，调用gaussian_sum(98)……。在触发终止条件前，会有很多次未完成的函数调用。每次函数调用时，我们在栈中推入一个新的帧，用来保存这次函数调用的相关信息。栈不断增长，直到计算出gaussian_sum(1)后，我们又会恢复计算gaussian_sum(2)、gaussian_sum(3)，……。由于栈“后进先出”的特点，所以每次只需弹出栈的帧，就正好是我们所需要的gaussian_sum(2)、gaussian_sum(3)……直到弹出藏在最底层的的帧gaussian_sum(100)。

所以，程序运行的过程，可以看作是一个先增长栈后消灭栈的过程。每次函数调用，都伴随着一个帧入栈。如果函数内部还有函数调用，那么又会多一个帧入栈。当函数返回时，相应的帧会出栈。等到程序的最后，栈清空，程序就完成了。

3．变量的作用域

有了函数栈的铺垫，变量的作用域就变得简单了。函数内部可以创建新变量，如下面的一个函数：

---

def internal_var(a, b):
    c = a + b
    return c

print(internal_var(2, 3))       # 结果为5

---

事实上，Python寻找变量的范围不止是当前帧。它还会寻找函数外部，也就是Python的主程序^(2)^{#ch2-back}中定义了的变量。因此，在一个函数内部，我们能“看到”函数外部已经存在的变量。比如下面的程序：

---

def inner_var():
    print(m)

m = 5
inner_var()     # 结果将打印5

---

当主程序中已经有了一个变量，函数调用内部可以通过赋值的方式再创建了一个同名变量。函数会优先使用自己函数帧中的那个变量。在下面的程序中，主程序和函数external_var()都有一个info变量。在函数external_var()内部，会优先使用函数内部的那个info：

---

def external_var():
    info = "Vamei's Python"
    print(info)    # 结果为"Vamei's Python"

info= "Hello World!"
external_var()
print(info)        # 结果为"Hello World!"

---

且函数内部使用的是自己内部的那一份，所以函数内部对info的操作不会影响到外部变量info。

函数的参数与函数内部变量类似。我们可以把参数理解为函数内部的变量。在函数调用时，会把数据赋值给这些变量。等到函数返回时，这些参数相关的变量会被清空。但也有特例，如下面的例子：

---

b = [1,2,3]
def change_list(b):
    b[0] = b[0] + 1
    return b

print(change_list(b))    # 打印[2, 2, 3]
print(b)                 # 打印[2, 2, 3]

---

我们将一个表传递给函数，函数进行操作后，函数外部的表b发生变化。当参数是一个数据容器时，函数内外部只存在一个数据容器，所以函数内部对该数据容器的操作，会影响到函数外部。这涉及到Python的一个微妙机制，我们会在第7章对此深入探索。现在需要记住的是，对于数据容器来说，函数内部的更改会影响到外部。