Python中的递归详解

大家好，欢迎来到IT知识分享网。

1.递归函数

工作中，我们可能经常会遇到递归函数的使用，今天我们就来深入讲讲什么是递归。

def digui(n): print(n,"<==1==>") if n > 0: digui(n-1) print(n,"<==2==>") digui(5) 

#此递归函数开辟了6层空间。去的过程

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==>") 

2.递归流程图

每次调用函数时,都要单独在内存当中开辟空间,叫做栈帧空间,以运行函数中的代码

3.递归总结

(1)递归实际上是不停的开辟栈帧空间和释放栈帧空间的过程,开辟就是去的过程,释放就是回的过程 (2)递归什么时候触发归的过程: 1.当最后一层栈帧空间执行结束的时候,触发归的过程. 2.当遇到return返回值的时候终止当前函数,触发归的过程. (3)递归不能无限的去开辟空间,可能造成内存溢出,蓝屏死机的情况, 所以一定要给予跳出的条件(如果递归的层数太大,不推荐使用) (4)开辟的一个个栈帧空间,数据是彼此独立不共享的. 

可以通过sys.setrecursionlimit()进行设置,但是一般默认不会超过3925-3929这个范围。

4.递归注意事项

函数调用的过程就是开辟栈帧和释放栈帧的过程,调用时开辟栈帧空间,结束时释放 (言外之意不结束这层栈帧不释放) 递归每次调用都会开辟一个栈帧,如果递归的层数过多,不建议使用,容易内存溢出 每次开辟的栈帧空间,代码必须全部执行完毕之后才释放空间,在回到上一个栈帧执行没结束的代码 如果使用递归 , 需要给与一个跳出的条件,不能无限递归 

5.内存栈区堆区(了解内容)

栈区 堆区 静态区 代码区 都是内存中的一段空间

6.递归案例

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)) 

print(“<====================>”)

2. 使用尾递归来实现任意数的阶乘

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) 

（1） 优化代码1

（2）优化代码2 [把尾递归需要的参数值隐藏起来,避免篡改.]

（3）优化代码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))