Java语言程序设计-基础篇-中文ppt-第二十章

1第20章递归2动因假设希望找出某目录下所有包含某个特定单词的文件，该如何解决这个问题呢？有几种方法可以解决这个问题。一个直观且有效的解决方法是使用递归在子目录下递归地搜索所有文件。3动因经典的八皇后难题就是将八个皇后放在棋盘上，而没有任何两个皇后可以互相攻击（既不会出现两个皇后在同一行、同一列或者同一条对角线上的情况），如图所示。该如何编写程序解决这个问题呢？一个好的办法就是使用递归。4学习目标了解什么是递归方法以及使用递归方法的好处（第20.1节）。决定递归方法的基础情况（第20.2-20.5节）。理解在调用栈中如何处理递归方法的调用（第20.2-20.3节）。使用递归解决问题（第20.2-20.5节）。使用一个重载的辅助方法派生一个递归方法（第20.5节）。使用递归获取目录大小（第20.6节）。使用递归解决汉诺塔问题（第20.7节）。使用递归绘制分形（第20.8节）。理解递归和迭代之间的联系和区分（第20.9节）。5计算阶乘factorial(0)=1;factorial(n)=n*factorial(n-1);n!=n*(n-1)!ComputeFactorial6计算阶乘factorial(3)动画factorial(0)=1;factorial(n)=n*factorial(n-1);7计算阶乘factorial(3)=3*factorial(2)

动画factorial(0)=1;factorial(n)=n*factorial(n-1);8计算阶乘factorial(3)=3*factorial(2)=3*(2*factorial(1))

动画factorial(0)=1;factorial(n)=n*factorial(n-1);9计算阶乘factorial(3)=3*factorial(2)=3*(2*factorial(1))=3*(2*(1*factorial(0)))

动画factorial(0)=1;factorial(n)=n*factorial(n-1);10计算阶乘factorial(3)=3*factorial(2)=3*(2*factorial(1))=3*(2*(1*factorial(0)))=3*(2*(1*1)))

动画factorial(0)=1;factorial(n)=n*factorial(n-1);11计算阶乘factorial(3)=3*factorial(2)=3*(2*factorial(1))=3*(2*(1*factorial(0)))=3*(2*(1*1)))=3*(2*1)动画factorial(0)=1;factorial(n)=n*factorial(n-1);12计算阶乘factorial(3)=3*factorial(2)=3*(2*factorial(1))=3*(2*(1*factorial(0)))=3*(2*(1*1)))=3*(2*1)=3*2动画factorial(0)=1;factorial(n)=n*factorial(n-1);13计算阶乘factorial(3)=3*factorial(2)=3*(2*factorial(1))=3*(2*(1*factorial(0)))=3*(2*(1*1)))=3*(2*1)=3*2=6动画factorial(0)=1;factorial(n)=n*factorial(n-1);14跟踪递归阶乘动画执行factorial(4)15跟踪递归阶乘动画执行factorial(3)16跟踪递归阶乘动画执行factorial(2)17跟踪递归阶乘动画执行factorial(1)18跟踪递归阶乘动画执行factorial(0)19跟踪递归阶乘动画返回120跟踪递归阶乘动画返回factorial(0)21跟踪递归阶乘动画返回factorial(1)22跟踪递归阶乘动画返回factorial(2)23跟踪递归阶乘动画返回factorial(3)24跟踪递归阶乘动画返回factorial(4)25factorial(4)跟踪堆栈变化26其它例子f(0)=0;f(n)=n+f(n-1);27斐波那契数斐波那契

数列:01123581321345589…

下标:01234567891011

