Python中的递归详解

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

到此递归函数执行结束…

打印 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:
        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,51) => 51432

n = 4 ,endval = 51 return jiecheng(n-1 , n * endval) => jiecheng(3,514) => 51432

n = 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 <= 1 成立 return endval

endval = 51432

最下层空间的返回值 是 54321 最上层接收到的返回值也是 54321

最下层和最上层返回的结果是一致的,所以对于尾递归来说,只需要考虑去的过程,无需考虑回的过程即可完成;

（1） 优化代码1

def jiecheng(n,endval=1):

if n <= 1:

return endval

return jiecheng(n-1 , n * endval)

res = jiecheng(5,100) # 54321

print(res,“<00000>”)

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

可以直接计算出来斐波那契数列 第几个值是多少