Python中的递归详解
文章目录
- 1.递归函数
- 2.递归流程图
- 3.递归总结
- 4.递归注意事项
- 5.内存栈区堆区(了解内容)
- 6.递归案例
- 1.使用递归实现任意数n的阶乘
- 普通实现
- 递归实现
- 2. 使用尾递归来实现任意数的阶乘
- （1） 优化代码1
- （2）优化代码2 [把尾递归需要的参数值隐藏起来,避免篡改.]
- （3）优化代码3(扩展)
- 3.使用递归来完成斐波那契数列
1.递归函数
工作中，我们可能经常会遇到递归函数的使用，今天我们就来深入讲讲什么是递归。
递归函数 : 在函数内部，可以调用其他函数。如果一个函数在内部自己调用自己，这个函数就是递归函数。必须由出口
递 : 去
归 : 回
一去一回叫做递归
def digui(n): print(n,"") if n > 0: digui(n-1) print(n,"") digui(5)#此递归函数开辟了6层空间。去的过程
n = 5 print(5,"") if 5 > 0: digui(5-1) => digui(4) 代码阻塞在第12行，下面的代码不再执行 n = 4 print(4,"") if 4 > 0: digui(4-1) => digui(3) 代码阻塞在第12行 n = 3 print(3,"") if 3 > 0: digui(3-1) => digui(2) 代码阻塞在第12行 n = 2 print(2,"") if 2 > 0: digui(2-1) => digui(1) 代码阻塞在第12行 n = 1 print(1,"") if 1 > 0: digui(1-1) => digui(0) 代码阻塞在第12行 n = 0 print(0,"") if 0 > 0: 不成立 print(0,"") 到此最后一层函数空间彻底执行完毕 这是在一个空间里面打印的 # 回的过程，从阻塞的地方代码往下走 回到上一层函数空间 n = 1 代码在第12行的位置,继续往下执行 print(1,"") 回到上一层函数空间 n = 2 代码在第12行的位置,继续往下执行 print(2,"") 回到上一层函数空间 n = 3 代码在第12行的位置,继续往下执行 print(3,"") 回到上一层函数空间 n = 4 代码在第12行的位置,继续往下执行 print(4,"") 回到上一层函数空间 n = 5 代码在第12行的位置,继续往下执行 print(5,"")
到此递归函数执行结束…
打印 543210012345
调用函数就得开辟空间，每次开辟的栈帧空间,代码必须全部执行完毕之后才释放空间,再回到上一个栈帧执行没结束的代码
2.递归流程图
每次调用函数时,都要单独在内存当中开辟空间,叫做栈帧空间,以运行函数中的代码
3.递归总结
(1)递归实际上是不停的开辟栈帧空间和释放栈帧空间的过程,开辟就是去的过程,释放就是回的过程 (2)递归什么时候触发归的过程: 1.当最后一层栈帧空间执行结束的时候,触发归的过程. 2.当遇到return返回值的时候终止当前函数,触发归的过程. (3)递归不能无限的去开辟空间,可能造成内存溢出,蓝屏***机的情况, 所以一定要给予跳出的条件(如果递归的层数太大,不推荐使用) (4)开辟的一个个栈帧空间,数据是彼此独立不共享的.递归不能不限开辟空间
官方说法最大默认是1000层. 但实际要看具体设备硬件性能
def deepfunc():
deepfunc()
deepfunc()
可以通过sys.setrecursionlimit()进行设置,但是一般默认不会超过3925-3929这个范围。
我这台电脑最大递归深度996层
4.递归注意事项
函数调用的过程就是开辟栈帧和释放栈帧的过程,调用时开辟栈帧空间,结束时释放 (言外之意不结束这层栈帧不释放) 递归每次调用都会开辟一个栈帧,如果递归的层数过多,不建议使用,容易内存溢出 每次开辟的栈帧空间,代码必须全部执行完毕之后才释放空间,在回到上一个栈帧执行没结束的代码 如果使用递归 , 需要给与一个跳出的条件,不能无限递归
尾递归:
在函数返回的时候，调用其本身，并且，return语句不包含表达式。
(简单来说是递归函数,且只调用自己的非表达式)
尾递归意义:
使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况.(需要Python解释器支持)
尾递归流程：
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 # 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 jiecheng(4,51) => 51432n = 4 ,endval = 5
1 return jiecheng(n-1 , n * endval) => jiecheng(3,514) => 51432n = 3 ,endval = 514 return jiecheng(n-1 , n * endval) => jiecheng(2,5143) => 51432
n = 2 ,endval = 5143 return jiecheng(n-1 , n * endval) => jiecheng(1,51432) => 51432
n = 1 ,endval = 51432 if n 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
可以直接计算出来斐波那契数列 第几个值是多少
