[toc]

python 函数(三)

变量名解析原则LEGB

• Local本地作用域、局部作用域的local命名空间,函数调时创建,调用结束消亡;
• Enclosing, Python2.2时引入了嵌套函数,实现了闭包,这个就是嵌套函数的外部函数的全名空间;
• Global,全局作用域,即一个模块的命名空间。模块被import 时创建，解释器退出时消亡;
• Build-in,内置模块的命名空间,生命周期从python解释器启动时创建 到解释器退出时消亡。例如 print(open)，print 和open都是内置的变量;
• 所以一个名词的查找顺序就是LEGB;

函数执行流程

def foo1(b,b1=3):
    print("foo1 called",b,b1)

def foo2(c):
    foo3(c)
    print("foo2 called",c)

def foo3(d):
    print("foo3 called", d)

def main():
    print("main called")
    foo1(100,101)
    foo2(200)
    print("main ending")

main()
main called
foo1 called 100 101
foo3 called 200
foo2 called 200
main ending

• 全局帧中生成foo1、foo2、foo3、main函数对象;
• main函数调用;
• main中查找内建函数print压栈，将常量字符串压栈，调用函数，弹出栈顶;
• main中全局查找函数foo1压栈，将常量100、101压栈，调用函数foo1，创建栈帧。print函数压栈，字符串和亦是b、b1压栈、调用函数，弹出栈顶，返回值。
• main中全局查找foo2函数压栈，将常量200压栈，调用foo2，创建栈帧。foo3函数压栈，变量c引用压栈，调用foo3，创建栈帧。foo3完成print函数调用后返回。foo2恢复调用。执行print后，返回值。main中foo2调用结束弹出栈顶，继续执行print函数调用，弹出栈顶。main函数返回。

递归Recursion

• 函数直接或者间接调用自身就是 递归;
• 递归需要有边界条件、递归前进段、递归返回段;
• 递归一定要有边界操作;
• 当办界条件不满足的时候，递归前进;

• 当边界条件满足的时候，递归返回;

• 斐波那契数列Fibonacci number: 1,1,2,3,5,8,13,21,34,55,89,144,...

• 如果设F(n)为该数列的第n项(n∈N* )，那么这句话可以写成如下形式:F(n)=F(n-1)+F(n-2)
• F(0)=0, F(1)=1,F(n)=F(n-1)+F(n-2)

pre = 0
cur = 1
print(pre,cur,end=' ')
n = 10
for i in range(n-1):
    pre, cur = cur,pre+cur
    print(cur,end=' ')

#结果: 0 1 1 2 3 5 8 13 21 34 55

递归实现

F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)

def fib(n):
    return 1 if n < 2 else fib(n-1) + fib(n-2)
for i in range(10):
    print(fib(i), end=' ')
# 1 1 2 3 5 8 13 21 34 55

解析:

fib(3) + fib(2)
fib(3) 调用fib(3)、fib(2)、fib(1)
fib(2) 调用fib2(2)、fib(1)
fib(1) 是边界

递归要求

• 递归一定要有退出条件，递归调用一定要执行到这个退出条件。没有退出条件的递归调用，就是无限调用;
• 递归调用的深度不宜过深;

1. Python 对递归调用的深度做了限制，以保护解释器;
2. 超过递归深度限制，抛出RecurisonError: maxinum recursion depth exceeded超出最大深度;
3. sys.getrecursionlimit()

In [1]: import sys
In [2]: print(sys.getrecursionlimit())
3000
In [4]: sys.setrecursionlimit(1000)
In [5]: print(sys.getrecursionlimit())
1000

优化改进

fib函数和循环的思想类似;
参数n是边界条件，用n来计数;
上一次的计算结果直接作为函数的实参;
效率很高;
和循环比较，性能相近。所以并不是递归一定是效率底下，但是递归有深度的限制;

pre = 0
cur = 1
print(pre, cur)

def fib(n, pre=0,cur=1):
    pre, cur = cur, pre + cur
    print(cur, end=' ')
    if n == 2 :
        return
    fib(n-1, pre, cur)

fib(10)
# 输出 1 2 3 5 8 13 21 34 55

间接递归

如

def foo1():
    foo2()

def foo2():
    foo1()

foo1()

间接递归，是通过别的函数调用了函数自身;
但是，如果构成了循环递归调用是非常危险的，但是往往这种情况下代码复杂的情况下，还是可能发生这种调用。要用代码的规范来避免这种递归调用的发生。

递归总结

• 递归是一种很自然的表达，符合逻辑思维;
• 递归相对运行效率低，每一次调用函数都要开辟栈帧;
• 递归有深度限制，如果递归层次太深，函数反复压栈，栈内存很快就溢出了;
• 如果是有限次数的递归，可以使用递归调用，或者使用循环代替，循环代码稍微复杂一些，但是只要不是死trggsk以多次迭代直至算出结果；
• 绝大多数递归，都可以使用循环实现;
• 即使递归代码很简洁，但是能不用则不用递归。

