折半查找算法62递归算法的执行过程例1.PPT

第6章 递归算法 6.1 递归的概念 6.2 递归算法的执行过 6.3 递归算法的设计方法 6.4 递归过程和运行时栈 6.5 递归算法的效率分析 6.6 递归算法到非递归算法的转换 6.7 设计举例 本章主要知识点： 递归的概念 递归算法的设计方法 递归算法的执行过程 递归算法的效率 6.1 递归的概念 若一个算法直接地或间接地调用自己本身，则称这个算法是递归算法。 1.问题的定义是递归的 例如：阶乘函数的定义 1 当n=0时 n!= n* (n-1) !当n0时 2. 问题的解法存在自调用 例如：折半查找算法 6.2 递归算法的执行过程 例1：阶乘的递归算法 public static long fact(int n) throws Exception{ int x; long y; if(n 0){ throw new Exception(参数错！); } if(n == 0) return 1; else{ x = n - 1; y = fact(x); return n * y; } } 设计一个计算3！得主函数如下,用来说明递归算法的执行过程： public static void main(String[] args){ long fn; try{ fn = fact(3); System.out.println(fn = + fn); } catch(Exception e){ System.out.println(e.getMessage()); } } 递归调用执行过程： 例2：折半查找递归算法 public static 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); //在下半区查找 } 测试主函数设计如下： public static void main(String[] args){ int[] a = {1, 3, 4, 5, 17, 18, 31, 33}; int x = 17; int bn; bn = bSearch(a, x, 0, 7); if(bn == -1) System.out.println(x不在数组a中); else System.out.println(x在数组a中，下标为 + bn); } 递归调用执行过程： 6.3 递归算法的设计方法 适宜于用递归算法求解的问题的充分必要条件是： （1）问题具有某种可借用的类同自身的子问题描述的性质 （2）某一有限步的子问题（也称作本原问题）有直接的解存在。 当一个问题存在上述两个基本要素时，设计该问题的递归算法的方法是： （1）把对原问题的求解表示成对子问题求解的形式。 （2）设计递归出口。 例 ：汉诺塔问题的递归求解过程 public static void towers(int n, char fromPeg, char toPeg, char auxPeg){ if(n == 1){ System.out.println(move disk 1 from peg + fromPeg + to peg + toPeg); return; } towers(n-1, fromPeg, auxPeg, toPeg); System.out.println(move disk + n + from peg + fromPeg + to peg + toPeg); towers(n-1, auxPeg, toPeg, fromPeg); } public static void main(String[] args){ towers(4,