目录
一、概述
- 代码复用与模块化设计
- 函数递归的理解
- 函数递归的调用过程
- 函数递归实例解析
二、代码复用与模块化设计
2.1 代码复用
把代码当成资源进行抽象
- 代码资源化：程序代码是一种用来表达计算的"资源"
- 代码抽象化：使用函数等方法对代码赋予更高级别的定义
- 代码复用：同一份代码在需要时可以被重复使用
函数 和 对象 是代码复用的两种主要形式
函数：将代码命名
在代码层面建立了初步抽象
对象：属性和方法
<a>.<b> 和 <a>.<b>()
在函数之上再次组织进行抽象
2.2 模块化设计
分而治之
- 通过函数或对象封装将程序划分为模块及模块间的表达
- 具体包括：主程序、子程序和子程序间关系
- 分而治之：一种分而治之、分层抽象、体系化的设计思想
紧耦合 松耦合
- 紧耦合：两个部分之间交流很多，无法独立存在
- 松耦合：两个部分之间交流较少，可以独立存在
- 模块内部紧耦合、模块之间松耦合
三、函数递归的理解
3.1 递归的定义
函数定义中调用函数自身的方式
3.2 递归的两个关键特征
- 链条：计算过程存在递归链条
- 基例：存在一个或多个不需要再次递归的基例
3.3 类似数学归纳法
- 数学归纳法
- 证明当n取第一个值n0n0 时命题成立
- 假设当nknk 时命题成立，证明当n=nk+1n=nk+1 时命题也成立
- 递归是数学归纳法思维的编程体现
四、函数递归的调用过程
4.1 递归的实现
n!={1n(n−1)!n=0otherwisen!={1n=0n(n−1)!otherwise
def fact(n):
if n == 0:
return 1
else:
return n * fact(n - 1)
4.2 函数 + 分支语句
- 递归本身是一个函数，需要函数定义方式描述
- 函数内部，采用分支语句对输入参数进行判断
- 基例和链条，分别编写对应代码
4.3 递归的调用过程
五、函数递归实例解析
5.1 字符串反转
将字符串s反转后输出：s[::-1]
- 函数 + 分支结构
- 递归链条
- 递归基例
def rvs(s):
if s == "":
return s
else:
return rvs(s[1:]) + s[0]
5.2 斐波那契数列
斐波那契数列
F(n)=⎧⎩⎨11F(n−1)+F(n−2)n=1n=1otherwiseF(n)={1n=11n=1F(n−1)+F(n−2)otherwise
F(n)=F(n−1)+F(n−2)F(n)=F(n−1)+F(n−2)
- 函数 + 分支结构
- 递归链条
- 递归基例
def f(n):
if n == 1 or n == 2:
return 1
else:
return f(n - 1) + f(n - 2)
5.3 汉诺塔
- 函数 + 分支结构
- 递归链条
- 递归基例
def hanoi(n, src, dst, mid):
global count
if n == 1:
print("{}:{}->{}".format(1, src, dst))
count += 1
else:
hanoi(n - 1, src, mid, dst)
print("{}:{}->{}".format(n, src, dst))
count += 1
hanoi(n - 1, mid, dst, src)
count = 0
hanoi(3, 'A', 'B', 'C')
print(count)
1:A->B
2:A->C
1:B->C
3:A->B
1:C->A
2:C->B
1:A->B
7
六、单元小结
6.1 代码复用与函数递归
- 模块化设计：松耦合、紧耦合
- 函数递归的2个特征：基例和链条
- 函数递归的实现：函数 + 分支结构