Python实例详解递归算法

作者:Python大数据分析 时间:2023-05-17 02:25:06 

递归是一种较为抽象的数学逻辑,可以简单的理解为「程序调用自身的算法」。

* 对递归的解释是:

递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。

例如,当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

"递"是传递的意思,"归"是归还的意思,先把一个方法一层层传递下去,然后传递到最后一层再把结果归还回来。

Python实例详解递归算法

比方说我排队做核酸检测,前面有100个人,我想问下医务人员几点下班,于是问了我前面那兄弟,他又问了他前面的人,一个个传递下去,最终传递到了医务人员那里,回话说下午六点下班。这句话又往回传,最终到了我这里,我知道了医务人员六点下班。

这个过程就是一个递归过程,如果说"传话"本身是一种方法,那这整个传话过程就是在调用自身方法,最终获得了结果。

这和循环不一样,循环相当于给所有人都所有人都戴了耳机,然后有"中介"挨个去问你知道医务人员几点下班吗,等问到医务人员的时候,得到答案,“中介”告诉我六点下班。

实质上,递归就是把一个大问题不断拆解,像剥洋葱一样,最终拆解到最小层面,会返回解题结果。

Python实例详解递归算法

用Python举一个最简单的递归函数例子,讲一讲什么是递归的应用。

我们经常会看到函数会调用自身来实现循环操作,比如求阶乘的函数。

整数n的阶乘即n*(n-1)*(n-2)*...*3*2*1

如下面5行Python代码,就能实现阶乘的计算

def fact(n):
    ''' n表示要求的数的阶乘 '''
    if n==1:
        return n 
    n = n*fact(n-1)
    return n  

print(factorial(5))

输出:

120

很多人可能困惑这里面的计算逻辑,为什么fact函数中调用了自身,最终能得到结果。

我们可以按照数学逻辑进行推演:

整数n的阶乘是:fact(n) = n*(n-1)*...*3*2*1

整数n-1的阶乘是:fact(n-1) = (n-1)*(n-2)*...*3*2*1

所以可以推断 fact(n) = n*fact(n-1)

Python实例详解递归算法

这里是不是一种 fact方法可以为每个数所调用,最终调用到了n=1的时候,就返回结果n的阶乘。

Python实例详解递归算法

大家看上图,递归函数会一层层往下调用,最终到n=1的时候,往上返回结果。

这就是递归的全过程,如果我们给递归下一个准确的定义,可以概括为以下3点:

1、至少有一个明确的递归结束条件;

2、给出递归终止时的处理办法;

3、每次进入更深一层递归时,问题规模(计算量)相比上次递归都应有所减少

以上面代码为例:

def factorial(n):
    ''' n表示要求的数的阶乘 '''
    if n==1: # 1、明确递归终止条件;
        return n # 2、递归终止时的处理办法
    n = n*factorial(n-1) # 递去
    return n  # 归来

除了常见的阶乘案例,还有斐波那契数列,也是递归的经典用法。

斐波那契数列:1,1,2,3,5,8,13,21,34,55,89...

这个数列从第3项开始,每一项都等于前两项之和。

它以如下被以递推的方法定义:F(0)=0,F(1)=1,F(n)=F(n - 1)+F(n - 2)(n≥ 2,n∈ N*)

在Python中,我们可以使用递归函数的方式去实现斐波那契数列:

# 1,1,2,3,5,8,13,21,34,55,试判断数列第12个数是哪个?
def fab(n):
    ''' n为斐波那契数列 '''
    if n <= 2:
        v = 1
        return v 
    v = fab(n-1)+fab(n-2) 
    return v  

print(fab(12)) 

使用数学方法进行推导:

  • fab(0) = 0(初始值)

  • fab(1) = 1(初始值)

  • 对所有大于1的整数n:fab(n) = fab(n-1)+ fab(n-2)(递归定义)

其实以上两个递归的案例都可以用数学归纳法来解释,就是高中数学的知识。

一般地,证明一个与自然数n有关的命题P(n),有如下步骤:

(1)证明当n取第一个值n0时命题成立。n0对于一般数列取值为0或1,但也有特殊情况;

(2)假设当n=k(k&ge;n0,k为自然数)时命题成立,证明当n=k+1时命题也成立。

综合(1)(2),对一切自然数n(&ge;n0),命题P(n)都成立。

除了数学的解释,之前也看到有人对递归更加形象的解释:

1、我们已经完成了吗?如果完成了,返回结果。如果没有这样的终止条件,递归将会永远地继续下去。

2、如果没有,则简化问题,解决较容易的问题,并将结果组装成原始问题的解决办法。然后返回该解决办法。

