文档介绍:递 归
冯文科
一、递归的基本概念。
一个函数、概念或数学结构,如果在其定义或说明内部直接或间接地出现对其本身的引用,或者是为了描述问题的某一状态,必须要用至它的上一状态,而描述上一状态,又必须用到它的上一状态……这种用自己来定义自己的方法,称之为递归或递归定义。在程序设计中,函数直接或间接调用自己,就被称为递归调用。
二、递归的最简单应用:通过各项关系及初值求数列的某一项。
在数学中,有这样一种数列,很难求出它的通项公式,但数列中各项间关系却很简单,于是人们想出另一种办法来描述这种数列:通过初值及与前面临近几项之间的关系。
要使用这样的描述方式,至少要提供两个信息:一是最前面几项的数值,一是数列间各项的关系。
比如阶乘数列
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;