一、递归函数
""" 自己调用自己的函数就是递归 递: 去 归: 回 一去一回就是递归 """
例、
def digui(n): print(n,"<====1===>") if n > 0: digui(n-1) print(n,"<====2===>") digui(5)
代码解析：
""" # 代码解析: 去的过程: n = 5 print(5,"<====1===>") 5>0 条件成立-> digui(5-1) => digui(4) 代码阻塞在第13行 n = 4 print(4,"<====1===>") 4>0 条件成立-> digui(4-1) => digui(3) 代码阻塞在第13行 n = 3 print(3,"<====1===>") 3>0 条件成立-> digui(3-1) => digui(2) 代码阻塞在第13行 n = 2 print(2,"<====1===>") 2>0 条件成立-> digui(2-1) => digui(1) 代码阻塞在第13行 n = 1 print(1,"<====1===>") 1>0 条件成立-> digui(1-1) => digui(0) 代码阻塞在第13行 n = 0 print(0,"<====1===>") 0>0 条件不成立 print(0,"<====2===>") 当前这层空间代码已经执行结束 此刻触发回的过程 n = 1 从上一次13行的代码阻塞位置,继续向下执行 print(1,"<====2===>") n = 2 从上一次13行的代码阻塞位置,继续向下执行 print(2,"<====2===>") n = 3 从上一次13行的代码阻塞位置,继续向下执行 print(3,"<====2===>") n = 4 从上一次13行的代码阻塞位置,继续向下执行 print(4,"<====2===>") n = 5 从上一次13行的代码阻塞位置,继续向下执行 print(5,"<====2===>") 到此,递归函数彻底执行结束. 5 4 3 2 1 0 0 """
1、栈帧空间
# 每次调用函数时,在内存中都会单独开辟一个空间,配合函数运行,这个空间叫做栈帧空间
""" (1).递归是一去一回的过程, 调用函数时,会开辟栈帧空间,函数执行结束之后,会释放栈帧空间 递归实际上就是不停的开辟和释放栈帧空间的过程 每次开辟栈帧空间,都是独立的一份,其中的资源不共享 (2).触发回的过程 1.当最后一层栈帧空间全部执行结束的时候,会触底反弹,回到上一层空间的调用处 2.遇到return,会触底反弹,回到上一层空间的调用处, (3).写递归时,必须给与递归跳出的条件,否则会发生内存溢出,蓝屏死机的情况. 如果递归层数过多,不推荐使用递归 """
2、举例
2.1、用递归计算n的阶乘
# 常规方法 # 5! = 5*4*3*2*1 def func(n): total = 1 for i in range(n,0,-1): total *= i return total res = func(5) print(res) # 递归写法 def jiecheng(n): if n <= 1: return 1 return n*jiecheng(n-1) res = jiecheng(5) print(res)
代码解析：
""" return 后面的表达式,一定是先计算完在返回 # 代码解析: # 去的过程: n = 5 return 5*jiecheng(5-1) => 5 * jiecheng(4) n = 4 return 4*jiecheng(4-1) => 4 * jiecheng(3) n = 3 return 3*jiecheng(3-1) => 3 * jiecheng(2) n = 2 return 2*jiecheng(2-1) => 2 * jiecheng(1) n = 1 return 1 # 回的过程: n = 2 return 2*jiecheng(2-1) => 2 * jiecheng(1) => 2 * 1 n = 3 return 3*jiecheng(3-1) => 3 * jiecheng(2) => 3 * 2 * 1 n = 4 return 4*jiecheng(4-1) => 4 * jiecheng(3) => 4 * 3 * 2 * 1 n = 5 return 5*jiecheng(5-1) => 5 * jiecheng(4) => 5 * 4 * 3 * 2 * 1 return 5 * 4 * 3 * 2 * 1 => return 120 """
2.2、尾递归
""" 自己调用自己,并且非表达式 计算的结果要在参数当中完成. 尾递归无论调用多少次函数,都只占用一份空间,但是目前cpython不支持. """
def jiecheng(n,endval): if n <= 1: return endval return jiecheng(n-1,endval*n) res = jiecheng(5,1) print(res)
代码解析：
""" # 代码解析: 去的过程 n=5 , endval=1 return jiecheng(5-1,endval*5) => jiecheng(4,1*5) n=4 , endval=1*5 return jiecheng(4-1,endval*4) => jiecheng(3,1*5*4) n=3 , endval=1*5*4 return jiecheng(3-1,endval*3) => jiecheng(2,1*5*4*3) n=2 , endval=1*5*4*3 return jiecheng(2-1,endval*2) => jiecheng(1,1*5*4*3*2) n=1 , endval=1*5*4*3*2 return endval 回的过程: n=2 return 120 n=3 return 120 n=4 return 120 n=5 return 120 因为最后一层空间的返回值就是第一层空间的返回值,所有在使用尾递归的时候 不需要考虑回的逻辑过程,就能解决问题.推荐使用. """
二、练习
1、打印多少
def extendList(val,list=[]): list.append(val) return list list1 = extendList(10) print(list1) list2 = extendList(123, []) print(list2) list3 = extendList('a') print(list3)
""" 默认参数: 当用户给与实参时,那么使用用户的实际参数 如果用没有给与实参,那么使用默认参数自带的值 """ """ 此刻list = [] 是内存中提前开辟好的一个空间 是list的默认值,每次都拿出这个默认值进行操作. 默认值只有一个,不是多个默认值. """ """ def extendList(val,list=[]): list.append(val) return list # 使用默认值 , 内存中提起开辟好的列表list = [] list1 = extendList(10) print(list1) # [10] # 用户给与的实参列表和 默认列表是两个完全不同的列表 list2 = extendList(123, []) print(list2) # 往实参列表中存入123 => [123] list3 = extendList('a') print(list3) # [10,"a"] 基于默认列表往里面存值 """
2、可滑动的序列 自定义一个函数 根据参数n的值，变成对应个元素的容器 （zip）
""" listvar = [1,2,3,4,5,6,7,8,9] n = 2 listvar = [[1,2],[3,4],[5,6],[7,8]] n = 3 listvar = [[1,2,3],[4,5,6],[7,8,9]] n = 4 listvar = [[1,2,3,4],[5,6,7,8]] """
""" listvar = [1,2,3,4,5,6,7,8,9] n = 2 listvar = [[1,2],[3,4],[5,6],[7,8]] lst1 = [1,3,5,7,9] lst2 = [2,4,6,8] lst1 = listvar[0::2] lst2 = listvar[1::2] it = zip(lst1,lst2) lst = list(it) print(lst) n = 2 listvar[i::2] for i in range(2) n = 3 listvar = [[1,2,3],[4,5,6],[7,8,9]] lst1 = [1,4,7] lst2 = [2,5,8] lst3 = [3,6,9] lst1 = listvar[0::3] lst2 = listvar[1::3] lst3 = listvar[2::3] it = zip(lst1,lst2,lst3) print(list(it)) n = 4 listvar = [[1,2,3,4],[5,6,7,8]] lst1 = [1,5,9] lst2 = [2,6] lst3 = [3,7] lst4 = [4,8] lst1 = listvar[0::4] lst2 = listvar[1::4] lst3 = listvar[2::4] lst4 = listvar[3::4] it = zip(lst1,lst2,lst3,lst4) print(list(it)) """ listvar = [1,2,3,4,5,6,7,8,9] n = 2 lst = [listvar[i::2] for i in range(2)] print(lst) n = 3 lst = [listvar[i::3] for i in range(3)] print(lst) n = 4 lst = [listvar[i::4] for i in range(4)] print(lst) lst = [[1, 5, 9], [2, 6], [3, 7], [4, 8]] it = zip(*lst) print(list(it)) # 普通方法 def func(n): return zip(*[listvar[i::n] for i in range(n)]) it = func(5) print(list(it)) # # lambda 表达式 func = lambda n : zip(*[listvar[i::n] for i in range(n)]) it = func(2) # [(1, 2), (3, 4), (5, 6), (7, 8)] # print(list(it)) print(list(map(list,it)))
3、递归题 -- 青蛙跳台阶
''' 一只青蛙要跳上n层高的台阶 一次能跳一级,也可以跳两级 请问这只青蛙有多少种跳上这个n层高台阶的方法? '''
""" n = 1 => 1 1:1 n = 2 => 2 2:1 1 | 2 n = 3 => 3 3:1 1 1 | 1 2 | 2 1 n = 4 => 5 5:1 1 1 1 | 1 2 1 | 2 1 1 | 1 1 2 | 2 2 n = 5 => 8 8:1 1 1 1 1 | 1 1 1 2 | 1 1 2 1 | 1 2 1 1 | 2 1 1 1 | 2 2 1 | 2 1 2 | 1 2 2 """ def jump(n): if n == 1 or n==2: return n return jump(n-1) + jump(n-2) res = jump(5) print(res)
4.递归反转字符串 "将14235 反转成53241"
# 方法一 strvar = "12345" lth = len(strvar) # 5 def func(lth,lst=[]): if lth == 0: return lst res = strvar[lth-1] lst.append(res) return func(lth-1) lst = func(lth) print(lst) print("".join(lst)) # 改造升级版: def outer(lth): # 递归函数 def func(lth,lst=[]): if lth == 0: return lst res = strvar[lth-1] lst.append(res) return func(lth-1) lst = func(lth) # 后期处理 return "".join(lst) lth = len(strvar) # 5 print(outer(lth)) # 方法二 strvar = "12345" def func(strvar): if len(strvar) == 1: return strvar return func(strvar[1:]) + strvar[0] res = func(strvar) print(res) # 54321 """ 递:去的过程 return func(2345) + 1 return func(345) + 2 return func(45) + 3 return func(5) + 4 return 5 归:回的过程 return 5 + 4 return 5 + 4 + 3 return 5 + 4 + 3 + 2 return 5 + 4 + 3 + 2 + 1 """