哈哈,到这里大家是不是对递归有了一个更加深刻的认识。

如果还不清楚,没关系,这里还有更多的递归案例,用Python来实现,可以说非常简洁。

「最大公因数:」

def gcd(m, n):
    if n == 0:
        return m
    else:
        return gcd(n, m%n)

「从 1 到 n 的数字之和:」

def sumnums(n):
    if n == 1:
        return 1
    return n + sumnums(n - 1)

print(sumnums(3))

「字符串倒序:」

def reverse(string):
    if len(string) == 0:
        return string
    else:
        return reverse(string[1:]) + string[0]

reverseme = '我是帅哥'
print(reverse(reverseme))

「汉诺塔问题:」

def towerOfHanoi(numrings, from_pole, to_pole, aux_pole):
    if numrings == 1:
        print('Move ring 1 from', from_pole, 'pole to', to_pole, 'pole')
        return
    towerOfHanoi(numrings - 1, from_pole, aux_pole, to_pole)
    print('Move ring', numrings, 'from', from_pole, 'pole to', to_pole, 'pole')
    towerOfHanoi(numrings - 1, aux_pole, to_pole, from_pole)

numrings = 2
towerOfHanoi(numrings, 'Left', 'Right', 'Middle')

「二分法找有序列表指定值:」

data = [1,3,6,13,56,123,345,1024,3223,6688]
def dichotomy(min,max,d,n):
    '''
    min表示有序列表头部索引
    max表示有序列表尾部索引
    d表示有序列表
    n表示需要寻找的元素
    '''
    mid = (min+max)//2
    if mid==0:
        return 'None'
    elif d[mid]<n:
        print('向右侧找!')
        return dichotomy(mid,max,d,n)
    elif d[mid]>n:
        print('向左侧找!')
        return dichotomy(min,mid,d,n)
    else:
        print('找到了%s'%d[mid])
        return 
res = dichotomy(0,len(data),data,222)
print(res)

有位大佬说过:To Iterate is Human, to Recurse, Divine.

中文译为:人理解迭代,神理解递归。

可见递归是非常神奇的算法,它的神奇之处在于它允许用户用有限的语句描述无限的对象。

当然人无完人,递归也是有缺点的,它一般效率较低,且会导致调用栈溢出。

因为递归不断调用自身函数,且产生大量变量,而栈空间的容量是有限的,循环太多就会效率低下,甚至导致调用栈溢出

来源:https://mp.weixin.qq.com/s/wXavl8l3v0MwJ2zWdJ0KCA

标签:Python,递归,算法
0
投稿

猜你喜欢

  • Thinkphp5.0 框架使用模型Model添加、更新、删除数据操作详解

    2024-06-07 15:35:37
  • Java实现从数据库导出大量数据记录并保存到文件的方法

    2024-01-16 09:47:37
  • SQLServer2000 报1053错误(服务没有及时响应或控制请求)的解决方法

    2024-01-23 10:40:47
  • Python OpenCV对本地视频文件进行分帧保存的实例

    2021-09-15 23:03:18
  • python编写脚本之pyautogui的安装和使用教程

    2021-06-17 09:48:11
  • 如何获知IE和NC客户端的屏幕分辨率?

    2009-11-23 20:56:00
  • python实现mask矩阵示例(根据列表所给元素)

    2022-04-19 19:37:16
  • Git科普文,Git基本原理及各种骚操作(推荐)

    2023-09-16 17:04:32
  • python中正则表达式与模式匹配

    2023-08-25 22:54:59
  • 有关于IE8 Beta 1两个提醒

    2008-05-15 12:32:00
  • 关于Python中*args和**kwargs的深入理解

    2021-04-07 17:45:06
  • 基于python requests selenium爬取excel vba过程解析

    2021-06-18 23:47:09
  • Python Xml文件添加字节属性的方法

    2023-08-27 03:48:31
  • pyqt5实现绘制ui,列表窗口,滚动窗口显示图片的方法

    2023-03-22 16:52:56
  • Python django搭建layui提交表单,表格,图标的实例

    2022-09-18 19:40:19
  • Python+Socket实现基于TCP协议的客户与服务端中文自动回复聊天功能示例

    2023-07-18 20:11:01
  • CSS Frameworks的概念

    2008-01-23 18:41:00
  • laravel学习教程之关联模型

    2023-06-11 19:46:55
  • PHP的SQL注入过程分析

    2023-11-18 02:53:27
  • ES6记录异步函数的执行时间详解

    2024-04-10 16:18:56
  • asp之家 网络编程 m.aspxhome.com