目录
- 一、概述
- 二、代码复用与模块化设计
- 2.1 代码复用
- 2.2 模块化设计
- 三、函数递归的理解
- 3.1 递归的定义
- 3.2 递归的两个关键特征
- 3.3 类似数学归纳法
- 四、函数递归的调用过程
- 4.1 递归的实现
- 4.2 函数 + 分支语句
- 4.3 递归的调用过程
- 五、函数递归实例解析
- 5.1 字符串反转
- 5.2 斐波那契数列
- 5.3 汉诺塔
- 六、单元小结
- 6.1 代码复用与函数递归
一、概述
- 代码复用与模块化设计
- 函数递归的理解
- 函数递归的调用过程
- 函数递归实例解析
二、代码复用与模块化设计
2.1 代码复用
把代码当成资源进行抽象
- 代码资源化：程序代码是一种用来表达计算的"资源"
- 代码抽象化：使用函数等方法对代码赋予更高级别的定义
- 代码复用：同一份代码在需要时可以被重复使用
函数 和 对象 是代码复用的两种主要形式
函数：将代码命名
在代码层面建立了初步抽象
对象：属性和方法
<a>.<b> 和 <a>.<b>()
在函数之上再次组织进行抽象
2.2 模块化设计
分而治之
- 通过函数或对象封装将程序划分为模块及模块间的表达
- 具体包括：主程序、子程序和子程序间关系
- 分而治之：一种分而治之、分层抽象、体系化的设计思想
紧耦合 松耦合
- 紧耦合：两个部分之间交流很多，无法独立存在
- 松耦合：两个部分之间交流较少，可以独立存在
- 模块内部紧耦合、模块之间松耦合
三、函数递归的理解
3.1 递归的定义
函数定义中调用函数自身的方式
3.2 递归的两个关键特征
- 链条：计算过程存在递归链条
- 基例：存在一个或多个不需要再次递归的基例
3.3 类似数学归纳法
- 数学归纳法
- 证明当n取第一个值\(n_0\)时命题成立
- 假设当\(n_k\)时命题成立，证明当\(n=n_k+1\)时命题也成立
- 递归是数学归纳法思维的编程体现
四、函数递归的调用过程
4.1 递归的实现
\[n!= \begin{cases} 1 & n=0 \\ n(n-1)! & \text{otherwise} \end{cases} \]
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)= \begin{cases} 1 & n=1 \\ 1 & n=1 \\ F(n-1)+F(n-2) & otherwise \end{cases} \]
\(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个特征：基例和链条
- 函数递归的实现：函数 + 分支结构