fib(0)=0;fib(1)=1;fib(index)=fib(index-1)+fib(index-2);index>=2fib(3)=fib(2)+fib(1)=(fib(1)+fib(0))+fib(1)=(1+0)+fib(1)=1+fib(1)=1+1=2ComputeFibonacci28斐波那契数（续）29递归的特点所有的递归方法都具有以下特点：使用一个或多个基础情况（最简单的情况）来停止递归。每次递归调用都会简化原始问题，让它不断地接近基础情况，直到它变成这种基础情况为止。通常，要使用递归解决问题，就要将这个问题分解为子问题。如果子问题像原始问题一样，那你可以递归地应用同样的方法去解决子问题。本质上讲，每个子问题几乎与原始问题是一样的，只是规模小一些。30使用递归解决问题考虑打印一条消息n次的简单问题。可以将这个问题分解为两个子问题：一个是打印消息一次，另一个是打印消息n-1次。第二个问题与原始问题是一样的，只是规模小一些。这个问题的基础情况是n==0。可以使用递归来解决这个问题，如下所示：publicstaticvoidnPrintln(Stringmessage,inttimes){if(times>=1){System.out.println(message);nPrintln(message,times-1);}//Thebasecaseistimes==0}31以递归的思路进行思考如果以递归的思路进行思考，本书前面章节中的许多问题都可以用递归来解决。例如：对程序清单7.1中的回文问题，我们可以用递归的方法如下解决：publicstaticbooleanisPalindrome(Strings){if(s.length()<=1)//Basecasereturntrue;elseif(s.charAt(0)!=s.charAt(s.length()-1))//Basecasereturnfalse;elsereturnisPalindrome(s.substring(1,s.length()-1));}32递归的辅助方法因为前面递归的isPalindrome方法要为每次递归调用创建一个新字符串，因此它不够高效。为避免创建新字符串，可以使用辅助方法：publicstaticbooleanisPalindrome(Strings){returnisPalindrome(s,0,s.length()-1);}publicstaticbooleanisPalindrome(Strings,intlow,inthigh){if(high<=low)//Basecasereturntrue;elseif(s.charAt(low)!=s.charAt(high))//Basecasereturnfalse;elsereturnisPalindrome(s,low+1,high-1);}33递归地选择排序RecursiveSelectionSort找出列表中的最小数，然后将它与第一个数进行交换。忽略最后一个数，对剩下的较小一些的列表进行递归排序。34二分查找RecursiveBinarySort情况1：如果关键字比中间元素小，那么只需在前一半的数组元素中进行递归查找。情况2：如果关键字和中间元素相等，则匹配成功，查找结束。情况3：如果关键字比中间元素大，那么只需在后一半的数组元素中进行递归查找。35递归地实现/**Usebinarysearchtofindthekeyinthelist*/publicstaticintrecursiveBinarySearch(int[]list,intkey){intlow=0;inthigh=list.length-1;returnrecursiveBinarySearch(list,key,low,high);}

/**Usebinarysearchtofindthekeyinthelistbetweenlist[low]list[high]*/publicstaticintrecursiveBinarySearch(int[]list,intkey,intlow,inthigh){if(low>high)//Thelisthasbeenexhaustedwithoutamatchreturn-low-1;

intmid=(low+high)/2;if(key<list[mid])returnrecursiveBinarySearch(list,key,low,mid-1);elseif(key==list[mid])returnmid;elsereturnrecursiveBinarySearch(list,key,mid+1,high);}36目录大小前面的例子可以不用递归很容易地解决。对于本节给出的这个问题，要是不使用递归是很难解决的。这里的问题是求出一个目录的大小。一个目录的大小是指该目录下所有文件大小之和。目录d可能会包含子目录。假设一个目录包含文件f1、f2、…、fn以及子目录d1、d2、…、dn，如图所示：37目录大小目录的大小可以如下递归定义：DirectorySize38汉诺塔n个盘子被标记为1、2、3、...、n，而三个塔标记为A、B和C。任何时候盘子都不能放在比它小的盘子的上方。初始状态时，所有的盘子都放在塔A上。每次只能移动一个盘子，并且这个盘子必须在塔顶位置。39汉诺塔（续）40汉诺塔的解决方法汉诺塔问题可以分解为三个子问题。41汉诺塔的解决方案借助塔B将前n-1个盘子从A移到C。将盘子n从A移到B。借助塔A将n-1个盘子从C移到B。TowersOfHanoi42练习题20.3最大公约数gcd(2,3)=1gcd(2,10)=2gcd(25,35)=5gcd(205,301)=5gcd(m,n)方法1：

穷举，从(n,m)中的较小值开始遍历到1，检查数值是否为m和n的公约数，如果是，这个数值就是m和n的最大公约数。方法2：Euclid算法方法3:递归方法43方法2：Euclid算法//Getabsolutevalueofmandn;t1=Math.abs(m);t2=Math.abs(n);//ristheremaind