递归算法详解.pdf

递 归 冯文科 一、递归的基本概念。 一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引 用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须 用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计 中，函数直接或间接调用自己，就被称为递归调用。 二、递归的最简单应用：通过各项关系及初值求数列的某一项。 在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单， 于是人们想出另一种办法来描述这种数列：通过初值及a 与前面临近几项之间的关系。 n 要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各 项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它，应该是： ⎧1,n=1 a = ⎨ n na ,n1 ⎩ n−1 如果需要写一个函数来求a 的值，那么可以很容易地写成这样： n int f(int n) { if(n==1) return 1; return n*f(n-1); } 这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一 些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二 个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为 特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问 题的解。 以上面求阶乘数列的函数 f(n)为例。如在求 f(3)时，由于3不是特殊值，因此需要计 算3* f(2)，但 f(2)是对它自己的调用，于是再计算 f(2)，2 也不是特殊值，需要计算 2* f(1)，需要知道 f(1)的值，再计算 f(1)，1是特殊值，于是直接得出 f(1)=1，返回上 1 一步，得 f(2) = 2* f(1)= 2，再返回上一步，得 f(3)= 3* f(2)= 3*2= 6，从而得最 终解。 用图解来说明，就是 f(3)的执行过程 f(2)的执行过程 f(1)的执行过程 （特殊值判断：） （特殊值判断：） （特殊值判断：） 3≠1，继续向下。 2≠1，继续向下。 1=1，由特殊情 （递归关系处理：） （递归关系处理：） 况出口直接返回1。 求3* f(2)，需要先 求2* f(1)，需要先 计算 f(2)，调用 f(2)， 计算 f(1)，调用 f(1)， 且本身挂起…… 且本身挂起…… …… …… …… …… 得到 f(2) = 2，由正 得到 f(1)=1，由正 常出口返回3*2 常出口返回2*1 下面再看一个稍复杂点的例子。 【例1】数列{a }的前几项为 n 1 1 1 1、 、 、 、…… 1+1 1 1