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所 示，其中，实线箭头表示函数调用，虚线箭头表示函数返回，此 函数在返回时函数名将带回返回值