递归练习

• 求n的阶乘

def fac(n):
    if n == 1 :
        return 1
    return n * fac(n-1)

def fac1(n, p =1 ):
    if n == 1:
        return p
    p *= n
    print(p)
    fac1(n-1,p)
    return p

def fac2(n, p = None):
    if p is None:
        p = [1]
    if n == 1 :
        return p[0]
    p[0] *= n
    print(p[0])
    fac2(n-1, p)
    return p
n = 10
print(fac(n))
print(fac1(n))
print(fac2(n))
# 输出
3628800
10
90
720
5040
30240
151200
604800
1814400
3628800
10
10
90
720
5040
30240
151200
604800
1814400
3628800
[3628800]

• 将一个数逆序放入列表中，例如1234 => [4,3,2,1]

num = 1234
def revert(num, target=[]):
    if num:
        target.append(num[len(num) -1]) # target.append(num[-1:])
        revert(num[:len(num) -1])
    return target
print(revert(str(num)))

• 解决猴子吃桃问题

猴子第一天摘下苦干个桃子，当即吃了一半，还不过瘾，又多吃了一个，第二天早上又剩下的桃子吃掉一半，又多吃了一个。以后每天早上都各吃了前一天剩下的一半零一个。到第10天早上想吃时，只剩下一个桃子了。求第一天共摘多少个桃子。

def peach(days=10):
    if days == 1:
        return 1
    return(peach(days-1)+1)*2
print(peach())

注意这里必须是10， 因为return(peach(days-1)+1)*2 立即拿不到结果，必须通过再一次进入函数时判断是不是到了最后一天。
也就是当前使用的值是由下一次函数调用得到，所以要执行10次函数调用。

换种方式表达

def peatch(days=1):
    if days == 10:
        return 1
    return(peatch(days+1)+1)*2
print(peatch())

匿名函数

Python 借助Lambda表达式构建匿名函数

例

In [1]: (lambda x:x*2)((4,2))
Out[1]: (4, 2, 4, 2)

• 使用lambda 关键字来定义匿名函数;
• 参数列表不需要小括号;
• 冒号是用来分割参数列表和表达式的;
• 不需要使用return，表达式的值，就是匿名函数返回值;
• lambda表达式(匿名函数)只能写在一行上，被称为单行函数
• 用途
  在高阶函数传参时，使用lambda表达式，往往能简化代码;

print((lambda :0)())
print((lambda x,y=3: x + y )(5))
print((lambda x,y=3: x + y)(5,6))
print((lambda x, *, y=30: x + y)(5))
print((lambda x, *, y=30: x + y)(5, y=10))
print((lambda *args: (x for x in args))(*range(5)))
print((lambda *args:[x+1 for x in args])(*range(5)))
print((lambda *args: [x + 2 for x in args])(*range(5)))
print((lambda *args: { x + 2 for x in args })(*range(5)))
###高阶函数
lst = [x for x in (lambda *args: map(lambda x: x+1,args))(*range(5))]
print(lst)
lst2 = [x for x in (lambda *args: map(lambda x:(x+1,args),args))(*range(5))]
print(lst2)

0
8
11
35
15
<generator object <lambda>.<locals>.<genexpr> at 0x10742dcf0>
[1, 2, 3, 4, 5]
[2, 3, 4, 5, 6]
{2, 3, 4, 5, 6}
[1, 2, 3, 4, 5]
[(1, (0, 1, 2, 3, 4)), (2, (0, 1, 2, 3, 4)), (3, (0, 1, 2, 3, 4)), (4, (0, 1, 2, 3, 4)), (5, (0, 1, 2, 3, 4))]

生成器

• 生成器generator
  生成器指的是生成器对象，可以由生成器表达式得到，也可以使用yeild关键字得到一个生成器函数，调用这个函数得到一个生成器对象

• 生成器函数
  函数体中包含yield语句的函数，返回生成器对象;
  生成器对象，是一个可迭代对象，是一个迭代对象;
  生成器对象，是延迟计算、惰性求值的。

def inc():
    for i in range(5):
        yield i
print(type(inc))
print(type(inc()))
x = inc()
print(type(x))
print(next(x))
for m in x:
    print(m, '*')
for m in x:
    print(m, '**')
# 输出
<class 'function'>
<class 'generator'>
<class 'generator'>
0
1 *
2 *
3 *
4 *

In [1]: y = (i for i in range(5))
In [2]: print(type(y))
<class 'generator'>
In [3]: print(next(y))
0
In [4]: print(next(y))
1

• 普通的函数调用fn()， 函数会立即执行完毕，但是生成器函数可以使用next函数多次执行;
• 生成器函数等价于生成器表达式，只不过生成器函数可以更加的复杂;

