第5章递归算法5.1递归的概念5.2递归算法的执行过程5.3递归算法的设计方法5.4设计举例
第5章 递归算法 5.1 递归的概念 5.2 递归算法的执行过程 5.3 递归算法的设计方法 5.4 设计举例
5.1递归的概念若一个算法直接的或间接的调用自己本身，则称这个算法是递归算法存在算法调用自己的情况：1问题定义是递推的阶乘函数的常见定义是：当n=0时2当n>0时nx(n-x...x1
5.1 递归的概念 存在算法调用自己的情况： 若一个算法直接的或间接的调用自己本身，则称这 个算法是递归算法。 阶乘函数的常见定义是： 1 问题定义是递推的
也可定义为：当n=0时21当n>0时nx(n-1)!写成函数形式，则为：当n=时当n>时n*f这种函数定义的方法是用阶乘函数自己本身定义了阶乘函数，称公式（6-3）是阶乘函数的递推定义式
也可定义为： 写成函数形式，则为： 这种函数定义的方法是用阶乘函数自己本身定义了阶乘 函数，称公式（6 – 3）是阶乘函数的递推定义式
2.问题的解法存在自调用查找17例如：折半查找算法357下标01246第一次：135417183133元素值44lowmidhighx>a[mid]023457第二次：下标16134517183133元素值444lowmidhighx<a[mid]35701246下标第三次：351718313314元素值Nlowx==a[mid]highmid
2. 问题的解法存在自调用 例如：折半查找算法 第 一 次 : 下 标 0 1 2 3 4 5 6 7 元 素 值 1 3 4 5 1 7 1 8 3 1 3 3 第 二 次 : 下 标 0 1 2 3 4 5 6 7 元 素 值 1 3 4 5 1 7 1 8 3 1 3 3 第 三 次 : 下 标 0 1 2 3 4 5 6 7 元 素 值 1 3 4 5 1 7 1 8 3 1 3 3 l o w m i d h i g h l o w m i d h i g h l o w h i g h m i d x > a [ m i d ] x < a [ m i d ] x = = a [ m i d ] 查找17
5.2递归算法的执行过程例1：阶乘的递归算法public static long fact(int n)long y;if (n< 0)(thrownewException("参数错！")1if (n == 0) return 1;else{y = fact(n-1);return n * y;77
5.2 递归算法的执行过程 例1：阶乘的递归算法 public static long fact(int n){ long y; if (n < 0){ throw new Exception("参数错！"); } if (n == 0) return 1; else { y = fact(n-1); return n * y; } }