4.4递归函数

4.4.1 递归函数的定义

函数在定义中调用自身的方式称为递归调用，简称递归。包含递归调用的函数称为递归函数。

递归函数具有就两个关键特征：递归基例和递归链条。

  • 递归基例是不需要再次递归的确定值或确定表达式。递归函数可能存在一个或多个基例。
  • 递归链条在递归函数中表达递归调用关系，所有递归链条均以一个或多个基例结尾
1
2
3
4
if <基例条件>:
    <返回：基例值>
else:
    <构造：递归链>

下面是计算 n 的阶乘值：

1
2
3
4
5
6
7
def fact(n):
    if n==0:
        return 1
    else:
        return n*fact(n-1)
num=eval(input("请输入一个正整数"))
print(fact(num))

4.4.2 计算方法：递归分解法

  1. 提取递归变量：提取反映递归特征的主要变量；
  2. 构建递归链条：以递归变量为核心，构建递归链条，初步构造递归函数；
  3. 确定递归基例：设定递归变量极值，缩小计算问题规模、获得确定结果，作为递归基例，完善递归函数。

递归分解法的核心是以构造递归函数为核心，包含递归变量、递归基调、递归链条。

实例 1：字符串反转

对于用户输入的字符串 s，输出反转后的字符串。

1
2
3
4
5
6
7
def reverse(s):
    if len(s) <= 1:
        return s
    else:
        return reverse(s[1:]) + s[0]
str = input("请输入一个字符串")
print(reverse(str))

实例 2：斐波那契数列

根据斐波那契数列构建递归函数。

1
2
3
4
5
6
7
8
def f(n):
    if n==0 or n==1:
        return=1
    else:
        return f(n-2) + f(n-1)
n = eval(input("请输入一个整数："))
for i in range(n):
    print(f(i),end=",")

实例 3：汉诺塔

根据汉诺塔构建递归函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#src 为第一个杆，mid 为第二个杆，dst 为第三个杆
count = 0
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)
hanoi(3,"A","C","B")
print("总移动步数："，count)

4.5代码复用和模块化设计

4.5.1抽象和代码复用

  • 编程语言从代码层面采用函数和对象两种抽象方式，分别对应面向过程和面向对象。
  • 函数是程序的一种基本抽象方式，它将一系列代码组织起来赋予名称，其他程序通过名字调用函数。
  • 对象是程序的一种高级抽象方式，它将程序代码组织为更高级别的类。对象包括表征对象特征的属性和代表对象操作的方法。

4.5.2模块化设计

模块是代码组合，表达一个特定功能。模块化设计能够简化程序设计，表现程序结构。

  1. 紧耦合：尽可能合理划分功能块，功能块内部耦合紧密。
  2. 松耦合：模块间关系尽可能简单，功能块之间耦合度低。

  • 耦合性是指程序结构中各模块之间相互关联的程度*，它取决于各模块间接口的复杂程度和调用方式。耦合性是影响软件复杂程度和设计质量的一个重要因素。

  • 紧耦合指各模块之间关系紧密，存在较多或复杂的互相调用。紧耦合的缺点在于更新一个模块可能导致其他模块变化，复用较困难。

  • 松耦合一般基于消息或协议实现，传递参数简单，系统交互简单。

4.6Python 标准函数

4.6.1Python 中的函数分类

  • python函数有四类，分别是：
  • 内置函数：python一经运行就加载到内存的，例如有list，len，str等函数
  • 标准库函数：需要用import语句进行导入，常见标准库有time，os等
  • 第三方库：需要另外下载到本地的库，例如opencv库，然后用import导入
  • 自定义函数：自己在模块里的写的函数

下为标准库中 71 个函数：

Aabs()aiter()all()anext()any()ascii() Bbin()bool()breakpoint()bytearray()bytes() Ccallable()chr()classmethod()compile()complex() Ddelattr()dict()dir()divmod() Eenumerate()eval()exec() Ffilter()float()format()frozenset() Ggetattr()globals() Hhasattr()hash()help()hex() Iid()input()int()isinstance()issubclass()iter() Llen()list()locals() Mmap()max()memoryview()min() Nnext() Oobject()oct()open()ord() Ppow()print()property() Rrange()repr()reversed()round() Sset()setattr()slice()sorted()staticmethod()str()sum()super() Ttuple()type() Vvars() Zzip() ___import__()