文档章节

连载|想用Python做自动化测试?递归函数

明说软件测试
 明说软件测试
发布于 07/29 08:20
字数 1956
阅读 1.9K
收藏 2

行业解决方案、产品招募中!想赚钱就来传!>>>

 递归函数就是函数内部调用自身,可以使代码逻辑更加易懂。但是递归也有坑,需要避免。


13.1 概念

  • 在函数内部,可以调用其他函数。如果一个函数在内部调用自身,这个函数就是递归函数。

  • 理论上,所有的递归函数都可以写成循环的方式,但循环的逻辑不如递归清晰。

计算阶乘n! = 1 x 2 x 3 x ... x n,用函数fact(n)表示:

def fact(n):  if n==1:      return 1  return n * fact(n - 1)

13.2 写递归代码的套路

写递归代码的关键就是找到如何将大问题分解为小问题的规律,然后按照下面套路即可实现:

  • 第一步,写出递推公式

以计算阶乘为例,递归公式是:fact(n)=n!=(n−1)×⋅⋅⋅3×2×1=n×(n−1)!=n×fact(n−1)

  • 第二步,推敲终止条件

以计算阶乘为例,终止条件是n=1时,fact(1)=1。

13.2.1 斐波那契数列

再来看一个斐波那契数列的例子,斐波那契数列中后一个元素是前两个相邻元素的和。比如:

0,1,1,2,3,5,8,13,21,34,55,…。

那么我们如何得到第n个数是多少?分两步走:

第一步,写出递推公式。求第n个元素,可以先求出n-1和n-2个元素的值,然后再将这两个求和,所以公式是:

fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)

第二步,推敲最终终止条件。终止条件包含三个:n=0时,f(n)=0;n=1时,f(n)=1;n=2时,f(n)=1。

if n < 1:  # 递归终止条件   return 0if n in [1, 2]:  # 递归终止条件   return 1

转换成完整代码就是:

def fibonacci(n):    if n < 1:  # 递归终止条件        return 0    if n in [1, 2]:  # 递归终止条件        return 1     return fibonacci(n - 1) + fibonacci(n - 2)  # 递归公式

不管是编写递归还是阅读递归代码,只要遇到递归,我们就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑搞清楚计算机每一步都是怎么执行的。

13.2.2 n 个台阶有多少种走法

再来看看一个例子,假如有 n 个台阶,每次可以跨 1 个台阶或者 2 个台阶,请问走这 n 个台阶有多少种走法?

我们从第一步开始想,如果第一步跨1个台阶,问题就变成了n-1个台架有多少种走法。如果第一步跨2个台阶,问题就变成n-2个台阶有多少种走法。我们把n-1个台阶的走法和n-2个台阶的走法求和,就是n个台阶的走法。用公式表示就是f(n)=f(n-1)+f(n-2)。这就是递归公式了。

再来看看终止条件,最后1个台阶就不需要再继续递归了,只有一种走法,就是f(1)=1。我们把这个放到递归公式里面看下,通过这个终止条件能否求出f(2),发现f(2)=f(1)+f(0),也就是仅知道f(1)是不能求出f(2)的,因此要么知道f(0)的值,或者直接将f(2)作为一个递归终止条件。f(0)表示0个台阶有几种走法,f(2)表示2个台阶有几种走法。明显,f(2)更容易理解一些。所以定为f(2)=2也是一个终止条件,表示最后2个台阶有两种走法,即一次跨1个台阶和一次跨2个台阶。有了f(1)和f(2),就能求出f(3),进而求出f(n)了。

转化成代码即是:

def walk(n):    if n == 1:  # 递归终止条件        return 1    if n == 2:  # 递归终止条件        return 2    return walk(n - 1) + walk(n - 2)  # 递归公式

13.3 递归可解决哪类问题

  • 原始问题的解可以分解为几个子问题的解

  • 原始问题和子问题,只有数据规模的不同,求解思路完全一样

  • 存在递归终止条件

13.4 递归存在的问题

  • 堆栈溢出

  • 重复计算

编写递归代码时,我们会遇到很多问题,比较常见的一个就是堆栈溢出,而堆栈溢出会造成系统性崩溃,后果会非常严重。什么是堆栈溢出呢?

函数调用会使用栈来保存临时变量。每调用一个函数,都会将临时变量封装为栈帧压入内存栈,等函数执行完成返回时,再出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大,调用层次很深,一直压入栈,就会有堆栈溢出的风险。

可以通过Pycharm工具查看调用栈的情况。在递归公式那行代码上添加断点,不断执行Step Over,可以看到Frames窗口中的栈信息会不断增加和减少,当调用一次函数会增加一帧,当调用返回后会减少一帧。最后返回第一层栈func.py。前面说的堆栈溢出的风险,体现在Frames窗口中的栈帧太多了。

那么,如何避免出现堆栈溢出呢?

通常可以在代码中限制递归调用的最大深度的方式来解决这个问题。比如Python语言,限制了递归深度,当递归深度过高,则会抛出:RecursionError: maximum recursion depth exceeded in comparison异常,防止系统性崩溃。