In [5]: def gen():
   ...:     print('line 1')
   ...:     yield 1
   ...:     print('line 2')
   ...:     yield 2
   ...:     print('line 3')
   ...:     return 3
In [6]: next(gen())
line 1
Out[6]: 1

In [7]: next(gen())
line 1
Out[7]: 1
In [8]: g = gen()
In [9]: print(next(g))
line 1
1
In [10]: print(next(g))
line 2
2
In [11]: print(next(g))
line 3
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-11-1dfb29d6357e> in <module>()
----> 1 print(next(g))
StopIteration: 3
In [12]: print(next(g, 'End'))
End

• 在生成器函数中，使用多个yield语句，执行一次后会暂停执行，把yeild表达式的值返回;
• 再次执行会执行到下一个yield语句;
• return语句依然可以终止函数运行,但是return语句的返回值不能被获取到;
• return会导致无法继续获取一下个值，抛出StopIteration异常;
• 如果函数没有显示的return语句，如果生成器函数执行到结尾，一样会抛出StopIteration异常;

生成器函数

• 包含yield语句的生成器函数生成生成器对象，生成器函数的函数体不会立即执行
• next(generator)会从函数的当前位置向后执行到之后踫到的第一个yeild语句，会弹出值，并暂停函数执行;
• 再次调用next函数，和上一条一样的处理过程;
• 没有多余的yield语句的能被执行，继续调用next函数，会抛出StopIteration异常;

生成器应用

In [13]: def counter():
    ...:     i = 0
    ...:     while True:
    ...:         i +=1
    ...:         yield i
In [14]: def inc(c):
    ...:     return next(c)
In [15]: c = counter()
In [16]: print(inc(c))
1
In [17]: print(inc(c))
2
In [18]: print(inc(c))
3
In [19]: print(inc(c))
4

In [21]: def counter():
    ...:     i = 0
    ...:     while True:
    ...:         i += 1
    ...:         yield i
    ...:

In [22]: def inc():
    ...:     c = counter()
    ...:     return next(c)
In [23]: print(inc())
1
In [24]: print(inc())
1
In [25]: print(inc())
1

计数器

def inc():
    def counter():
        i = 0
        while True:
            i +=1
            yield i

    c = counter()
    return lambda : next(c)
foo = inc()
print(foo())
print(foo())
print(foo())
# 输出
1
2
3

lambda 表达式是匿名函数
return 返回的是一个匿名函数
等价于下面的代码

def inc():
    def counter():
        i = 0
        while True:
            i +=1
            yield i

    c = counter()
    def _inc():
        return next(c)
    return _inc
foo = inc()
print(foo())
print(foo())
print(foo())

处理递归问题

def fib():
    x = 0
    y = 1
    while True:
        yield y
        x,y = x, x+y
foo = fib()
for _ in range(5):
    print(next(foo))
for _ in range(100):
    next(foo)
print(next(foo))

等价于下面的代码

pre = 0
cur = 1
print(pre, cur, end=' ')
def fib1(n, pre=0, cur=1):
    pre, cur = cur, pre + cur
    print(cur, end=' ')
    if n ==2 :
        return
    fib1(n-1,pre,cur)

• 协程coroutine

1. 生成器的高级用法 ;
2. 比进程、线程轻量级;
3. 是在用户空间调度函数的一种实现;
4. Python3 asyncio就是协程实现，已经加入到标准库;
5. Python3.5使用async、await关键字直接原生支持协程;

• 协程高度器实现思路;

1. 有2个生成器A、B
2. next(A)后，A执行到了yeild语句暂停，然后去执行next(B)，B执行到yield语句也暂停，然后再次调用next(A)，再调用next(B)在，周而复始，就实现了调度的效果;
3. 可以引入调度的策略来实现切换的方式;

• 协程是一种非抢占调度

yield from

• 举例

In [26]: def inc():
    ...:     for x in range(1000):
    ...:         yield x
    ...:

In [27]: foo = inc()

In [28]: print(next(foo))
0
In [29]: print(next(foo))
1
In [30]: print(next(foo))
2

等价于下面的代码

In [31]: def inc():
    ...:     yield from range(1000)
In [32]: foo = inc()
In [33]: print(next(foo))
0
In [34]: print(next(foo))
1
In [35]: print(next(foo))
2

• yield from 是Python 3.3 出现的新的语法

• yield from iterable 是 for item in iterable: yield item 形式的语法粮

• 可迭代对象中一个个拿元素

In [36]: def counter(n):
    ...:     for x in range(n):
    ...:         yield x
In [37]: def inc(n):
    ...:     yield from counter(n)
In [38]: foo = inc(10)
In [39]: print(next(foo))
0
In [40]: print(next(foo))
1
In [41]: print(next(foo))
2

格言

知止而后有定，定而后能静，静而后能安，安而后能虑，虑而后能得 数语，尽矣;