递归算法详解

《递归算法详解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、信息：一是最前面几项的数值，一是数列间各项的关系。比如阶乘数列1、2、6、24、120、720……如果用上面的方式来描述它，应该是：如果需要写一个函数来求的值，那么可以很容易地写成这样：intf(intn){if(n==1)return1;returnn*f(n-1);}这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为特殊情况处理而得出直接的结果，再通过递归关系逐

3、层返回到原来的数据规模，最终得出问题的解。以上面求阶乘数列的函数为例。如在求时，由于3不是特殊值，因此需要计算，但是对它自己的调用，于是再计算，2也不是特殊值，需要计算，需要知道的值，再计算，1是特殊值，于是直接得出71，返回上一步，得，再返回上一步，得，从而得最终解。用图解来说明，就是的执行过程（特殊值判断：），继续向下。（递归关系处理：）求，需要先计算，调用，且本身挂起………………得到，由正常出口返回的执行过程（特殊值判断：），继续向下。（递归关系处理：）求，需要先计算，调用，且本身挂起………………得到，由正常出口返回的执行过程（特殊值判断：），由

4、特殊情况出口直接返回1。下面再看一个稍复杂点的例子。【例1】数列的前几项为1、、、、……输入，编程求的精确分数解。分析：这个题目较易，发现，其它情况下有。如要求实数解的话，这基本已经可以写出递归函数了。但由于题目要求精确的分数解，还需做一些调整。设，则由递归关系，有，再约分化简，即得71。但发现一个问题：求出时，需要返回两个整数：分子与分母，而通常的函数只能返回一个整数。这个问题一般有两类解决办法，一种是让求值函数返回一个结构体变量，这样就可以返回两个变量了（其实还可以不只两个呢）；另一种是在求值函数的参数表中加入两个指针变量或引用变量，通过参数给带回

5、数值。但由于后一种做法会使程序结构不清晰——返回值是由参数表得到的，因此我们使用前一种方法。另外，在通过得出后，就已经是最简分数了，无须化简。证明如下：若是最简分数，即说明的最大公约数为1，即对任何，都有与不全为0，不防记、，则有只要与不全为0，且，就有与不全为0。因此对任何的，有与不全为0。而对于的情况而言，记，则有由于，因此同样有与不全为0。所以对任意，都有与不全为0，因此它们的最大公约数为1，即是最简分数。虽然这是个要求（即）是最简分数的结论，但由于数列第二项为，是最简分数，因此可以证明第三项也是最简分数，同时也证明对所有的，求出的就是最简分数，

6、无须化简。具体代码如下：//Exam1.cpp#includeusingnamespacestd;structFS71{unsignedlonglongq,p;};FSf(intn){FSr;if(n==1){r.q=1;r.p=1;returnr;}r=f(n-1);r.p=r.p+r.q;r.q=r.p-r.q;returnr;}intmain(){FSr;intn;cin>>n;r=f(n);cout<

7、下的让下一步去做吧。对大多数问题而言，当它的规模缩小至“特殊情况”时，都可以非常轻易地得出问题的解，因此我们不过多地讨论“特殊情况”，只详细地讨论递归关系的确定。寻找递归关系，最低标准是它能使问题的规模变小，且变小后的问题与原问题在本质上是一样的。当找到递归关系后，我们的递归函数只须处理特殊情况与递归关系，不需要处理其它的信息——至于下一步的事情，就让下一步去做吧。另一个需要考虑的事情就是递归函数的参数表，首先，在通常情况下，参数表都要使用变量参数，且递归函数中尽量使用局部变量——这会减少很多不必要的麻烦；其次，参数表中，大多都有一个表示当前在执行第几

8、步的参数。71【例2】下图是一个有向图，输入，打印的所有路径。1357902468分析：仔细研