我们在代码中也可以自己设置递归的深度,比如限制n最大不能超过100,代码如下:

def walk(n):    if n == 1:        return 1    if n == 2:        return 2    if n > 100:        raise RecursionError("recursion depth exceede 100")    return walk(n - 1) + walk(n - 2)

除此之外,使用递归时还会出现重复计算的问题。什么意思?拿走台阶那个例子来说明。比如计算6个台阶的走法f(6),过程如下图:

从图中,我们可以直观地看到,想要计算 f(5),需要先计算 f(4) 和 f(3),而计算 f(4) 还需要计算 f(3),因此,f(3) 就被计算了很多次,这就是重复计算问题。

那么怎么解决这个问题?为了避免重复计算,我们可以通过字典保存已经求解过的 f(k)。当递归调用到 f(k) 时,先看下是否已经求解过了。如果是,则直接从字典中取值,不需要重复计算,这样就能避免刚讲的问题了。

修改下计算台阶走法的代码,解决重复计算的问题:

data = dict()  # 保存中间结果

def walk(n): if n == 1: return 1 if n == 2: return 2 if n > 100: raise RecursionError("recursion depth exceed 100") if n in data: # 如果在中间结果中,则直接返回,不用进入递推公式再次计算 return data[n] result = walk(n - 1) + walk(n - 2) # 在递归公式前面增加个查找步骤 data[n] = result # 将计算结果保存在中间结果data字典中 return result

print(walk(6))


本文分享自微信公众号 - 明说软件测试(liuchunmingnet)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

明说软件测试
粉丝 0
博文 41
码字总数 71974
作品 0
私信 提问
加载中
请先登录后再评论。
访问安全控制解决方案

本文是《轻量级 Java Web 框架架构设计》的系列博文。 今天想和大家简单的分享一下,在 Smart 中是如何做到访问安全控制的。也就是说,当没有登录或 Session 过期时所做的操作,会自动退回到...

黄勇
2013/11/03
3.4K
6
用vertx实现高吞吐量的站点计数器

工具:vertx,redis,mongodb,log4j 源代码地址:https://github.com/jianglibo/visitrank 先看架构图: 如果你不熟悉vertx,请先google一下。我这里将vertx当作一个容器,上面所有的圆圈要...

jianglibo
2014/04/03
3.9K
3
SQLServer实现split分割字符串到列

网上已有人实现sqlserver的split函数可将字符串分割成行,但是我们习惯了split返回数组或者列表,因此这里对其做一些改动,最终实现也许不尽如意,但是也能解决一些问题。 先贴上某大牛写的s...

cwalet
2014/05/21
9.6K
0
beego API开发以及自动化文档

beego API开发以及自动化文档 beego1.3版本已经在上个星期发布了,但是还是有很多人不了解如何来进行开发,也是在一步一步的测试中开发,期间QQ群里面很多人都问我如何开发,我的业余时间实在...

astaxie
2014/06/25
2.7W
22
树莓派(Raspberry Pi):完美的家用服务器

自从树莓派发布后,所有在互联网上的网站为此激动人心的设备提供了很多有趣和具有挑战性的使用方法。虽然这些想法都很棒,但树莓派( RPi )最明显却又是最不吸引人的用处是:创建你的完美家用...

异次元
2013/11/09
5.7K
8

没有更多内容

加载失败,请刷新页面

加载更多

鼠年吉祥,新年快乐

今天是大年初一,很高兴在过去一年中有您的陪伴,希望大家在新的一年中平安健康,一切顺利,加油。 邓飞 202001250539 于后园爷爷家 本文分享自微信公众号 - 育种数据分析之放飞自我(R-bre...

育种数据分析之放飞自
01/25
0
0
不烧脑、不耗时、全免费,带你0基础学Python

文末有福利 Python是人工智能的未来。 最近,电气和电子工程师协会( IEEE)发布了顶级编程语言交互排行榜:Python高居首位。 而且随着大数据和人工智能的发展,Python受到了越来越多程序员的...

kunjian
今天
0
0
R语言入门系列之一

写在前面 计算机语言的学习并不困难,关键是一定要由浅入深的实际操作练习。也许最开始的比较简单,学习者一带而过没有实际操作,之后的进一步学习很可能会陷入不知所云的困境,实际操作所带...

SYSU星空
2019/02/17
0
0
Istio-本地运行

概述 基于上一篇 Istio1.6-二进制编译和本地运行 但集中在 pilot-discovery 和 envoy(pilot-agent 大部分功能仅作为 envoy 的 watchdog,略过) NOTE: 以下的描述,相对路径都基于目录 /g...

深蓝苹果
22分钟前
9
0
基于Linux、C、JSON、Socket的编程实例(附代码)

点击上方「嵌入式大杂烩」,选择「置顶公众号」第一时间阅读编程笔记! 一、前言 之前在学习socket编程的时候有分享一个基于控制台的简易天气客户端的实现,当时提供的是window下的代码,最近...

学以解忧
2019/10/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部