【第六天】Python的递归与库

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便可以找到那个模块