一.递归函数
自己调用自己的函数就是递归
递: 去
归: 回
一去一回就是递归
1 def digui(n): 2 print(n,"<====1===>") 3 if n > 0: 4 digui(n-1) 5 print(n,"<====2===>") 6 digui(5)
(1)代码解析:
去的过程: 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 2 3 4 5
(2)每次调用函数时,在内存中都会单独开辟一个空间,配合函数运行,这个空间叫做栈帧空间
(1).递归是一去一回的过程, 调用函数时,会开辟栈帧空间,函数执行结束之后,会释放栈帧空间 递归实际上就是不停的开辟和释放栈帧空间的过程 每次开辟栈帧空间,都是独立的一份,其中的资源不共享 (2).触发回的过程 1.当最后一层栈帧空间全部执行结束的时候,会触底反弹,回到上一层空间的调用处 2.遇到return,会触底反弹,回到上一层空间的调用处, (3).写递归时,必须给与递归跳出的条件,否则会发生内存溢出,蓝屏死机的情况. 如果递归层数过多,不推荐使用递归
二.递归练习
(1) 用递归计算n的阶乘
<1>常规方法
1 def func(n): 2 total = 1 3 for i in range(n,0,-1): 4 total *= i 5 return total 6 res = func(5) 7 print(res)
<2>递归写法
1 def jiecheng(n): 2 if n <= 1: 3 return 1 4 return n*jiecheng(n-1) 5 res = jiecheng(5) 6 print(res)
<3>代码解析
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 额外解析: jiecheng(1) => 1 jiecheng(2) => 2*jiecheng(1) => 2*1 jiecheng(3) => 3*jiecheng(2) => 3*2*1 jiecheng(4) => 4*jiecheng(3) => 4*3*2*1 jiecheng(5) => 5*jiecheng(4) => 5* 4*3*2*1
(2)尾递归
自己调用自己,并且非表达式
计算的结果要在参数当中完成.
尾递归无论调用多少次函数,都只占用一份空间,但是目前cpython不支持.
<1>尾递归
1 def jiecheng(n,endval): 2 if n <= 1: 3 return endval 4 return jiecheng(n-1,endval*n) 5 res = jiecheng(5,1) 6 print(res)
<2>代码解析
去的过程 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 120 回的过程: n=2 return 120 n=3 return 120 n=4 return 120 n=5 return 120 因为最后一层空间的返回值就是第一层空间的返回值,所有在使用尾递归的时候 不需要考虑回的逻辑过程,就能解决问题.推荐使用.
(3)优化1
1 def jiecheng(n,endval=1): 2 if n <= 1: 3 return endval 4 return jiecheng(n-1,endval*n) 5 res = jiecheng(5) 6 print(res,)
(4)优化2
为了避免用户乱传参数,把endval这个参数隐藏起来
1 def outer(n): 2 def jiecheng(n,endval=1): 3 if n <= 1: 4 return endval 5 return jiecheng(n-1,endval*n) 6 return jiecheng(n) # jiecheng(n-1,endval*n) 7 res = outer(5) 8 print(res)
(5)递归计算斐波那契数列
1,1,2,3,5,8,13 ....
n = 3 => 2
n = 5 => 5
n = 6 => 8
上一个 n-1 上上个 n-2
<1>
1 def feb(n): 2 # 递归跳出的条件 3 if n <= 2: # n == 1 or n == 2 => 1 4 return 1 5 return feb(n-1) + feb(n-2) 6 res = feb(5) 7 print(res)
<2>代码解析
n = 5 return feb(5-1) + feb(5-2) => feb(4) + feb(3) feb(4)->3 + feb(3)->2 => 5 feb(3) + feb(2) feb(2) + feb(1) feb(2)+feb(1) | 1 1 + 1 1 + 1 + 1