一、递归函数

1.1 概念

• 递归是解决问题的一种方式，它的整体思想，是将要给大的问题分解为一个小的问题，直到问题无法分解时，再去解决问题。
• 递归函数有2个条件：
  • 基线条件 ： 问题可以被分解为最小问题，当满足基线条件时，再去解决问题，递归就不再执行了。
  • 递归条件 ： 可以将问题继续分解的条件。

1.2 案例分析什么时递归？

分析：求取 10的阶乘
1 的阶乘 1! = 1
2 的阶乘 2! = 1 * 2
3 的阶乘 3! = 1 * 2 * 3
……
10的阶乘 10! = 1 * 2 * 3 * 4……10

n = 1
for i in range(1, 11):
      n *= i
print(10)

def fun(n):
    r = 1
    for i in range(1, 11):
        r *= i
    return r

上面两种方式都不属于递归，就是一个普通的循环。那么什么样才是递归呢 ？

从前有座山，山上有座庙，庙里有个老和尚和小和尚，老和尚对小和尚说……
从前有座山，山上有座庙，庙里有个老和尚和小和尚，老和尚对小和尚说……
从前有座山，山上有座庙，庙里有个老和尚和小和尚，老和尚对小和尚说……

这种情况就是递归：简单理解就是自己调用自己。
总结： 递归函数就是在函数中自己调用自己。

使用递归求 10的 阶乘~
10! = 10 *9!
9! = 9 * 8!
……
2！= 2 *1
1！= 1
推导结论： n! = n * (n-1)!

def fun(n):  # fun(n) 是为了求取n 的阶乘
def  fun(n):
    if n == 1:
        return 1
    return n * fun(n-1)

print(fun(10))

过程分析：
首先 n=10 时，打印的fun(10)的运行结果；
fun(10)= 10 * fun(9), 那么fun(9) 又可以被分解为 9 * fun(8),；
一直到被分解为 n =1时就不能再分解，返回 1。
最终为 9 8 * 7 6 * 5 *4 * 3 *2 *1 的结果。就是10 的阶乘。

1.3 练习

（1）求任意数的任意次幂
分析：
10 ** 5 = 10 * 10 **4
10 ** 4 = 10 * 10 **3
10 ** 3 = 10 * 10 **2
10 **1 = 10

def fun(n, m):
    if m == 1:
      return n
    return  n * fun(n, m-1)

print(fun(10, 6))
----------------输出--------------
1000000

（2）回文字符串

• 回文字符串，从左到由于从右到左读都是一样的。
  分析：2种情况
  123456789987654321　　　12345678987654321
  　2345678998765432　　　　234567898765432
  　　34567899876543　　　　　3456789876543
  　　　　　99　　　　　　　　　　　　9
• 首先，基线条件，分别从字符串两边开始取值，直到到最后一个，字符串还剩1个或2个一样的，因此我们可以得到递归的基线条件为 len(str) < 2 才行。
• 其次，递归条件，通过切片取值，拿到最外层的2个索引的值。

def fun(s):
    if len(s) < 2:
      return True
   elif  s[0] != s[-1]:
      return False
   return fun(s[1:-1])   # 返回值，切片取字符串索引 1 到 -1，因为列表特性取不到结尾，所以取得前一个值。即去除最外层２个字符串。

print(fun('123456789987654321'))
print(fun('12345678987654321'))
print(fun('12'))
print(fun('1'))
True
True
False
True

二、高阶函数

2.1 什么是高阶函数 ？

• 接收函数对象作为参数
• 将别的函数对象作为返回值返回的函数就是高阶函数。
  满足以上条件之一就是高阶函数。
  比如上面的判断回文字符串的递归函数：

def fun(s):
  if len(s) < 2:
    return True
  elif s[0] != s[1]
    return False
  return fun(s[1:-1])
print('1234567890')

没有接受函数做参数，同时 return = fun(s[1:-1])，返回值就是 f(s) ，因此没有调用其他的函数作为返回值，因此不是高阶函数。

2.2 定义高阶函数

def fun1(i):
    if i % 2 == 0:
        return True

def fun2(fn):
    list1 = []
    for i in  range(1, 101)
        if fn(i):       # fn(i)  这里fn 是形参，形参等于实参，fn=fun1, 那么 fn(i)==fun1(i)
            list1.append(i)
    return list1

print(fun2(fun1))

• 注意： fn(i) ，fn 是 fun2()的形参，形参等于实参，那么fn = fun1，即 fn(i) = fun1(i)
• fun2(fun1) 实现了将目标函数 fun1 当作变量传递到了 fun2() 里面来。fun1就是一个对象，里面存储的就是 fun1()函数的功能。

• 那么 if fn(i): 其实就是执行 fun1(i), 也就是调用 fun1(i), 如果 return True ，就继续执行list1.append(i)，
  因此符合高阶函数的要求。

  
  
  图片.png

注意：函数调用函数也不一定是 高阶函数！
比如上面的例子：

def fun1(i):
    if i % 2 == 0:
      return True

def fun2(fn):
    list1 = []
    for i in range(1, 101):
        if fun1(i):    #### 这里调用的是 fun1()
            list1.append(i)
    return list1

print(fun())  

同样实现功能，但是不满足高阶函数的2个条件，所以不是高阶函数。

三、匿名函数

3.1 匿名函数介绍

