Python第四课----函数

1、内建函数：max（），reversed（）。
2、库函数：math.ceil。

def 函数名（参数列表）
  函数体（代码块）
  [return 返回值]
函数名就是标识符，命名要求一样。
语句块缩进四个空格。
函数中如果没有return语句，隐式会返回一个None值。
定义中的参数列表是形式参数，只是一种表达，简称形参。

def add(x,y):
  result = x+y
  return result
out = add(4,5)
print(out)

函数---->add，计算结果通过返回值返回、返回值可以使用变量接收，函数是可调用对象，callable（add）试一下，是通用的

1、参数调用时，传入的参数要和定义的个数匹配（可变例外）
2、位置参数：def f（x，y，z） 调用时：f（3，4，5），按照顺序传入实参
3、关键参数：def f（x，y，z） 调用时：f（x=3，y=4，z=5），使用形参名字传入实参的方式，顺序无所谓
4、传参：f（z=None，y=10，x=[1]）、f（（1，），z=6，x=4.1）、f（y=5，z=6，2）最后这种不行，位置参数必须在关键字参数之前传入

1、参数默认值：def f（x=4，y=5）：这个时候，x，y都有默认值，默认可以输出
2、参数非常多的时候，并不需要输出所有参数，有默认值就可以了

1、问题：有多个数，累加求和
    def add（nums）：----这样的话，nums需要是一个可迭代对象
2、可变位置参数（一个星号）一个形参可以匹配任意个参数x
    def add（*args）：----sum=0，for x in args：----sum+=x
3、可变关键字参数（两个星号）
def add（**kwargs）：
  for k，v in kwargs.items( )：
     print（“{}={}”.format(k,v)）
add（x=1，y=2）
只能用关键字调用，组成的是个字典
4、混合使用参数、可变参数：
    1、def  showconfig（username，password，**kwargs）
  2、def  showconfig（username，*args，**kwargs）
  3、def  showconfig（username，password=“mage”，*args，**kwargs）
  4、def fn(*args,x,y,**kwargs):---->这么写，调用必须对唯一关键词x、y进行关键字传参
  5、fn（*，x，y）强制将x，y变成唯一关键词
  6、fn（*agrs，x=5）默认值给了可以直接调用fn（）

