大蟒蛇python教程共享Python全栈之递归函数

目录

• 1. 递归函数
• 2. 递归练习
• 3. 小练习
• 总结

  # ### 递归函数  """  递归函数 : 自己调用自己的函数 , 叫做递归函数  递 : 去  归 : 回  一去一回叫做递归  """  def digui(n):      print(n,"<==1==>")      if n > 0:          digui(n-1)      print(n,"<==2==>")  digui(5)  """  # 去的过程  n = 5 print(5,"<==1==>")  if 5 > 0:   digui(5-1) =>  digui(4) 代码阻塞在第12行  n = 4 print(4,"<==1==>")  if 4 > 0:   digui(4-1) =>  digui(3) 代码阻塞在第12行  n = 3 print(3,"<==1==>")  if 3 > 0:   digui(3-1) =>  digui(2) 代码阻塞在第12行  n = 2 print(2,"<==1==>")  if 2 > 0:   digui(2-1) =>  digui(1) 代码阻塞在第12行  n = 1 print(1,"<==1==>")  if 1 > 0:   digui(1-1) =>  digui(0) 代码阻塞在第12行  n = 0 print(0,"<==1==>")  if 0 > 0: 不成立 print(0,"<==2==>") 到此最后一层函数空间彻底执行完毕  # 回的过程  回到上一层函数空间  n = 1 代码在第12行的位置,继续往下执行  print(1,"<==2==>")  回到上一层函数空间  n = 2 代码在第12行的位置,继续往下执行  print(2,"<==2==>")  回到上一层函数空间  n = 3 代码在第12行的位置,继续往下执行  print(3,"<==2==>")  回到上一层函数空间  n = 4 代码在第12行的位置,继续往下执行  print(4,"<==2==>")  回到上一层函数空间  n = 5 代码在第12行的位置,继续往下执行  print(5,"<==2==>")  到此递归函数执行结束..  打印 543210012345  """  """  每次调用函数时,都要单独在内存当中开辟空间,叫做栈帧空间,以运行函数中的代码  递归总结:  	(1)递归实际上是不停的开辟栈帧空间和释放栈帧空间的过程,开辟就是去的过程,释放就是回的过程  	(2)递归什么时候触发归的过程:  		1.当最后一层栈帧空间执行结束的时候,触发归的过程.  		2.当遇到return返回值的时候终止当前函数,触发归的过程.  	(3)递归不能无限的去开辟空间,可能造成内存溢出,蓝屏死机的情况,所以一定要给予跳出的条件(如果递归的层数太大,不推荐使用)  	(4)开辟的一个个栈帧空间,数据是彼此独立不共享的.  """  # 递归不能不限开辟空间  """官方说法最大默认是1000层."""  def deepfunc():  	deepfunc()  deepfunc()  

  # ### 1.使用递归实现任意数n的阶乘   # 普通实现  # 5! =5 *4*3*2*1  n = 5  total = 1  for i in range(n,0,-1):  	total *= i  print(total) # 120  # 递归实现  def jiecheng(n):  	if n <= 1:  		return 1  	return jiecheng(n-1) * n  print(jiecheng(2))  # jiecheng(1) => 1   # jiecheng(2) => jiecheng(1) * 2 => 1 * 2  # jiecheng(3) => jiecheng(2) * 3 => 1 * 2 * 3  # jiecheng(4) => jiecheng(3) * 4 => 1 * 2 * 3 * 4  # jiecheng(5) => jiecheng(4) * 5 => 1 * 2 * 3 * 4 * 5  print(jiecheng(5))  """  代码解析:  去的过程:  n = 5 return jiecheng(n-1) * n => jiecheng(4) * 5  n = 4 return jiecheng(n-1) * n => jiecheng(3) * 4  n = 3 return jiecheng(n-1) * n => jiecheng(2) * 3  n = 2 return jiecheng(n-1) * n => jiecheng(1) * 2  n = 1 return 1  回的过程:  n = 2 return jiecheng(1) * 2 => 1 * 2  n = 3 return jiecheng(2) * 3 => 1 * 2 * 3  n = 4 return jiecheng(3) * 4 => 1 * 2 * 3 * 4  n = 5 return jiecheng(4) * 5 => 1 * 2 * 3 * 4 * 5  到此程序结束:  返回  1 * 2 * 3 * 4 * 5  """  print("<====================>")  # ### 2. 使用尾递归来实现任意数的阶乘  """ return 在哪调用,在哪返回 """  """自己调用自己,且返回时非运算表达式,只是函数本身"""  """  特点:  	尾递归只开辟一个空间,不会无限的开辟,在一个空间里面去计算最后的结果进行返回,比较节省空间,有的解释器支持尾递归的调用特点  	但是cpython解释器目前不支持  写法:  	所有运算的值都在函数的参数中计算完毕,最后返回运算的参数;  """  def jiecheng(n,endval):  	if n <= 1:  		return endval  	return jiecheng(n-1 , n * endval)  res = jiecheng(5,1) # 5*4*3*2*1  print(res)  """  代码解析:  去的过程  n = 5 ,endval = 1 return jiecheng(n-1 , n * endval) => jiecheng(4,5*1) => 5*1*4*3*2  n = 4 ,endval = 5*1 return jiecheng(n-1 , n * endval) => jiecheng(3,5*1*4) => 5*1*4*3*2   n = 3 ,endval = 5*1*4 return jiecheng(n-1 , n * endval) => jiecheng(2,5*1*4*3) => 5*1*4*3*2   n = 2 ,endval = 5*1*4*3 return jiecheng(n-1 , n * endval) => jiecheng(1,5*1*4*3*2) => 5*1*4*3*2   n = 1 ,endval = 5*1*4*3*2   if n <= 1 成立  return endval  endval = 5*1*4*3*2   最下层空间的返回值 是 5*4*3*2*1  最上层接收到的返回值也是 5*4*3*2*1  最下层和最上层返回的结果是一致的,所以对于尾递归来说,只需要考虑去的过程,无需考虑回的过程即可完成;  """  # 优化代码1  def jiecheng(n,endval=1):  	if n <= 1:  		return endval  	return jiecheng(n-1 , n * endval)  res = jiecheng(5,100) # 5*4*3*2*1  print(res,"<00000>")  # 优化代码2 [把尾递归需要的参数值隐藏起来,避免篡改.]  def outer(n):  	def jiecheng(n,endval=1):  		if n <= 1:  			return endval  		return jiecheng(n-1 , n * endval)  	return jiecheng(n,1)# 120  print(outer(5))  # 优化代码3(扩展)  # 闭包实现  def outer(n):  	endval = 1  	def jiecheng(n):  		nonlocal endval  		if n <= 1:  			return endval  		endval *= n   		return jiecheng(n-1)  	return jiecheng  func = outer(5)  print(func(5),"<===111==>")  print("<================>")  # ### 3.使用递归来完成斐波那契数列  """ 1 1 2 3 5 8 13 21 34 ... """  def feib(n):  	if n == 1 or n == 2:  		return 1  	# 上一个结果 + 上上个结果  	return feib(n-1) + feib(n-2)  print(feib(5))  """  # 代码解析:  n = 5               feib(5) => 3 + 2 => return 5    		feib(4)        +         feib(3)      feib(3)+feib(2)          feib(2)+feib(1) => 1 + 1 => 2  feib(2)+feib(1)+feib(2) => 1 + 1 + 1 => 3      """  

  # (选做)  # 1.可滑动的序列 自定义一个函数 根据参数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]]  """  """  lst1 = [1,3,5,7,9]  lst2 = [2,4,6,8]  zip(lst1,lst2)  """  listvar = [1,2,3,4,5,6,7,8,9]  n = 2  lst1 = [1,3,5,7,9]  lst2 = [2,4,6,8]  # lst1 = listvar[0::2]  <=> [1,3,5,7,9]  # lst2 = listvar[1::2]  <=> [2,4,6,8]  print(lst2,"1111")  print(list( zip(lst1,lst2) ))  n = 3  lst1 = [1,4,7]  lst2 = [2,5,8]  lst3 = [3,6,9]  # lst1 = listvar[0::3]  <=> [1,4,7]  # lst2 = listvar[1::3]  <=> [2,5,8]  # lst3 = listvar[2::3]  <=> [3,6,9]  print(lst1,"2222")  print(list( zip(lst1,lst2,lst3) ))  n = 4  lst1 = [1,5]  lst2 = [2,6]  lst3 = [3,7]  lst4 = [4,8]  # lst1 = listvar[0::4]  <=> [1,5,9]  # lst2 = listvar[1::4]  <=> [2,6]  # lst3 = listvar[2::4]  <=> [3,7]  # lst4 = listvar[3::4]  <=> [4,8]  print(lst1,"3333")  print(list( zip(lst1,lst2,lst3,lst4) ))  print("<=============>")  n = 3  lst = [ listvar[i::n] for i in range(n) ]  print(lst) # [[1, 4, 7], [2, 5, 8], [3, 6, 9]]  # zip(*lst) => zip([1,4,7],[2,5,8],[3,6,9])  it = zip(*lst)  print(list(it))  func = lambda n : zip(  *[ listvar[i::n] for i in range(n) ]   )  it = func(2)  # 把里面的元组强转成列表  print(list(map(list,it)))  # 2.青蛙跳台阶  (递归实现)  '''  一只青蛙要跳上n层高的台阶  一次能跳一级,也可以跳两级  请问这只青蛙有多少种跳上这个n层高台阶的方法?  n = 1   1 => 1  n = 2   2 => 1 1 | 2  n = 3   3 => 1 1 1 | 1 2 | 2 1   n = 4   5 => 1 1 1 1 | 1 2 1 | 2 1 1 | 1 1 2 | 2 2  n = 5   8 => 1 1 1 1 1 | 1 1 1 2 |2 1 1 1 | 1 2 1 1  | 1 1 2 1 | 2 2 1 | 1 2 2 | 2 1 2   '''  def func(n):  	if n == 1 or n == 2:  		return n  	return func(n-1) + func(n-2)  print(func(5))  # 3.递归反转字符串 "将14235 反转成53241" (递归实现)  # 把后面的字符往前挪动 方法一  strvar = "14235"  # lst.append(5)  # lst.append(3)  # lst.append(2)  # lst.append(4)  # lst.append(1)  # lth = 字符串的总长度  lst 要插入的列表  def func(lth,lst=[]):  	if lth == 0:  		return lst  	res = strvar[lth-1]  	lst.append(res)  	return func(lth-1)  lth = len(strvar)  lst = func(lth)  print(lst) # ['5', '3', '2', '4', '1']  print("".join(lst))  # 简写  def func(lth,lst=[]):  	if lth == 0:  		return "".join(lst)  	res = strvar[lth-1]  	lst.append(res)  	return func(lth-1)  print(func(lth))  # 把前面的字符往后挪动 方法二  strvar = "14235"  def func(strvar):  	if len(strvar) == 1:  		return strvar  	return func(strvar[1:])+strvar[0]  res = func(strvar)  print(res)  """  递:  return func(4235) + 1  return func(235)  + 4  return func(35)   + 2  return func(5)    + 3  return 5  归:  return func(5)    + 3 => 5 + 3  return func(35)   + 2 => 5 + 3 + 2  return func(235)  + 4 => 5 + 3 + 2 + 4  return func(4235) + 1 => 5 + 3 + 2 + 4 + 1  return 5 + 3 + 2 + 4 + 1  """    # 4.斐波那契数列用尾递归实现  a,b = 0,1  i = 0  n = 5  while i < n:  	print(b)  	a,b = b,a+b  	i +=1  a,b = 0,1  n = 5  while n > 0:  	print(b)  	a,b = b,a+b  	n -= 1  print("<==============>")  def func(n,a=0,b=1):  	if n == 1:  		return b  	return func(n-1,b,a+b)  print(func(6))