Python递归思想与代码实现

Python递归思想与代码实现,第1张

1, 递归思想

递归算法:递归(Recursion),在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。

这是官方的解释,翻译成人话就是:

  • 函数内部自己调用自己
  • 函数必须有出口 

函数自己调用自己很好理解,但什么是出口呢?我们知道,递归实际上是简化嵌套for循环的一种精简算法,所以在函数内部自己调用自己的过程就是在不短的循环,并改变函数传入的参数。如果没有不再执行自己调用自己的出口,那么递归就会陷入无限循环的无底洞。

出口通常是用return或if else语句避免再调用自己。

def recursion(n):
    print(n, "<===1====>")
    if n > 0:
        recursion(n - 1)
    # 那么这就是一个出口,如果n <= 0了就会不再递归
    else:
        print(n, '<===2====>')


recursion(5) # 外部调用

结果就是:


5 <===1====>
4 <===1====>
3 <===1====>
2 <===1====>
1 <===1====>
0 <===1====>
0 <===2====>  # 这个是出口,在这个时候n = 0

Process finished with exit code 0

递归还有两个重要的思想,第一个我们要找到等价的运算式,也就是将大问题拆分成很多个可递归的小问题。

第二个:

  1. 递推:像上边递归实现所拆解,递归每一次都是基于上一次进行下一次的执行,这叫递推。
  2. 回溯:则是在遇到终止条件,则从最后往回返一级一级的把值返回来,这叫回溯。

听到这是不是有点懵,我们来通过下面阶乘的实例与代码实现来进一步理解这个思想。

2,递归求阶乘,代码实现与思想解析

首先先上代码:

def factorial(n):
    # 出口
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))

这段代码求出了5的阶乘,大家先试着理解。

其中出口就是在n - 1 = 1的时候,递归就开始了回溯。

我们看一下流程图:

n * factorial(n-1)是等价表达式。红色箭头是递推的过程,从1-2-3-4;绿色箭头是回溯的过程,从a-b-c-d;紫色箭头是参数的变化。我把每一个式子都分解了一下,我们可以发现最后真正输出的是最外层的return,回溯顺序是从最底层往上返回。 

如果我们改一下代码,在每一次回溯的时候输出等价表达式的值:

def factorial(n):
    # 出口
    if n == 1:
        return 1
    # 递归内层
    else:
        factor = n * factorial(n-1)
        print(factor)
        return factor

print(factorial(5))

输出:

2
6
24
120
120

Process finished with exit code 0

不难发现,第一个输出的2就是流程图中的a式的值,6是b式的值,24是c式的值,120就是d式也就是最外层返回的5的阶乘了。

通过此输出,也证明了回溯过程的实现。这样我们就可以利用此思想求斐波那契数列等等等。那么递归其实也是可以用for来实现的。

# 求5的阶乘
num = 1
for i in range(1,6):
    num *= i
print(num)
3,栈溢出

递归效率不高,递归层次过多会导致栈溢出(在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出),此时程序会抛出错误:超出最大递归深度。

那么一般最大的深度是1000左右,我们可以通过sys的两个方法来设置最大深度和得到最大深度。

import sys


# 得到最大的深度值
print(sys.getrecursionlimit())
# 设置最大深度为2000
sys.setrecursionlimit(2000)
4,运行速度
import sys
import time
print(sys.getrecursionlimit())
sys.setrecursionlimit(2000)
start = time.time()


def factorial(n):
    # 出口
    if n == 1:
        return 1
    # 递归内层
    else:
        return n * factorial(n-1)

print(factorial(1000))
print(time.time() - start)

我们通过time方法来获取运行的时间,发现大概在0.008s左右

而for循环实测在0.004秒左右,所以我们看到递归的缺点是资源占用和运行速度劣与for循环。

所以我们总结一下递归的缺点:

  1. 递归由于是函数调用自身,而函数调用是有时间和空间的消耗的--效率
  2. 递归中很多计算都是重复的,由于其本质是把一个问题分解成两个或者多个小问题,多个小问题存在相互重叠的部分,则存在重复计算--效率
  3. 调用栈可能会溢出,其实每一次函数调用会在内存栈中分配空间,而每个进程的栈的容量是有限的,当调用的层次太多时,就会超出栈的容量,从而导致栈溢出,强制设置最大深度会导致内存占用大--性能

优点:

  1. 简洁
  2. 在特殊情况下比for循环更加简洁,逻辑清晰。
4,建议

在使用for循环运算量并不太大时使用递归,在for循环逻辑太过于繁琐时使用递归。

  

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/727397.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-26
下一篇 2022-04-26

发表评论

登录后才能评论

评论列表(0条)

保存