1、fn（x，y）：
       return（x+y）
   fn（*（4，5））/*[4,5]/*{4,5}/fn（*range（1，3））/fn（（1，2）[0]，[3][0]）
2、字典解构fn（**{x：5，y：6}）或者fn（*d.keys（））或d.valus（）
3、def fn（*args）：
    print（args）
   fn（*[1,2,3]）
4、def fn(*args):
    sum = 0
    for x in args:
      sum += x
    print(sum)

1、一个标识符的可见范围，也就是变量，一般说变量的作用域

2、x = 5           x = 5
  def foo():         def foo():
  print(x)             x+=1
   foo()                                                print(x)
可执行，x为全局变量       foo()不可执行，下方的x+=1，实际上是重新定义变量x，但是并不存在

3、全局作用域，global变量，可以管辖下面的函数，但函数内部高度自治，自己管自己局部作用域，local变量，里面可以使用外部的变量，但本地变量，只能在内部使用，外部不可见

4、嵌套结构
def outer( ):                        def outer( ):
  o = 65                           o = 65
  def inner( ):                         def inner( ):
      print("inner { }".format(o))                o = 97
      print(chr(o))                       print("inner { }".format(o))
      print("outer { }".format(o))                print(chr(o))
  inner( )                             print("outer { }".format(o))
outer( )     打印65，65，A                    inner( )  
外部变量内部可用，但赋值即定义                                 outer( )打印结果65，97，a

x = 5
def foo( ):
   y = x+1
   x = 1
   print(x)
foo( )报错，赋值即定义，上面x用不上，下面的又没有定义就被y拿来使用

5、全局变量global
x = 5                                 def foo（）：
def foo（）：                            global x
   global  x                          x = 10
   x+=1                              x +=1     
将x声明为使用外部的全局作用域，外面必须有x的定义               这个x=10，是全局变量，是为外面定义一个变量

6、闭包
自由变量：未在本地作用域定义的变量，例如定义在外层函数作用域的变量
闭包：出现在嵌套函数中，指的是内层函数引用了外层函数的自由变量
def counter（）：
  c = [0]
  def inc( ):
    c[0] += 1
    return c[0]
  return inc
foo = counter( )
print(foo( ),foo( ))
c = 100
print(foo( ))   每次局部变量应该消失，但[ ]是引用对象，每次都会改变，借用的是引用类型

7、nonlocal关键字----关键字绝对不能被占用
使用了nonlocal关键字，将变量标记为在上级的局部作用域中定义，是上级的局部作用域，而不是全局作用域
函数调用为什么会循环count+=1？？？
def  counter（）：
   count = 0
   def inc（）：
     nonlocal  count
     count +=1
     return count
   return inc
foo = counter( )
print(foo( ),foo( ))     闭包内的函数，在外面foo调用的时候，保留了count这个变量，而且每次都执行了+1

8、函数默认值的作用域：（foo.__defaults__）使用两个下划线+defaults+两个下划线
def foo(xyz=[]):
  xyz.append(1)
    print(xyz)
print(foo(),id(foo))
print(foo.__defaults__)
print(foo(),id(foo))
print(foo.__defaults__)    
函数的默认值不会发生变化，缺省值不会改变，是个元组，但元组内的列表发生了改变，这是个引用

def foo(w,u="abc",z=123):
  u = "xyz"
  z = 456
  print(w,u,z)
print(foo.__defaults__)
foo("magedu")
print(foo.__defaults__)   
函数的默认值不会发生改变，重新赋值的展示在函数调用里

9、默认值的作用域用法：
def foo(xyz=[],u="abc",z=123):
  xyz=xyz[:]
  xyz.append(1)
  print(xyz)
foo()
print(foo.__defaults__)
foo()
print(foo.__defaults__)
foo([10])
print(foo.__defaults__)
foo([10,5])
print(foo.__defaults__)
xyz重新被赋值定义，做了拷贝，原xyz还是不变，默认值始终不变

def foo(xyz=None,u="abc",z=123):
  if xyz is None:
    xyz=[]
    xyz.append(1)
    print(xyz)
foo()
print(foo.__defaults__)
foo()
print(foo.__defaults__)
lst = [10]
foo(lst)
print(lst)
print(foo.__defaults__)
foo([10,5])
print(foo.__defaults__)
使用不可变类型默认值，如果使用none，则创建新列表，如果，传入一个列表，就修改这个列表，lst发生了变化，但是默认值一直没有发生变化，始终是None，abc，123的元组

def foo(x=None):
  if x == None:
    x = []
    x.append(1)
    return x
lst = foo()
a = foo(lst)
print(a)
一般这么写函数，lst=foo（）就会执行一次foo（），结果是[1]，a=foo（lst）会再执行一次，结果就是[1,1]

del或重新赋值

1、定义：
  (1）、非线性解构，每个元素可以有多个前驱和后继（这句话，是前驱0或1，后继多个）
 （2）、树是n≥0个元素的集合
  (3）、n = 0，则是空树，树的根Root没有前驱
 （4）、其余元素只能有一个前驱，多个后继
2、递归定义：
  (1）、有且只有一个特殊元素根，其余元素划分为m个互不相交的集合T1，T2.。。。Tm，每一个集合都是树，称为T的子树Subtree
  （2）、子树也有自己的根
3、树的概念                                                              
  （1）、结点，树中的数据元素，每个元素都是一个结点
 （2）、结点的度degree：结点拥有的子树的数目，称为度，记作d（v），B的度是1，C的度是2，D的度是3
 （3）、叶子结点，结点的度为0，则是叶子结点leaf、终端结点，末端结点
 （4）、分支结点，结点度不为0，则是分支结点  ABCDE
 （5）、分支，结点之间的关系，A和B的分支，关系，这条线
 （6）、内部结点，除掉根和叶子结点，中间的结点
 （7）、树的度：树内各结点，谁的度数大，树的度数就是多少，上图为3
 （8）、孩子（儿子Child）结点，结点的子树的根节点成为成为该结点的孩子
 （9）、双亲（父Parent）结点：一个结点是它各个子树的根结点的双亲
 （10）、兄弟结点（sibling）：具有相同双亲结点的结点
 （11）、祖先结点：从根结点到该结点所经分支上所有的结点。ABD都是G的祖先
 （12）、子孙结点：结点的所有子树上的结点都成为该结点的子孙，B的子孙是GDHI
 （13）、结点的层次（Level）：根结点为第一层，根的孩子是第二层，以此类推，记作L（v）
 （14）、树的深度（高度Depth）：树的层次的最大值，上图深度为4
 （15）、堂兄弟，双亲在同一层的结点
4、树的概念：
 （1）、有序树：结点的子树是有顺序的，不能交换
 （2）、无序树：结点的子树是无序的，可以交换
 （3）、路径：树的k个结点n1，n2，。。。nk，满足ni是n（i+1）的双亲，成为n1到nk的一条路径，就是一条线下来的，前一个是后一个的父结点，A-B-D-G
 （4）、路径长度：路径上结点数-1
 （5）、森林：m≥0颗不相交的树的集合 D、E、F，结点的子树集合就是森林
5、树的特点：
 （1）、唯一的根
 （2）、子树不相交
  （3）、除了根之外，每个元素只有一个前驱，0或多个后继
 （4）、根结点没有前驱，叶子结点没有后继
 （5）、如果vi是vj的双亲，则L（vi）=L（vj）-1，双亲比孩子Level小1
 （6）、堂兄弟的双亲不一定是兄弟

1、每个结点最多两颗子树：二叉树不存在度数大于二的结点
2、二叉树是有序树，左子树，右子树是有顺序的，不能交换
3、即使某个结点只有一棵树，也要确定它是左子树还是右子树
4、二叉树的五种形态
 （1）、空二叉树   
 （2）、只有根结点的二叉树
 （3）、根结点只有左子树
 （4）、根结点只有右子树
 （5）、根结点有左子树和右子树

1、左斜树：全是左子树
2、右斜树：全是右子树

1、一颗二叉树的所有分支结点都存在左子树和右子树，并且叶子结点只存在最下面一层，一个都不能少，左右完全对称
2、同样深度中，满二叉树结点最多
3、k为深度（1≤k≤n），则结点总数为2**k-1

1、若二叉树的深度为k，则二叉树的层数从1到k-1层的结点数都达到了最大个数，在第k曾的所有结点都集中在最左边，这就是完全二叉树（最后一层，从左到右，不能空）
2、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树 
3、H在左边，若E有一个分支结点，则不是，必须D有两个，E有一个左子树，才是完全二叉树

1、在二叉树的第i层上最多有2**（i-1）个结点
2、深度为k的二叉树，至多有2**k-1个结点
3、对于任意一颗二叉树T，如果其终端结点为n0，度数为2的结点为n2，则有n0=n2+1（叶子结点，是度数为2的结点加1）上图中，叶子结点n0=4（HEFG），n2=3（ABC）
4、叶子结点数-1就等于度数为2的结点数
   证明：n0+n1+n2=n（0叶子，1度数为1，2度数为2）：
      n0+n1+n2-1（一棵树的分支数为n-1（总数减去根结点））
      分支数还等于n0*0+n1*1+n2*2-----2n*2+n1
      2*n2+n1=n0+n1+n2-1---->n2=n0-1
5、高度为k的二叉树，至少有k个结点（左斜树）
7、具有n个结点的完全二叉树的深度为int（（log2n+1））n开方+1取整，或者math.ceil(log2(n+1))
8、如果有一颗n个结点的完全二叉树，可以按照层序编号
 （1）、如果i=1，则结点i是二叉树的根，无双亲，如果i>1，则其双亲是int（i/2），向下取整。就是子结点的编号整除2得到的就是父结点的编号。父节点如果是i，左孩子结点就是2i，右孩子就是2i+1
 （2）、如果2i>n，则结点无左孩子，即结点i为叶子结点，否则其左孩子结点存在编号为2i
 （3）、如果2i+1>n，则结点i无右孩子，否则右孩子存在编号为2i+1

1、Local----先本地作用域，调用结束消亡
2、Enclosing，嵌套函数的闭包的外部函数的命名空间
3、Global----全局，解释器退出时消亡
4、Build-in 内置模块的命名空间，解释器启动到退出，就是生命周期，print、open等

1、函数执行流程：              全局帧中生成foo1、2、3、main函数对象
def foo1(b,b1=3):              main函数调用
  print("foo1 called",b,b1)      main中查找内建函数print压栈，将常量字符串压栈，调用函数，弹出栈顶
def foo2(c):                  main中全局查找函数foo1压栈，将常量100，101压栈，调用foo1函数，
  foo3(c)                  创建栈帧，print压栈，字符串和常量压栈，调用函数，弹出栈顶，返回值。  
  print("foo3 called",c)            后续全部类似
def foo3(d):
  print("foo3 called",d)
def main():
  print("main called")
  foo1(100,101)
  foo2(200)
  print("main called")
main()

1、函数直接或间接调用自身，就是递归
2、递归需要边界条件
3、当不满足边界条件时，递归前进，当满足边界条件时，递归结束。
4、使用import sys  ----sys.getrecursionlimit( )来查看递归深度
5、sys.setrecursionlimit(2000)修改递归深度
6、递归的性能，不高，需要将条件优化，循环稍微复杂，不是死循环，最终可得结果
7、少用递归

1、没有名字的函数
2、Python借助lambda表达式构建匿名函数
  (1）、lambda 参数列表：表达式
  lambda x：x**2-----这是生成函数，x是参数，x**2是表达式
 （lambda x：x**2）（4）这是直接调用了
  foo = lambda x，y ：（x+y）**2  ## 不推荐用法
  foo（4，5）---这样就建议def foo（x，y）
3、使用lambda关键字来定义匿名函数
4、不需要return，因为表达式就是返回结果，只能写一行，单行函数
5、用途，高阶函数传参时，使用lambda表达式，能简化代码
6、(lambda *args:(x for x in range(5)))(*range(5))依然是参数加传参调用的方式
7、print((lambda :0)())
  print((lambda x,y=3:x+y)(5))
  print((lambda x,y=3:x+y)(3,6))
  print((lambda x,*,y=3:x+y)(3))
  print((lambda x,*,y=3:x+y)(3,y=5))
  print((lambda *args:(x for x in args))(*range(5)))
  print((lambda *args:[x for x in args])(*range(5)))
  print((lambda *args:{x for x in args})(*range(5)))

1、生成器函数，有yield语句就是生成器函数，yield语句拨一下转一下，每次执行一下就停止了，但函数还在，只是暂停，让出给下一句

  def gen():
    print("line 1")
    yield 1
    print("line 2")
    yield 2
    print("line 3")
    return 3
  next(gen())
  next(gen())
  g = gen()
  print(next(g))
  print(next(g))
  # print(next(g))
  print(next(g,"End"))   End类似于缺省值，随便加，不会报异常，会打印End

2、yield的无限循环
    def nums():         c = nums（），c是个生成器，无限循环
       i = 0
     while True:
       i+=1
       yield i
    def inc(c):
     return next(c)
    c = nums()
    print(inc(c))
    print(inc(c))
    print(inc(c))
    
    def nums():          c = nums( ) ，c赋值即定义，每次都是重新赋值
     i = 0
     while True:
       i+=1
       yield i
    def inc():
     c = nums()
     return next(c)
      print(inc())
    print(inc())
    print(inc())
    
    def inc():                             嵌套函数
     def nums():
       i = 0
         while True:
         i+=1
          yield i
          c = nums()
      return lambda :next(c)
    foo = inc()
    print(foo())
    print(foo())
                        
    def inc():                              等同于上面
     def nums():
       i = 0
        while True:
          i += 1
          yield i         
      c = nums()    
      def _inc():
         return next(c)
      return _inc
        
    foo = inc()
    print(foo())
    print(foo())

3、处理递归问题

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

4、协程coroutine

（1）、生成器的高级用法
（2）、比进程、线程轻量级
（3）、是在用户空间调度函数的一种实现
（4）、实现思路
   有两个生成器A，B
   next（A）后，A执行到了yield语句暂停，然后去执行next（B），
   B执行到yield语句也暂停，然后再次调用next（A），再调用next（B），
   周而复始，实现调度效果可以引入调度的策略来实现切换的方式
（5）、协程时一种非抢占式调度

def inc():
  for x in range(1000):
     yield x
foo = inc()
  print(next(foo))
  print(next(foo))
等价于：
def inc(():
  yield from range(1000)
foo = inc()
print(next(foo))

6、从可迭代对象中一个个拿元素

def counter（n）：
  for x in range（n）：
     yield x
def inc（n）：
  yield from counter（n）
foo = inc（10）
print（next（foo））
counter（）是一个迭代器，下面inc调用一个迭代器，也可以不是迭代器，list这些都行

import random
def nums(*args):
    print(args)
    return max(args),min(args)
print(*nums(*[random.randint(10,20) for _ in range(10)]))

2、递归函数，斐波那契

import datetime
start = datetime.datetime.now()
def fib(n):
    return 1 if n < 2 else fib(n-1) + fib(n-2)
for i in range(35):
    print(fib(i),end=" ")

# pre = 0
# cur = 1
# print(pre,cur,end=" ")
# def fib(n,pre=0,cur=1):
#     pre,cur=cur,pre+cur
#     print(cur,end=" ")
#     if n == 2:
#         return 1
#     fib(n-1,pre,cur)
# print(fib(5))
delat = (datetime.datetime.now() - start).total_seconds()
print()
print(delat)

# a = 1234
# length = len(str(a))
# def nums(n,j=[]):
#     if n == 0 :
#         return
#     j.append(str(a)[n-1])
#     nums(n-1)
#     return j
# print(nums(length))

# data = str(1234)
#
# def revert(x):
#     if x == 0:
#         return ""
#     return data[x-1]+revert(x-1)
# print(revert(len(data)))

# a = str(1234)
# def nums(n):
#     if n == 0:
#         return ""
#     return a[n-1]+nums(n-1)
#     # print(a[n-1],end="")
#     # nums(n-1)
#     # return ""
# print(nums(len(a)))

a = str(1234)
length = len(a)
def nums(n,t=[]):
    if n == 0:
        return ""
    t.append(a[n-1])
    return a[n-1]+nums(n-1)
print(nums(length))

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

# def factorial(n,pre=1):
#     pre = pre*n
#     if n == 1:
#         return pre
#     return factorial(n-1,pre)
# print(factorial(5))

def fact(n,answer = 1):
    answer *=n
    if n == 1:
        return answer
    return fact(n-1,answer)
print(fact(5))

# def fact(n):
#     if n == 1:
#         return 1
#     return n*fact(n-1)
# print(fact(5))

def nums(n,pre=1):
    pre = 2*(pre+1)
    if n == 1:
        return pre
    return nums(n-1,pre)
print(nums(9))

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