• 有些简单的函数，实现一些简单功能之后，我们也不会再使用，就会占位，那其他人要去定义的时候还要去查询确认，浪费资源，而实际生生产环境，都是小组协同开发一个项目，为了提高效率，我们尽量使用匿名函数。
  匿名函数的功能：
  1） 防止重名
  2） 不用再去定义函数，使用方便
  3） 可以作为一个传递的工具

3.2 lambda 函数

• lambda 函数就是匿名函数
  比如，我们之前筛选出偶数，我们就不用去单独定义一个函数实现这个功能了~
• lambda 语法： lambda 参数：表达式

print((lambda a, b: a + b)(1,2))
# 前面括号 a, b 就是形参，后面括号(1, 2) 就是实参~

• 前面括号里面 a,b 就是形参，后面括号传递实参。

• 案例解析：

list1 = [1, 2, 3, 4, 5, 6, 7, 8]
s = lambda a: a % 2 ==0
# print((lambda a: a % 2 ==0)(list1))  # list 无法传递给lambda，需要取处理list 里面的值。
# filter  两个参数，第一个参数是过滤规则，第二个参数是过滤的数据
## 这里就需要使用 filter() 过滤规则，将给出的过滤规则，将过滤数据返回出来。
s = lambda a: a % 2 == 0
print(list(filter(s, list1)))
----------------输出--------------
[2, 4, 6]

四、闭包

• 将函数作为返回值也是高阶函数，也称为闭包。
• 闭包的好处
  • 通过闭包可以创建一些只有当前函数能访问的变量
  • 可以将一些私有数据藏到闭包中。
• 形成闭包的条件
  • 函数嵌套。
  • 将内部函数作为返回值返回。
  • 内部函数和必须要使用到外部函数的变量。

注意： 闭包用多了会导致占用内存较高，生产慎用~

# 定义一个外部函数
def fun_out(num1):
    
    # 定义一个内部函数
    def fun_inner(num2):
          res = num1 + num2
          print(res)

    return fun_inner

f = fun_out(1)
print(f(2))
------------输出-----------
3
None

分析：

1. 因为函数的调用等于函数的返回值，f = fun_out(1) = fun_inner
2. 那么 f() = fun_inner() = fun_out(1)()，因此 调用到 f()=fun_inner() ,调用内部函数，内部函数没有返回值，结果返回 None。
3. 内部函数调用 ： f(2) = fun_inner(2) = fun_out(1)(2), print(f(2)) 。执行内部函数 print(1+2) =3

综上，有函数嵌套，内部函数作为返回值返回 （return fun_inner）, 内部函数使用外部函数的参数 num1，所有上面就是一个 闭包。

特性： 保证被内部使用的外部变量不被销毁

案例2： 修改外部函数的变量。

# 定义外部函数
def fun_out(num1):

    # 定义一个内部函数
    def fun_inner(num2):
        num1 = 10   # 这里num1 = 10 是重新赋值,与形参num1 不是一个同一个概念。
        # 类似于
        # b = 1
        # def fun3(a):  # a = b
        #       a = 0
        #       print(a)
        # fun(b)
        # print(b)
        res = num1 + num2
        return res

    print(num1)
    fun_inner(1)
    print(num1)
    return fun_inner

f = fun_out(1)
-----------输出--------------
1
1

分析：

1. 首先，程序执行 fun_out(1) , 调用外部函数 fun_out(1), 没有调用内部函数，继续向下执行，print(1) = 1
2. 然后，fun_inner(1) 调用内部函数 fun_inner(1) ,执行内部函数 res =num1+ num2，return = res=11。
3. 然后， 继续，print(num1) 。但是此时 num1 并不是外部函数的形参，只是重新赋值，不会被外部函数所使用，所以num1 依然是 1 ，print (1) = 1
4. 最后，函数执行完成，返回 fun_inner。

图片.png

因此，上面函数中，不满足第三个条件，内部函数没有使用到外部函数的变量，不是闭包。

• nonlocal 修改外部变量
  作用： 告诉解释器，这里使用的不是本地的变量，而是外部变量。

   def fun_inner(num2):
        # global num1 # 为啥不用 global1 呢？ 因为global 成了全局变量。也不符合要求。
        nolocal num1  # 告诉解释器，这里使用的不是本地变量。而是外部变量num1.
        num1 = 10 
        res = num1 + num2
        return res

    print(num1)
    fun_inner(1)
    print(num1)
    return fun_inner

f = fun_out(1)

• 所以这里才是闭包。

练习：
猴子吃桃问题（递归）
猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，有多吃了一个，第二天早上又将剩下的桃子吃掉了一半，又多吃了一个，以后每天早上都吃了前一天剩下的一半零一个。到了第10天早上想再吃时，见到只剩下一个桃子了，请问一共摘了多少个 桃子 ？

分析：递归方法
第10天剩下的桃子： 1
第9天剩下的桃子： （1+1）*2
第8天剩下的桃子： (( 1 + 1) * 2 +1) * 2
第7天剩下的桃子： ((( 1 + 1) * 2 +1) * 2+1) *2
依次类推
规律：当天剩下的桃子数 = （后面一天的桃子数+1） * 2
即 f(n) = (f(n+1) +1) * 2

因此递归函数就是：

def  count(n):
     if  n == 10:
        return 1
    else:
        return  (count(n+1)  +1  ) * 2

print(count(1)) 
------- 输出----------
1534