湖北工业大学：《数据结构》第6章 递归

6.1递归的概念 若一个算法直接的或间接的调用自己本身,则称这 个算法是递归算法。 存在算法调用自己的情况: (1)问题的定义是递推的 阶乘函数的常见完义是: 当n=0时 xx(-1x…×1 当n>0时

2 存在算法调用自己的情况： 若一个算法直接的或间接的调用自己本身，则称这 个算法是递归算法。 （1）问题的定义是递推的 阶乘函数的常见定义是： 6.1递归的概念

也可定义为: n×(2-1) 当x>0时 写成函数形式,则为 当n=0时 f(n)= 6-3 n米f(x-1 当n>时 这种函数定义的方法是用阶乘函数 自己本身定义了阶乘函数,称公式(6 3)是阶乘函数的递推定义式

3 也可定义为： 写成函数形式，则为： 这种函数定义的方法是用阶乘函数 自己本身定义了阶乘函数，称公式（6 – 3）是阶乘函数的递推定义式

(2)问题的解法存在自调用 个典型的例子是在有序数组中查找一个数据 元素是否存在的折半查找算法。 下 元亲值 a [ md] 第二次:下标 元素值 17 31 hich r G[mid] 第三次:下标 元亲值 囝6-1析半查我过程 ber ch=

4 （2）问题的解法存在自调用 一个典型的例子是在有序数组中查找一个数据 元素是否存在的折半查找算法

62递归算法的执行过程 例6-1给出按照公式6-3计算阶乘函数的递归算法 并给出n=3时递归算法的执行过程。 设计:按照公式6-3计算阶乘函数的递归算法如下: long int Fact(int n) int x long int y; if(n<0)*(n<0时阶乘无定义* printf(“参数错!”); return -1: if(n ==0)return 1; else{y= Fact(n-1)/递归调用/ return n*y;

5 6.2递归算法的执行过程 例6-1 给出按照公式6-3计算阶乘函数的递归算法， 并给出n = 3时递归算法的执行过程。 设计：按照公式6-3计算阶乘函数的递归算法如下： long int Fact(int n) { int x; long int y; if(n < 0) /*(n < 0时阶乘无定义*/ { printf(“参数错！”); return -1; } if(n == 0) return 1; else {y = Fact(n - 1); /*递归调用*/ return n * y; } }

为说明该递归算法的执行过程,设计主函数如下 void main(void) long int fn; fn Fact (3: 主函数用实参n=3调用了递归算法Fact(3),而Fact(3)要通 过调用Fact(2)、Fact(2)要通过调用Fact(1)、Fact(1)要通过调 用Fact(0)来得出计算结果。Fact(3)的递归调用过程如图62所 示,其中,实线箭头 数调用,虚线箭头表示函数返回,此 函数在返回时函数名将带回返回值

6 为说明该递归算法的执行过程，设计主函数如下 void main(void) { long int fn; fn = Fact(3); } 主函数用实参n = 3调用了递归算法Fact(3)，而Fact(3)要通 过调用Fact(2)、Fact(2)要通过调用Fact(1)、Fact(1)要通过调 用Fact(0)来得出计算结果。Fact(3)的递归调用过程如图6-2所 示，其中，实线箭头表示函数调用，虚线箭头表示函数返回，此 函数在返回时函数名将带回返回值

main fact(3) fact(2) fact fetus return(3*y) retu〕 return(it) 图62Fac3的递归两用执行过程 例6-2给出在有序数组a中查找数据元素k是否存在的递归算法, 并给出如图6-1所示实际数据的递归算法的执行过程。 设计:算法的参数包括:有序数组a,要查找的数据元素x 数组下界下标ow,数组上界下标high。当在数组a中查找到数据 元素x时函数返回数组的下标;当在数组a中查找不到数据元素x 时函数返回1

7 例6-2 给出在有序数组a中查找数据元素x是否存在的递归算法， 并给出如图6-1所示实际数据的递归算法的执行过程。 设计：算法的参数包括：有序数组a，要查找的数据元素x， 数组下界下标low，数组上界下标high。当在数组a中查找到数据 元素x时函数返回数组a的下标；当在数组a中查找不到数据元素x 时函数返回-1

递归算法如下: int BSearch (int a[ int x, int low, int high) int mid: if(low> high)return-1; 八查找不成功*/ mid =(low high)/2; f(x==a[mid) return mid;/查找成功*/ else if(x< a[midD) return bsearch(a,x,low,mid-1);/在下半区查找* else return bsearch(a,x,mid+1,high);/在上半区查找*

8 递归算法如下： int BSearch(int a[], int x, int low, int high) { int mid; if(low > high) return -1; /*查找不成功*/ mid = (low + high) / 2; if(x == a[mid]) return mid; /*查找成功*/ else if(x < a[mid]) return BSearch(a, x, low, mid-1); /*在下半区查找*/ else return BSearch(a, x, mid+1, high); /*在上半区查找*/ }

测试主函数设计如下: include main (void) {inta=11,3,4,517,18,31,33} int x=17. int bn: bn BSearch(a, x, 0,7: if(bn==-1) printf("x不在数组a中"); else printi("x在数组a的下标%d中",bn)

9 测试主函数设计如下： # include main(void) { int a[] = {1, 3, 4, 5, 17, 18, 31, 33}; int x = 17; int bn; bn = BSearch(a, x, 0,7); if(bn == -1) printf("x不在数组a中"); else printf("x在数组a的下标%d中", bn); }

BSearch(a,x20,7)的递归调用过程姬图6-3所示 其中,实箭头表示函数凋用,虚箭头表示函数的返回值 mainO 图6-3 BSearch(a,x,0,7)的递归调用过程 brcBSearch(a,z,0, 7) bIcBSearch(a,z,0, 7) brcBSearch(a, z, 4, 7 brEBSea rch(a, z,4, 4) d=3 mi d=5 mi d=4 return(bneBSear ch(a, z, 4, 7) return(bn=BS earch(a, z, 4. 47) re turn〔4)

10 BSearch(a, x, 0,7)的递归调用过程如图6-3所示， 其中，实箭头表示函数调用，虚箭头表示函数的返回值

63递归算法的设计方法 递归算法既是一种有效的算法设计方法,也是一种有效的分析问题的方 法。递归算法求解问题的基本思想是:对于一个较为复杂的问题,把原问题 分解成若干个相对简单且类同的子问题,这样较为复杂的原问题就变成了相 对简单的子问题;而简单到一定程度的子问题可以直接求解;这样,原问题 就可递推得到解 并不是每个问题都适宜于用递归算法求解。适宜于用递归算法求解的问 题的充分必要条件是: (1)问题具有某种可借用的类同自身的孑问题描述的性质; (2)某一有限步的子问题(也称作本原问题)有直接的解存在。 当一个问题存在上述两个基本要素时,设计该问题的递归算法的方法是: (1)把对原问题的求解设计成包含有对子问题求解的形式 (2)设计递归出口

11 6.3递归算法的设计方法 递归算法既是一种有效的算法设计方法，也是一种有效的分析问题的方 法。递归算法求解问题的基本思想是：对于一个较为复杂的问题，把原问题 分解成若干个相对简单且类同的子问题，这样较为复杂的原问题就变成了相 对简单的子问题；而简单到一定程度的子问题可以直接求解；这样，原问题 就可递推得到解。 并不是每个问题都适宜于用递归算法求解。适宜于用递归算法求解的问 题的充分必要条件是： （1）问题具有某种可借用的类同自身的子问题描述的性质； （2）某一有限步的子问题（也称作本原问题）有直接的解存在。 当一个问题存在上述两个基本要素时，设计该问题的递归算法的方法是： （1）把对原问题的求解设计成包含有对子问题求解的形式。 （2）设计递归出口