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;

最近更新

2025年度商业街区停车位租赁及充电桩配套服务.. 9页

2025年度商业办公家具租赁及保养服务合同 9页

2025年度员工股权激励与公司内部审计协议 7页

2025年度员工入股项目投资合作协议 7页

2025年度吊车安全协议责任书(适用于矿山开采.. 8页

2025年度合同审批流程优化与电子化管理服务合.. 9页

2025年度合伙投资无人机研发制造合同 8页

2025年度可再生能源用地地基转让协议书模板 9页

2025年度厨房智能化设计顾问服务合同 8页

2025年度厂家与销售店客户满意度提升合同协议.. 8页

2025年度单身公寓租赁与家政服务合同 9页

2025年度医院附属检验检测中心租赁合同 9页

2025年度医院与培训机构合作医护人员培训合同.. 9页

2025年度医疗耗材租赁及维护保养服务合同 9页

2025年度医疗器械包装与运输服务合同 8页

2025年度区域代理商合同全新版:高端化妆品区.. 8页

2025年度化妆品跨境电商物流与仓储合作协议 9页

2025年度劳动合同电子版远程办公安全协议合同.. 8页

2025年度劳务合同补充协议:养老服务机构护理.. 9页

2025年度剧组与演员影视作品主题展览合作合同.. 8页

2025年度分红权股权激励计划合同书 8页

2025年度出租车公司车辆安全检测与维护合同 9页

2025年度冷链运输冷链物流冷链产品冷链配送服.. 9页

胸腔积液的长期随访研究-全面剖析 25页

2025年度农村房屋拆迁补偿与农村土地流转合同.. 7页

2025年度农村墓地墓碑定制与销售合同 9页

2025年度农村合作社农业综合开发项目土地承包.. 9页

2025年度农副产品品牌推广与销售合作协议 8页

第03讲中心对称(知识解读+达标检测)-2024-2.. 19页

2025年循环流化床锅炉合作协议书 68页