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;

最近更新

关于班级班长的工作总结(9篇) 34页

劳动的心得体会 27页

合租租房合同标准版(28篇) 93页

地理教学总结集锦十篇 25页

2025年心理异常与心理健康研究 94页

二零二五年度企业并购中介服务协议 8页

二零二五年度企业员工餐饮服务外包管理合同 8页

2025年北京协和医院学习交流成果分享 134页

2025年化工脂肪酸应用领域探究 77页

二零二五年度人工智能众筹合作分红协议 8页

2025年刮痧减肥法助降血脂改善单纯肥胖 106页

二零二五年度互联网行业劳动合同法实施细则与.. 7页

2025年冠脉搭桥术后护理要点解析 21页

二零二五年度临时项目经理项目协作服务协议 8页

二零二五年度临床研究药物临床试验项目进度监.. 9页

2025年愚公移山读后感精选6篇600字 7页

二零二五年度个体劳动协议(区块链技术顾问).. 8页

二零二五年度个人货车租赁与车辆维修合同 8页

二零二五年度个人绩效合同制员工岗位评估标准.. 8页

二零二五年度个人租房合同协议范本(含租客亲.. 7页

二零二五年度个人汽车购置贷款两个人借款合同.. 8页

2025年情人之间有爱情的语录吗 10页

二零二五年度个人房屋转让合同范本(含车位).. 9页

二零二五年度个人工资合同:航空航天行业个人.. 8页

2025年儿童喘息症状的精准诊断策略 50页

二零二五年度个人养老保障贷款二零二五年度还.. 8页

二零二五年度个人住房商业贷款合同 8页

2025年保脾胰尾切除手术全解析 47页

二零二五年度专业级产后护理个人雇佣月嫂合同.. 8页

力合股份有限公司的供应链风险管理研究-全面剖.. 28页