61递归的概念 若一个算法直接的或间接的调用自己本身,则称这 个算法是递归算法。 存在算法调用自己的情况: (1)问题的定义是递推的 阶乘函数的常见定义是 M= 二 X(x-1x…×1 当n>
2 存在算法调用自己的情况： 若一个算法直接的或间接的调用自己本身，则称这 个算法是递归算法。 （1）问题的定义是递推的 阶乘函数的常见定义是： 6.1递归的概念
也可定义为: 彐 = N|= 写成函数形式,则为 当当 时 时 这种函数定义的方法是用阶乘函数自己本身定义了阶 乘函数,称公式(6-3)是阶乘函数的递推完义式
3 也可定义为： 写成函数形式，则为： 这种函数定义的方法是用阶乘函数自己本身定义了阶 乘函数，称公式（6 – 3）是阶乘函数的递推定义式
(2)问题的解法存在自调 个典型的例子是在有序数组中查找一个数据元素是否 存在的折半查找算法
4 （2）问题的解法存在自调用 一个典型的例子是在有序数组中查找一个数据元素是否 存在的折半查找算法
下 元赤但 17 1 IAid 二次:下 元赤伯 mid Ia[ma] 界三:下坪 元但 萬=[m副 ber chaq
5
62递归算法的执行过程 例6-1给出按照公式6-3计算阶乘函数的递归算法 并给出n=3时递归算法的执行过程。 设计:按照公式6-3计算阶乘函数的递归算法如下:
6 6.2递归算法的执行过程 例6-1 给出按照公式6-3计算阶乘函数的递归算法， 并给出n = 3时递归算法的执行过程。 设计：按照公式6-3计算阶乘函数的递归算法如下：
long int Fact(int n) ntx: long int y if(n<0) /n<0时阶乘无定义 { printi(“参数错!"); return -1 if(n==O)return 1 else t y=Fact(n-1) 递归调用 return n * y;
7 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(vo long int fn; fn=Fact(3); 主函数用实参=3调用了递归算法Fat(3),而 Fact(3)要通过调用Fact(2)、Fact(2)要通过调用Fact(1) Fact(1)要通过调用Fact(0来得出计算结果。Fac(3)的 递归调用过程如图6-2所示
8 设计主函数如下 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所示
fact(3) fact fa ct fetus fact(e) fact(2) Fact(1) fect retum[3*y retum( 27) return(*) 图6-2Fact(3)的递归调用执行过程
9 图6-2 Fact(3)的递归调用执行过程
例6-2给出在有序数组a中查找数据元素x是否存在的 递归算法,并给出如图6-1所示实际数据的递归算法的 执行过程。递归算法如下:
10 例6-2 给出在有序数组a中查找数据元素x是否存在的 递归算法，并给出如图6-1所示实际数据的递归算法的 执行过程。递归算法如下：
int BSearch(int al int x, int low, int high) Int mi id if(low >high)return-1; 查找不成功 mid=(low t high)/2; if(x= amid) return mid;/查找成功 else if(x a midd return BSearch(a, x, low, mid-1); /在庄下半区查找 ese return bsearch(a,x,mid1,high);在上半区查找
11 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); //在上半区查找 }