3.3 递归
1. 高斯求和与数学归纳法
求 1 到 100 的和, 用编程方法解决:
- sum = 0
- for i in range(1,101):
- 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, 尽管整个递归过程很复杂
但是在编写程序时, 我们只需要关注初始条件, 终止条件及衔接
而无需关注具体的每一步, 计算机会负责具体的执行
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
事实上, py 寻找变量的范围不止是当前帧, 它还会寻找函数外部
也就是 py 主程序中定义了的变量, 因此, 在一个函数内部
我们能 "看到" 函数外部已经存在的变量, 例如:
- 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))
- print(b)
- [2, 2, 3]
- [2, 2, 3]
我们将一个表传递给函数, 函数进行操作后, 函数外部的表 b 发生变化
当参数是一个数据容器时, 函数内外部只存在一个数据容器
所以函数内部对该数据容器的操作, 会影响到函数外部
这涉及到 py 的一个微妙机制, 在第六章会对此进行深入探索
3.4 引入
1. 引入模块
在 py 中, 一个. py 文件就构成了一个模块, 通过模块, 你可以调用其他文件中的函数
而引入 (import) 模块, 就是为了在新程序中重复利用已有的 py 程序
对于面向过程语言来说, 模块是比函数更高一层的封装模式
程序可以以文件为单位实现复用, 典型的面向过程语言, 如 c 语言
就有很完善的模块系统, 把常见功能编到模块中, 方便未来使用
就成了所谓的库(library)
由于 py 的库非常丰富, 所以很多工作都可以通过引用库
即借助前人的工作来完成
2. 搜索路径
py 会在其他地方寻找库:
(1) 标准库的安装路径
(2) 操作系统环境变量 PYTHONPATH 所包含的路径
标准库是 py 官方提供的库, py 会自动搜索标准库所在路径
如果是自定义模块, 则可以放在自认为合适的地方
然后修改 PYTHONPATH 这个环境变量, 当 PYTHONPATH 包含模块所在路径时
py 便可以找到那个模块
来源: http://www.jianshu.com/p/29e46ae55adb