python 15day--递归函数与匿名函数

一、递归函数

1、递归调用：函数嵌套调用的一种特殊形式，函数在调用时直接或者间接调用了自身，就是递归调用

 1 #直接调用本身
 2 def f1():
 3     print('from f1')
 4     f1()
 5 f1()
 6 
 7 #间接调用本身
 8 def f1():
 9     print('from f1')
10     f2()
11 
12 def f2():
13     print('from f2')
14     f1()
15 f1()
16 
17 # 调用函数会产生局部的名称空间，占用内存，因为上述这种调用会无需调用本身，python解释器的内存管理机制为了防止其无限制占用内存，对函数的递归调用做了最大的层级限制
18 四 可以修改递归最大深度
19 
20 import sys
21 sys.getrecursionlimit()
22 sys.setrecursionlimit(2000)
23 
24 def f1(n):
25     print('from f1',n)
26     f1(n+1)
27 f1(1)
28 
29 虽然可以设置，但是因为不是尾递归，仍然要保存栈，内存大小一定，不可能无限递归，而且无限制地递归调用本身是毫无意义的，递归应该分为两个明确的阶段，回溯与递推
30 
31 详解

2、递归调用应该分为两个明确的阶段：递推，回溯

 1 #1、递归调用应该包含两个明确的阶段：回溯，递推
 2     回溯就是从外向里一层一层递归调用下去，
 3         回溯阶段必须要有一个明确地结束条件，每进入下一次递归时，问题的规模都应该有所减少（否则，单纯地重复调用自身是毫无意义的）
 4 
 5     递推就是从里向外一层一层结束递归
 6 
 7 #2、示例+图解。。。
 8 # salary(5)=salary(4)+300
 9 # salary(4)=salary(3)+300
10 # salary(3)=salary(2)+300
11 # salary(2)=salary(1)+300
12 # salary(1)=100
13 #
14 # salary(n)=salary(n-1)+300     n>1
15 # salary(1) =100                n=1
16 
17 def salary(n):
18     if n == 1:
19         return 100
20     return salary(n-1)+300
21 
22 print(salary(5))

3、 python中的递归效率低且没有尾递归优化：

 1 #python中的递归
 2 python中的递归效率低，需要在进入下一次递归时保留当前的状态，在其他语言中可以有解决方法：尾递归优化，即在函数的最后一步（而非最后一行)调用自己，尾递归优化：http://egon09.blog.51cto.com/9161406/1842475
 3 但是python又没有尾递归，且对递归层级做了限制
 4 
 5 #总结递归的使用：
 6 1. 必须有一个明确的结束条件
 7 
 8 2. 每次进入更深一层递归时，问题规模相比上次递归都应有所减少
 9 
10 3. 递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）

4、递归实现斐波那契数列

 1 # Filename : test.py
 2 # author by : www.runoob.com
 3  
 4 def recur_fibo(n):
 5    """递归函数
 6    输出斐波那契数列"""
 7    if n <= 1:
 8        return n
 9    else:
10        return(recur_fibo(n-1) + recur_fibo(n-2))
11  
12  
13 # 获取用户输入
14 nterms = int(input("您要输出几项? "))
15  
16 # 检查输入的数字是否正确
17 if nterms <= 0:
18    print("输入正数")
19 else:
20    print("斐波那契数列:")
21    for i in range(nterms):
22        print(recur_fibo(i))

二、匿名函数

1、什么是匿名函数

1 匿名就是没有名字
2 def func(x,y,z=1):
3     return x+y+z
4 
5 匿名
6 lambda x,y,z=1:x+y+z #与函数有相同的作用域，但是匿名意味着引用计数为0，使用一次就释放，除非让其有名字
7 func=lambda x,y,z=1:x+y+z 
8 func(1,2,3)
9 #让其有名字就没有意义

2、有名函数与匿名函数的对比：

#有名函数与匿名函数的对比
有名函数：循环使用，保存了名字，通过名字就可以重复引用函数功能

匿名函数：一次性使用，随时随时定义

应用：max，min，sorted,map,reduce,filter