1 / 61
文档名称:

递归算法详解.docx

格式:docx   大小:177KB   页数:61页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

递归算法详解.docx

上传人:iris028 2020/12/9 文件大小:177 KB

下载得到文件列表

递归算法详解.docx

相关文档

文档介绍

文档介绍:递  归
冯文科
一、递归的基本概念。
一个函数、概念或数学结构,如果在其定义或说明内部直接或间接地出现对其本身的引用,或者是为了描述问题的某一状态,必须要用至它的上一状态,而描述上一状态,又必须用到它的上一状态……这种用自己来定义自己的方法,称之为递归或递归定义。在程序设计中,函数直接或间接调用自己,就被称为递归调用。
二、递归的最简单应用:通过各项关系及初值求数列的某一项。
在数学中,有这样一种数列,很难求出它的通项公式,但数列中各项间关系却很简单,于是人们想出另一种办法来描述这种数列:通过初值及与前面临近几项之间的关系。
要使用这样的描述方式,至少要提供两个信息:一是最前面几项的数值,一是数列间各项的关系。
比如阶乘数列
1、2、6、24、120、720……
如果用上面的方式来描述它,应该是:
如果需要写一个函数来求的值,那么可以很容易地写成这样:
int f(int n)
{
if(n==1)
return 1;
return n*f(n-1);
}
这就是递归函数的最简单形式,从中可以明显看出递归函数都有的一个特点:先处理一些特殊情况——这也是递归函数的第一个出口,再处理递归关系——这形成递归函数的第二个出口。
递归函数的执行过程总是先通过递归关系不断地缩小问题的规模,直到简单到可以作为特殊情况处理而得出直接的结果,再通过递归关系逐层返回到原来的数据规模,最终得出问题的解。
以上面求阶乘数列的函数为例。如在求时,由于3不是特殊值,因此需要计算,但是对它自己的调用,于是再计算,2也不是特殊值,需要计算,需要知道的值,再计算,1是特殊值,于是直接得出,返回上一步,得,再返回上一步,得,从而得最终解。
用图解来说明,就是
的执行过程
(特殊值判断:)
,继续向下。
(递归关系处理:)
求,需要先计算,调用,且本身挂起……
……
……
得到,由正常出口返回
的执行过程
(特殊值判断:)
,继续向下。
(递归关系处理:)
求,需要先计算,调用,且本身挂起……
……
……
得到,由正常出口返回
的执行过程
(特殊值判断:)
,由特殊情况出口直接返回1。
下面再看一个稍复杂点的例子。
【例1】数列的前几项为
1、、、、……
输入,编程求的精确分数解。
分析:
这个题目较易,发现,其它情况下有。如要求实数解的话,这基本已经可以写出递归函数了。但由于题目要求精确的分数解,还需做一些调整。设,则由递归关系,有,再约分化简,即得。但发现一个问题:求出时,需要返回两个整数:分子与分母,而通常的函数只能返回一个整数。
这个问题一般有两类解决办法,一种是让求值函数返回一个结构体变量,这样就可以返回两个变量了(其实还可以不只两个呢);另一种是在求值函数的参数表中加入两个指针变量或引用变量,通过参数给带回数值。但由于后一种做法会使程序结构不清晰——返回值是由参数表得到的,因此我们使用前一种方法。
另外,在通过得出后,就已经是最简分数了,无须化简。证明如下:
若是最简分数,即说明的最大公约数为1,即对任何,都有与不全为0,不防记、,则有
只要与不全为0,且,就有与不全为0。因此对任何的,有与不全为0。
而对于的情况而言,记,则有
由于,因此同样有与不全为0。
所以对任意,都有与不全为0,因此它们的最大公约数为1,即是最简分数。虽然这是个要求(即)是最简分数的结论,但由于数列第二项为,是最简分数,因此可以证明第三项也是最简分数,同时也证明对所有的,求出的就是最简分数,无须化简。
具体代码如下:
//
#include <iostream>
using namespace std;
struct FS
{
unsigned long long q, p;
};
FS f(int n)
{
FS r;
if(n==1)
{
=1;
=1;
return r;
}
r=f(n-1);
=+;
=-;
return r;

最近更新

关于综采工作面最佳长度的数理分析与探讨 2页

关于生产资料双轨制价格的思考 2页

2025年肾炎症状与治疗攻略 29页

关于江苏太湖地区农业发展问题的探讨 2页

关于机制转换过程中企业开户问题的实证研究 2页

关于我国天然气工业的分析与建议 2页

2025年特种纤维项目合作计划书 45页

关于开征“劳动技术资源占用税”的探讨 2页

2025年环保仪器仪表项目合作计划书 74页

关于层次分析法中判断矩阵间接给出法的讨论 2页

2025年管理心理学高效复习策略解析 53页

关于商品学研究对象问题的探讨 2页

《雄激素与男科疾病》 78页

2025年深度解读护理服务本质与价值 30页

2025年护理职业转型与发展之路 23页

六省市自治区使用外棉学术讨论会 2页

2025年广泛性宫颈切除+盆腔淋巴结清扫手术指南.. 36页

全国重点城市食品工业技术协作会在沪召开 2页

2025年多瑞吉缓解消化道癌痛高效方案 51页

2025年呼吸衰竭患者照护指南 49页

2025年医疗机构护理安全策略与实施要点 51页

2025年全面护理体检攻略 11页

2025年中医减肥美容实操教程 32页

关于普法教育心得体会(24篇) 49页

2025年脑梗塞精准诊断与鉴别策略 62页

单位车辆委托个人办理的委托书范本(6篇) 4页

2025年无针水光产品培训课件PPT 33页

中医技能知识考试题+答案 20页

天津春季高考试题及答案 4页

《在市民政局以案促改警示教育大会上的讲话》.. 7页