文章目录
- 1. 函数的执行流程
- 1.1. 字节码了解压栈过程
- 1.2. 嵌套函数的压栈
- 2. 递归
- 2.1. 递归函数
- 2.2. 递归的性能
- 2.3. 递归的优化
- 2.4. 间接递归
- 2.5. 递归总结
- 3. 匿名函数
- 4. Python 生成器
- 4.1. 基本结构
- 4.2. 使用场景
- 4.3. 协程 coroutine
- 4.4. yield from
1. 函数的执行流程
函数的执行需要对函数进行 压栈 ，什么是压栈呢，简而言之就是在函数执行时在栈中创建 栈帧 存放需要的 变量 以及 指针 的意思。具体涉及的知识非常多，这里就以一个 Python 脚本简单进行分析。
def
foo1
(
b
,
b1
=
3
)
:
print
(
'call foo1'
,
b
,
b1
)
def
foo2
(
c
)
:
foo3
(
c
)
print
(
'call foo2'
,
c
)
def
foo3
(
d
)
:
print
(
'call foo3'
,
d
)
def
main
(
)
:
print
(
'call main'
)
foo1
(
100
,
101
)
foo2
(
20
)
print
(
'main ending'
)
main
(
)
当我们运行上面代码时，它的执行流程如下：
- 全局栈帧中生成 foo1、foo2、foo3、main 函数对象
- main 函数调用
- main 中查找内建函数 print 压栈，将常量字符串压栈，调用函数，弹出栈顶
- main 中全局查找函数 foo1 压栈，将常量 100、101 压栈，调用函数 foo1，创建栈帧。print 函数压栈，字符串和变量 b、b1 压栈，调用函数，弹出栈顶，返回值。
- main 中全局查找 foo2 函数压栈，将常量 20 压栈，调用 foo2，创建栈帧。foo3 函数压栈，变量 c 引用压栈，调用 foo3，创建栈帧。foo3 完成 print 函数调用返回。foo2 恢复调用，执行 print 语句后，返回值。main 中 foo2 调用结束后弹出栈顶，main 继续执行 print 函数调用，弹出栈顶，main 函数返回。
1.1. 字节码了解压栈过程
Python 代码先被编译为字节码后，再由 Python 虚拟机来执行字节码， Python 的字节码是一种类似汇编指令的中间语言， 一个 Python 语句会对应若干字节码指令，虚拟机一条一条执行字节码指令， 从而完成程序执行。Python
dis 模块
支持对 Python 代码进行反汇编， 生成字节码指令。下面针对上面的例子通过字节码理解函数调用时的过程。
import
dis
print
(
dis
.
dis
(
main
)
)
# ======> result
53
0
LOAD_GLOBAL
0
(
print
)
2
LOAD_CONST
1
(
'call main'
)
4
CALL_FUNCTION
1
6
POP_TOP
54
8
LOAD_GLOBAL
1
(
foo1
)
10
LOAD_CONST
2
(
100
)
12
LOAD_CONST
3
(
101
)
14
CALL_FUNCTION
2
16
POP_TOP
55
18
LOAD_GLOBAL
2
(
foo2
)
20
LOAD_CONST
4
(
20
)
22
CALL_FUNCTION
1
24
POP_TOP
56
26
LOAD_GLOBAL
0
(
print
)
28
LOAD_CONST
5
(
'main ending'
)
30
CALL_FUNCTION
1
32
POP_TOP
34
LOAD_CONST
0
(
None
)
36
RETURN_VALUE
字节码含义 ：
-
LOAD_GLOBAL：加载全局函数 (print) -
LOAD_CONST: 加载常量 -
CALL_FUNCTION: 函数调用 -
POP_TOP：弹出栈顶 -
RETURN_VALUE： 返回值
1.2. 嵌套函数的压栈
def
outer
(
)
:
c
=
100
def
inner
(
)
:
nonlocal
c
c
+=
200
return
c
return
inner
a
=
outer
(
)
a
(
)
- 函数只有在执行的时候才会压栈，所以在 outer 执行时，会开辟栈空间压栈 (c,inner)
-
执行完后，删除栈空间，但是由于 outer 返回了内部函数 inner，但并没有执行，所以不会继续压栈，当执行 a 的时候，会重新压栈，而此时内部函数已经记住了外部自由变量
c，并且每次调用 outer 都会重新生成一个 inner。
注意：这种情况叫做闭包，自由变量 c 会被当成内部函数 inner 的一个属性，被调用。
PS ：内存两大区域 (栈，堆)。垃圾回收，清理的是堆中的空间。函数的调用就是压栈的过程，而变量的创建都是在堆中完成的。 栈中存储的都是堆中的内存地址的指向，栈清空，并不会使堆中的对象被清除，只是指向已经被删除。 函数，变量都是在堆内创建的，函数调用需要压栈 。
2. 递归
函数直接或者间接的调用自身就叫 递归 ，递归需要有边界条件、递归前进段、递归返回段，当边界条件不满足的时候，递归前进，当边界条件满足时，递归返回。 注意：递归一定要有边界条件，否则可能会造成内存溢出。
2.1. 递归函数
前面我们学过斐波那契序列，利用递归函数，我们可以更简洁的编写一个计算斐波那契序列第 N 项，或者前 N 项的代码：
在数学上，斐波纳契数列以如下被以递推的方法定义：
F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n >= 3，n ∈ N*）
# 公式版本
def
fib
(
n
)
:
if
n
<
3
:
return
1
return
fib
(
n
-
1
)
+
fib
(
n
-
2
)
# 公式版本之简洁版
def
fib
(
n
)
:
return
1
if
n
<
3
else
fib
(
n
-
1
)
+
fib
(
n
-
2
)
很多人可能不明白其中原理，这里简要说明一下，以 fib(6) 为例子:
- fib(6) 返回 fib(5) + fib(4)
- fib(5) 返回 fib(4) + fib(3)
- fib(4) 返回 fib(3) + fib(2)
- fib(3) 返回 fib(2) + fib(1)
- fib(2),fib(1) 是边界，return 1，然后逐级调用返回
[外链图片转存失败(img-AbD3k3t3-1562240946327)(https://github.com/colinlee19860724/Study_Notebook/raw/master/Photo/re_fib.png)]
递归的要求：
- 递归一定要有退出条件，递归调用一定要执行到这个退出条件。没有退出条件的递归调用，就是无限调用
-
递归调用的深度不宜过深，Python 对递归的深度做了限制，以保护解释器，超过递归深度限制，则抛出
RecursionError异常。
使用
import sys; sys.getrecursionlimit()获取当前解释器限制的最大递归深度
2.2. 递归的性能
由于 Python 是预先计算等式右边的，所以我们发现，上图中，重复计算了
fib(4)
和
fib(3)
那么效率呢？由于只是计算了 fib(6)，如果
fib(35)
呢？可以预想，它要重复计算多少次啊。这里我们来测试一下它执行的时间。
# 递归版本
import
timeit
def
fib
(
n
)
:
return
1
if
n
<
3
else
fib
(
n
-
2
)
+
fib
(
n
-
1
)
start
=
timeit
.
default_timer
(
)
fib
(
35
)
duration
=
timeit
.
default_timer
(
)
-
start
print
(
'{:.6f}'
.
format
(
duration
)
)
# 1.783832
# 循环版本
def
fib
(
n
)
:
a
=
1
b
=
1
count
=
2
while
count
<
n
:
a
,
b
=
b
,
a
+
b
count
+=
1
return
b
start
=
timeit
.
default_timer
(
)
fib
(
35
)
duration
=
timeit
.
default_timer
(
)
-
start
print
(
'{:.6f}'
.
format
(
duration
)
)
# 0.000037
经过对比，我们发现使用递归虽然代码更优美了，但是运行时间还不如我们的普通循环的版本，这是因为递归重复计算了很多次，当规模到达一定程度时，那么这个时间是成指数递增的。
总结一下现在的问题：
- 循环稍微复杂一点，但是只要不是死循环，可以多次迭代直至算出结果
- fib 函数代码极简易懂，但是只要获取到最外层的函数调用，内部跌代结果都是中间结果。而且给定一个 n 都要进行近 2n 次递归，深度越深，效率越低。为了获取斐波那契数列需要在外面套一个 n 次的循环，效率就更低了。
- 递归还有深度限制，如果 递归复杂 ， 函数反复压栈 ，栈内存就很快溢出了。
2.3. 递归的优化
如何优化呢？前面的版本使用递归函数时会重复计算一些相同的数据，那么我们来改进一下，在代码层面对递归的特性进行优化。
import
timeit
def
fib
(
n
,
a
=
1
,
b
=
1
)
:
a
,
b
=
b
,
a
+
b
if
n
<
3
:
return
b
return
fib
(
n
-
1
,
a
,
b
)
start
=
timeit
.
default_timer
(
)
fib
(
35
)
duration
=
timeit
.
default_timer
(
)
-
start
print
(
'{:.6f}'
.
format
(
duration
)
)
# 0.000038
代码优化后，发现运行时间很快，因为计算的是
fib(n),fib(n-1)..fib(1)
并没有进行重复计算，所以要使用递归，必须要考虑重复计算以及函数递归调用时产生的内存浪费等。
2.4. 间接递归
间接递归，就是通过别的函数，来调用函数本身，下面来看一个例子，来理解间接递归的概念：
def
foo1
(
)
:
foo2
(
)
def
foo2
(
)
:
foo1
(
)
foo1
(
)
# RecursionError: maximum recursion depth exceeded
我们可以看到，这种递归调用是非常危险的，但是往往在代码复杂的情况下，还是可能发生这种调用。要用代码规范来避免这种递归调用的发生。
2.5. 递归总结
递归是一种很自然的表达，符合逻辑思维：
- 运行效率低，每一次调用函数都要开辟栈帧。
- 有深度限制，如果递归层次太深，函数反复压栈，栈内存很快就溢出了。
- 如果是有限次数的递归，可以使用递归调用，或者使用循环代替，虽然代码稍微复杂一点，但是只要不是死循环，可以多次叠代直至算出结果。
- 绝大多数递归，都可以使用循环实现， 能不用递归则不用递归 。
3. 匿名函数
没有名字的函数，在 Python 中被称为匿名函数，考虑一下，我们之前都是通过 def 语句定义函数的名字，而开始定义一个函数的，那么不用名字该如何定义函数？函数没有名字又该如何调用呢？
Python 中借助 lambda 表达式构建匿名函数。它的格式为：
lambda
' 参数列表 '
：
' 返回值 '
# 等于:
def
xxx
(
参数列表
)
:
return
返回值
需要注意的是：
- 冒号左边是参数列表，但不要括号。
- 冒号右边是函数体，但不能出现等号。
- 函数体只能写一行，不能使用分号分隔多个语句。(也被称为单行函数)
- return 语句，可以不写 return 关键字
下面来看一下各种匿名函数的写法
(
lambda
x
,
y
:
x
+
y
)
(
4
,
5
)
# 9
(
lambda
x
,
y
=
10
:
x
+
y
)
(
10
)
# 20
(
lambda
x
,
y
=
10
:
x
+
y
)
(
x
=
10
)
# 20
(
lambda
x
,
y
=
10
:
x
+
y
)
(
10
,
y
=
10
)
# 20
(
lambda
x
,
y
=
10
,
*
args
:
x
+
y
)
(
10
,
y
=
10
)
# 20
(
lambda
x
,
y
=
10
,
*
args
,
**
kwargs
:
x
+
y
)
(
10
,
y
=
10
)
# 20
(
lambda
*
args
:
(
i
for
i
in
args
)
)
(
1
,
2
,
3
,
4
,
5
)
# generate<1,2,3,4,5>
(
lambda
*
args
:
(
i
for
i
in
args
)
)
(
*
range
(
5
)
)
# generate<0,1,2,3,4>
[
x
for
x
in
(
lambda
*
args
:
(
i
for
i
in
args
)
)
(
*
range
(
5
)
)
]
# [0, 1, 2, 3, 4]
[
x
for
x
in
(
lambda
*
args
:
map
(
lambda
x
:
x
+
1
,
(
i
for
i
in
args
)
)
)
(
*
range
(
5
)
)
]
# [1, 2, 3, 4, 5]
- lambda 是一个匿名函数，我们在它后面加括号就表示函数调用
- 在高阶函数传参时，使用 lambda 表达式，往往能简化代码
还记得，我们之前的默认值字典吗，这里的：
d = collections.defaultdict(lambda :0)，其实就等于(lambda :0)()，即当我们传入任意值时都返回 0
4. Python 生成器
生成器指生成器对象，可以由生成器表达式得到，也可以使用 yield 关键字得到一个生成器函数，调用这个函数返回一个生成器对象。
生成器函数，函数体中包含 yield 关键字的函数，就是生成器函数，调用后返回生成器对象。关于生成器对象，我们可以理解它就是一个
可迭代对象
，是一个
迭代器
，只不过它是
延迟计算
的，
惰性求值
的。
4.1. 基本结构
我们说在函数中使用 yield 关键字来返回数据的函数，叫做 生成器函数 ，那么我们来写一个生成器函数，看看和 return 函数有什么区别
def
func
(
)
:
for
i
in
range
(
2
)
:
yield
i
g
=
func
(
)
In
:
next
(
g
)
Out
:
0
In
:
next
(
g
)
Out
:
1
In
:
next
(
g
)
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
StopIteration Traceback
(
most recent call last
)
<
ipython
-
input
-
93
-
e734f8aca5ac
>
in
<
module
>
-
-
-
-
>
1
next
(
g
)
StopIteration
:
这个报错看起来是不是很熟悉？没错，和生成器表达式的结果是相同的，只不过生成器函数可以写的更加的复杂，现在我们来看下生成器函数的执行过程。
- 当函数执行过程中遇到 yield 函数时，会暂停，并把 yield 表达式的值返回。
- 再次执行时会执行到下一个 yield 语句
yield 关键字，和return 关键字在生成器场景下， 不能一起使用 。因为 return 语句会导致当前函数立即返回，无法继续执行，也无法继续获取下一个值，并且 return 语句的返回值也不能被next()获取到，还会产生 StopIteration 的异常.
再来总结一下生成器的特点：
-
包含
yield语句的生成器函数调用生成生成器对象的时候，生成器函数的函数体不会立即执行。 -
next(genreator)会从函数的当前位置向后执行到之后碰到的一个yield语句，会弹出值，并暂停函数执行。 -
再次调用
next函数，和上一条一样的处理结果 -
继续调用
next函数，生成器函数如果结束执行了（显示或隐式调用了return语句），会抛出 StopIteration 异常
4.2. 使用场景
我们想要生成一个无限自然数的序列时，生成器就是一个很好的方式
def
counter
(
)
:
c
=
0
while
True
:
c
+=
1
yield
c
c
=
counter
(
)
In
:
next
(
c
)
Out
:
1
In
:
next
(
c
)
Out
:
2
In
:
next
(
c
)
Out
:
3
又或者前面的斐波那契序列，我们也可以利用生成器的特点，惰性计算。
def
fib
(
n
,
a
=
0
,
b
=
1
)
:
for
i
in
range
(
n
)
:
yield
b
a
,
b
=
b
,
a
+
b
print
(
list
(
fib
(
5
)
)
)
# [1, 1, 2, 3, 5]
或者包含所有斐波那契序列的生成器
def
fib
(
)
:
a
=
0
b
=
1
while
True
:
yield
b
a
,
b
=
b
,
a
+
b
g
=
fib
(
)
for
i
in
range
(
101
)
:
print
(
next
(
g
)
)
4.3. 协程 coroutine
协程是生成器的一种高级方法，比进程、线程更轻量级，是在用户空间调度函数的一种实现，Python 3 的 asyncio 就是协程实现，已经加入到了标准库中，Python 3.5 使用 async、await 关键字直接原生支持协程。协程在现阶段来说比较复杂，后面会详细进行说明，这里提一下实现思路：
- 有两个生成器 A、B
- next(A) 后，A 执行到了 yield 语句后暂停，然后去执行 next(B),B 执行到 yield 语句也暂停，然后再次调用 next(A)，再次调用 next(B)
- 周而复始，就实现了调度的效果
- 还可以引入调度的策略来实现切换的方式
协程是一种非抢占式调度
4.4. yield from
在 Python 3.3 以后，出现了
yield from
语法糖。它的用法是
def
counter
(
)
:
yield
from
range
(
10
)
- yield from 后面需要一个可迭代对象
-
yield from iterable实际上等同于for item in iterable: yield item
当然
yield from
也可以结合生成器来使用，因为生成器也是一个可迭代对象啊。
def
fib
(
n
)
:
a
=
0
b
=
1
for
i
in
range
(
n
)
:
yield
b
a
,
b
=
b
,
a
+
b
def
counter
(
)
:
yield
from
fib
(
10
)
g
=
counter
(
)
print
(
list
(
g
)
)
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
生成器包生成器，真是妙极了！
