目 录
1. 递归函数
递归函数： 函数直接或者间接调用自身就是递归函数。
- 递归是解决问题的一种方式，它的整体思想
- 递归函数是指 连续执行某一处理过程时， 该过程的某一步要用到他自身的上一步或者上几步的结果。
- 当有一种方法可以将要解决的问题从某个方面分化为更简单或更小的、相同类型的问题时，即可考虑使用递归。
递归分类：
（1）、直接递归
在函数a中又调用函数a自己
（2）、间接递归
如果函数a中先调用函数b，函取b调用函数a，则称函数a为间接递归
注意：
编写递归程序时要注意： 找出正确的递归算法； 确定结束递归结束的条件（边界条件）
递归特性：
优点：程序变得简洁，紧凑，容易解决问题；缺点：牺牲存储空间，影响程序执行的速度。
- （1）、必须有明确结束条件（递归一定需要有边界条件），递归调用一定执行到这个退出条件。没有退出条件的递归调用，就是无限调用
- （2）、python3的cpython中递归深度为1000
- （3）、每次进入更深递归时，问题规模应比上次递归少
- （4）、递归效率不高，递归层次过多会导致栈溢出。超过递归深度限制，抛出RecursionError:maxinum recursion depth exceeded 超出最大深度
import sys
print('最大递归深度：', sys.getrecursionlimit()) # 1000
# 执行结果：
最大递归深度： 1000
递归式函数有2个条件：
1. 基线条件 ： 问题可以被分解为最小问题，当满足基线条件时，递归就不执行了
2. 递归条件 ： 可以将问题继续分解的条件
**例1：**计算连续整数之和（递归）
# 例1：计算连续整数之和（递归）
def sum_num(num):
if num == 1:
return 1
# 设sum_num函数用于完成num - 1 的累加，则：
tmp = sum_num(num - 1)
return num + tmp # 算法：两个数字的相加
print(sum_num(100))
# 执行结果：
5050
2. 求任意数的阶乘
def fun(x):
if x == 1: # 基线条件
return 1
return fun(x-1)*x # 递归条件
print(fun(5)) # 得 120
3. 高阶函数
高阶函数： 接收函数作为参数，或者将别的函数对象作为返回值返回的函数就是高阶函数
例1：
# 高阶函数：接受函数做为参数，或者将别的函数对象作为返回值返回的函数就是高阶函数
# 例：
def fun_(c, b, func): # 函数作为参数
return func(c) % func(b) # 函数作为返回值
print((fun_('5', '-2', eval))) # -1
# 执行结果：-1
例2：
# 接收函数作为参数，或者将别的函数作为返回值返回的函数就是高阶函数
import time
# ---------------------------------
def time_begin():
global t1
t1 = time.perf_counter()
print('起始时间t1：')
return t1
time_begin()
# time.perf_counter() # 调用一次 perf_counter()，从计算机系统里随机选一个时间点A，计算其距离当前时间点B1有多少秒。当第二次调用该函数时，默认从第一次调用的时间点A算起，距离当前时间点B2有多少秒。两个函数取差，即实现从时间点B1到B2的计时功能。
# ------------------------------------
g = lambda x: x % 2 == 0
def fun(x):
if g(x):
return True
else:
return False
def fun1(fn):
list1 = []
for i in range(1, 101):
if fn(i):
list1.append(i)
print(list1)
return "偶数列举完毕！"
print(fun1(fun))
# -----------------------------
def time_end():
t2 = time.perf_counter()
alltime = t2 - t1
return alltime
print('程序列举运算总耗时为：', time_end(),'秒')
# 执行结果：
# [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100]
# 偶数列举完毕！
# 程序列举运算总耗时为： 0.0001674000000093656 秒
特殊说明
递归不是高阶函数
因为 高阶函数是将别的函数对象作为 返回值
而 递归函数 是自己调用自己
- 递归是解决问题的一种方式，它的整体思想，是将一个大问题分解为一个个的小问题，直到问题无法分解时，在去解决问题（递归简单理解就是自己调用自己）
4. 匿名函数
-
定义一个匿名函数并调用，定义格式如–>lambda 参数1, 参数2…参数n : 表达式
-
防止重名，不用再去定义函数，使用方便，可以作为一个传参的工具
-
lambda函数就是匿名函数
格式：
lambda 形式参数： 表达式
例如：
（1）、lambda a: a % 2 == 0 # 只有形参，无实参，这整个是一个函数对象
（2）、(lambda m, n: m + n)(1, 2) # m, n是形参，1和2是实参
（3）、(lambda a: a % 2 == 0)(132) # 形参a，实参132
匿名函数的定义
（1）、lambda 关键字表示匿名函数
（2）、冒号前面为参数，可以多个参数，可位置传参和关键字传参
（3）、冒号后面为表达式，只能有一个
（4）、且只能有 一个返回值
匿名函数的作用
- 匿名函数作为参数传参
- 匿名函数可以减少命名空间，减少函数名的重复率
- 不用再去定义函数，使用方便
例1：
list = [1,2,3,4,5,6,7,8]
# 语法： lambda 参数 ：表达式
print(lambda a,b: a+b)(1,2) # 前面形参，后面实参
s = lambda a : a % 2 == 0
# filter() 有两个参数，第一个参数（函数）是过滤规则，第二个是过滤的数据
print(list(filter(s,list1)))
例2： 匿名函数的参数 可以使用默认参数和关键字参数， 但不能使用*和**号的参数
# 匿名函数的参数 可以使用默认参数和关键字参数， 但不能使用* 和** 号的参数
lmd1 = lambda e, g, z=2: e * 10 + g + z ** 3
print(lmd1(4, 1, 3)) # 68
print(lmd1(2, 5)) # 33
print(lmd1(z=3, e=7, g=2)) # 99
例3： 把匿名函数作用为返回值返回给调用函数
# 匿名函数作为另外一个函数调用的返回值
def fun_out():
return lambda x, y: x * y
fin = fun_out()
print(fin(2, 5)) # 10
例4： 匿名函数在列表和字典中作为元素
# 匿名函数在列表和字典中作为元素
# ------------------------------------------1-列表元素-----------------------------------------------------------
xy = [lambda x, y: x + y, lambda x, y: x ** 2 + y ** 2, 1, 2]
print(xy) # [<function <lambda> at 0x000000001E144C10>, <function <lambda> at 0x000000001E144CA0>, 1, 2]
print(xy[0](2, 3), xy[1](2, 3)) # 5 13
# ------------------------------------------2-字典元素-----------------------------------------------------------
lmd = {"a": lambda x, y: x + y, "b": lambda x, y: x ** 2 + y ** 2}
print(lmd["a"](23, 27), lmd["b"](3, 4)) # 50 25
print(lmd) # {'a': <function <lambda> at 0x000000001E144C10>, 'b': <function <lambda> at 0x000000001E144CA0>}
# ------------------------------------------3-列表元素-----------------------------------------------------------
list1 = list(range(1, 10))
lmd_ = lambda a: a % 2 == 0
print(list(filter(lmd_, list1))) # [2, 4, 6, 8] # filter(参数(判断函数), 可迭代对象)的作法见下面插补内容。
插补filter()函数用法：
filter(function, iterable)函数：
参数：function – 判断函数。iterable – 可迭代对象。
返回值：返回列表
# 过滤出列表中的所有奇数：
def is_odd(n):
return n % 2 == 1
newlist = filter(is_odd, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
print(newlist) # [1, 3, 5, 7, 9]
# 过滤出1~100中平方根是整数的数：
import math
def is_sqr(x):
return math.sqrt(x) % 1 == 0
newlist = filter(is_sqr, range(1, 101))
print(newlist) # [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
5. 闭包（将函数对象作为返回值）
闭包的定义： 将函数对象作为返回值也是高阶函数我们也称为闭包。闭包本质上就是一个函数
如何创建闭包？
◉ 函数要嵌套（有内外部函数）
◉ 内部函数使用外部函数的变量
◉ 外部函数返回内部函数的名称
如何使用闭包？ 典型的使用场景是装饰器的使用。
global与nonlocal的区别：
◉ global可以改变全局变量，同时可以定义新的全局变量；
◉ nonlocal只能改变外层函数变量，不能定义新的外层函数变量，并且nonlocal也不能改变全局变量。
◉ global关键字可以用在任何地方，包括最上层函数中和嵌套函数中；
◉ nonlocal关键字只能用于嵌套函数中，并且外层函数中必须定义了相应的局部变量，否则会发生错误。
闭包的好处：
◉ 通过闭包可以创建一些只有当前函数能访问的变量
◉ 可以将一些私有数据藏到闭包中
特性： 可以保证外部函数变量不被销毁
行成闭包的条件：
◉ 函数嵌套
◉ 将内部函数作为返回值返回
◉ 内部函数必须要使用到外部函数的变量
例1：
def outFun(arg1):
def inFun(arg2):
nonlocal arg1 # nonlocal关键字用来在函数或其他作用域中使用外层(非全局)变量。
arg1+=200
return arg1*arg2
return inFun
infun=outFun(100) # 调用外部函数，传入参数，返回是内部函数
result=infun(300) # 调用内部函数，传入参数
print("the result is:",result)
#使用闭包求给function计算耗时（上面的内容已经提到）代码如下：
import time
def waste_time(func): # 用于计算函数执行的耗时
def function(*args,**kwargs):
start_time=time.time()
result=func(*args,**kwargs)
end_time=time.time()
spend=end_time-start_time
print("函数%s 总共耗时%.3f秒:"%(func.__name__,spend))
return result
return function
例2：
def fun_out(a):
def fun_inner(b):
# nonlocal a
# a = 20
c = a + b
print(c)
print(a)
return c
return fun_inner
x = fun_out(50)
print(x(30))
# 执行结果：
80
50
80
6. 作业
题目：猴子吃桃问题（递归）：
猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了，求第一天共摘了多少桃子？
方法一：
思路分析：
- 假设第一天桃子的数量为x，则当天吃掉的桃子为 x/2+1，第二天的桃子的（余数）初始数量为 x-(x/2+1) = x/2-1；按此规律推演，据题意可知，第十天的桃子数量为1；
- 第一天的桃子的数量和第二天的桃子数量之间的关系为：（第二天桃子的数量+1）*2
程序设计：
连续两天之间的桃子的数量之间的关系，用等价的表达式可以表示为（n代表天数）：f(n)=(f(n-1)+1)*2，程序代码如下：
def f(n): # n代表天数
if n == 1: # 递归的出口很重要，否则会形成死循环
return 1
return (f(n-1)+1)*2
print('第%d天桃子数:', f(10)) # 求出第10天的桃子总数
for n in range(10,0,-1): # 每天的初始的桃子数量
print('第%d天桃子数:' % n, f(n))
# 执行结果：
1534
第10天桃子数: 1534
第9天桃子数: 766
第8天桃子数: 382
第7天桃子数: 190
第6天桃子数: 94
第5天桃子数: 46
第4天桃子数: 22
第3天桃子数: 10
第2天桃子数: 4
第1天桃子数: 1
方法二：
def fun(x):
if x == 10 :
return 1
return 2*(fun(x + 1) + 1)
print(fun(1)) # 得 1534 第一天共摘了1534个桃子
# 执行结果：
1534