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;

最近更新

公务员年度考核工作总结最新与公务员年度考核.. 8页

2025年度委托收款服务提供商代理合同 8页

2025年度夫妻婚内借款协议附电子版及法律咨询.. 10页

2025年度大米加工技术改造与节能减排合同 9页

2025年度大型牧场养牛合作及技术服务合同 9页

2025年度多人合伙创立文化体验馆合作协议 9页

2025年度外墙抹灰工程节能评估合同 7页

2025年度塔吊安装与拆卸施工安全评估合同 8页

2025年度城市绿地场地无偿使用与生态保护协议.. 8页

2025年度城市中心区域二手房买卖中介佣金合同.. 8页

2025年度地下室租赁合同——城市地下公共服务.. 8页

2025年度土地流转与农村人才引进培养协议 8页

2025年度国际贸易出口合同履行流程规范图 9页

2025年度国有企业员工健康体检全面合作合同 9页

2025年度商铺店面LED照明系统改造装修协议 9页

细胞膜动态调控机制-第1篇-全面剖析 25页

2025年度员工解除劳动合同经济补偿及离职手续.. 8页

2025年度员工入股股权激励合同协议书 7页

2025年度合资建筑节能照明系统研发合同 8页

2025年度合作建房建筑安全防护合同 9页

2025年度合伙人个人股权转让合同 7页

2025年度双方自愿调解协议书:金融领域信用纠.. 7页

2025年度原创设计商标授权与推广合作协议 8页

2025年度卫生间防水施工与智能化系统集成合同.. 8页

2025年度华过户协议书:个人二手车交易过户安.. 9页

2025年度医院与医院间医疗设备租赁合同 9页

2025年度医疗机构影像科技师岗位聘用合同书 7页

2025年度劳动合同电子台账系统定制开发与实施.. 9页

2025年度动产租赁担保合同成立与生效规定 9页

2025年度创意设计街区商铺租赁合同 8页