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页

正式车牌租赁合同草案 5页

中国证券投资基金发展的影响因素研究 2页

森林资源经营权流转合同 6页

中国工业产权研究会工作报告(摘要) 2页

中国企联研究探讨雇主责任标准 2页

个人所得税存在的问题及改革路径分析 2页

东海表层水温预报方法的初步研究 2页

世界主要国家的电碳和碳素研究团体 2页

不同类型大蒜的辐射保鲜效果研究 2页

上海经济区将举办水产养殖技术、信息交易会 2页

上海大气闪烁的孔径平滑因子及其在激光工程中.. 2页

2025年幼儿园教师新学期工作计划 幼儿园工作计.. 13页

2025年幼儿园教师师德师风演讲稿范文 16页

2025年幼儿园教师个人发展计划总结 9页

2025年幼儿园托班教学工作计划样本00字3篇 18页

三氯化磷法合成杀虫脒的全分析及其热稳定性的.. 2页

《太空一日》优秀课件 25页

2025年幼儿园师德演讲论文5分钟 9页

丁炔二醇催化合成反应的本征动力学研究 2页

一起制氧机组分子筛控制系统故障分析及解决 2页

一类二级供应链分销系统的成本优化模型 2页

一种间接测量矿井高压电网电容电流的新方法 2页

2025年幼儿园安全责任书最新版 15页

一种测量残余应力沿表面层深度分布的有效方法.. 2页

一种数控车床自动送料装置的设计研究 2页

机械装备长途运输合同3篇 91页

机场候机厅墙纸装饰协议3篇 54页

二年级数学上册二单元试卷(带答案) 7页

景观装修工程劳动合同3篇 50页