算法设计与分析--递归-59页文档资料

递归算法详解精编W O R D版IBM system office room 【A0816H-A0912AAAHH-GX8Q8-GNTHHJ8】递归冯文科一、递归的基本概念。

一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。

在程序设计中，函数直接或间接调用自己，就被称为递归调用。

二、递归的最简单应用：通过各项关系及初值求数列的某一项。

在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简a与前面临近几项之间的关单，于是人们想出另一种办法来描述这种数列：通过初值及n系。

要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。

比如阶乘数列1、2、6、24、120、720……如果用上面的方式来描述它，应该是：a的值，那么可以很容易地写成这样：如果需要写一个函数来求n这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。

递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。

以上面求阶乘数列的函数)f为例。

如在求)3(f时，由于3不是特殊值，因此需(n要计算)2(3f，但)2(f是对它自己的调用，于是再计算)2(f，2也不是特殊值，需要计*算)1(f，返回)1(= 2f，需要知道)1(f的值，再计算)1(f，1是特殊值，于是直接得出1*上一步，得23*)2()3(==f，从而得最终=f)1(32**)2(==f2f，再返回上一步，得6解。

用图解来说明，就是下面再看一个稍复杂点的例子。

例3.4 将下面的递归程序转化成等价的非 递归程序。 procedure P(w∶int)； begin if w>0 then begin call P(w-1)； write(w)； end； endp；







由此归纳出： n =4时是递归的出口，在退出时作5个移动 操作： move (4,5) (9,10) move (8,9) (4,5) move (2,3) (8,9) move (7,8) (2,3) move (1,2) (7,8) 如果 2n 个棋子的移动用 chess( n )表示，则 递推关系是： Move (n,n+1) (2n+1,2n+2); move (2n-1,2n) (n,n+1); call chess(n-1);

④对返回语句，如果栈不空，则依次执行如下操 作，否则结束本子程序，返回。 a.回传数据：若有变参或是函数，将其值保存 到回传变量中； b.恢复现场：从栈顶取出返址(不妨设保存到X 中)及各变量、形参的值，并退栈； c.返回，执行goto X； d.对其中的非递归调用和返回操作可照搬。
修 改 后 的 程 序
3.4

递归算法的设计
适宜于用递归算法求解的问题的充分必要条件是： ①问题 P 的描述涉及规模，即 P(size)； ②规模发生变化后，问题的性质不发生变 ③问题的解决有出口。

表现形式

procedure P(参数表)； begin if 递归出口 then 简单操作 else begin 简单操作；call P; 简单操作 end; endp;

• • • • • • 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。
9
2.1 递归的概念
例4 排列问题
递归算法生成n个元素{r1,r2,…,rn}的全排列。 设R={r1,r2,…,rn}是要进行排列的n个元素， Ri=R-{ri}。去掉元素ri。 集合X中元素的全排列记为perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一个排列 前加上前缀得到的排列。 R的全排列可归纳定义如下：板
3
计划授课时间：6～8课时
2.1 递归的概念
直接或间接地调用自身的算法称为递归算法 用函数自身给出定义的函数称为递归函数(板) 使用递归技术使算法的描述简洁、易理解。 在实时系统或嵌入系统开发中，建议不使用 递归算法 下面来看几个实例。
4
2.1 递归的概念
例1 阶乘函数(板) 可递归地定义为：高低 1 n0 其中： n! n(n 1)! n 0 n=0时，n!=1为结束条件 n>0时，n!=n(n-1)!为递归方程 结束条件也称为边界条件，这二者是递归函 数的二个要素。 T=1; //递归结束条件为循环初值 递归为递推 for (i=2;i<n+1;i++){T=T*i;} 循环低高
算法设计与分析
第二章 递归与分治策略Fra bibliotek杨圣洪
学习要点: 理解递归的概念。 掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。 （1）二分搜索技术； （2）大整数乘法； （3）Strassen矩阵乘法； （4）棋盘覆盖； （5）合并排序和快速排序； （6）线性时间选择； （7）最接近点对问题； （8）循环赛日程表。

一般地，一个递归模型是由递归出口和递归体两部分组成，前者确定 递归到何时结束，后者确定递归求解时的递推关系。
递归出口的一般格式如下：
f(s1)=m1
(2.1)
这里的s1与m1均为常量，有些递归问题可能有几个递归出口。
递归体的一般格式如下：
f(sn+1)=g(f(si)，f(si+1)，…，f(sn)，cj，cj+1，…，cm) (2.2)
struct LNode *next; } LinkList;
为什么可以这样 递归定义类型
结构体LNode的定义中用到了它自身，即指针域next是一种指向自 身类型的指针，所以它是一种递归数据结构。
不带头结点单链表示意图
以L为首结点指针的单链表
L
a1
a2
…
an ∧
以L->next为首结点指针的单链表
盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以 插在X、Y和Z中任一塔座；任何时候都不能将一个较大的盘片放在较小的 盘片上。
设计递归求解算法，并将其转换为非递归算法。
设Hanoi(n，x，y，z)表示将n个盘片从x通过y移动到z上， 递归分解的过程是：
Hanoi(n，x，y，z)
Hanoi(n-1，x，z，y)； move(n，x，z):将第n个圆盘从x移到z； Hanoi(n-1，y，x，z)
return(L->data+Sum(L->next)); }
【例2.2】分析二叉树的二叉链存储结构的递归性，设计求非
空二叉链bt中所有结点值之和的递归算法，假设二叉链的data域为 int型。
解：二叉树采用二叉链存储结构，其结点类型定义如下：