Java語言程序設(shè)計-基礎(chǔ)篇-中文ppt-第二十章

1第20章遞歸2動因假設(shè)希望找出某目錄下所有包含某個特定單詞的文件，該如何解決這個問題呢？有幾種方法可以解決這個問題。一個直觀且有效的解決方法是使用遞歸在子目錄下遞歸地搜索所有文件。3動因經(jīng)典的八皇后難題就是將八個皇后放在棋盤上，而沒有任何兩個皇后可以互相攻擊（既不會出現(xiàn)兩個皇后在同一行、同一列或者同一條對角線上的情況），如圖所示。該如何編寫程序解決這個問題呢？一個好的辦法就是使用遞歸。4學(xué)習(xí)目標(biāo)了解什么是遞歸方法以及使用遞歸方法的好處（第20.1節(jié)）。決定遞歸方法的基礎(chǔ)情況（第20.2-20.5節(jié)）。理解在調(diào)用棧中如何處理遞歸方法的調(diào)用（第20.2-20.3節(jié)）。使用遞歸解決問題（第20.2-20.5節(jié)）。使用一個重載的輔助方法派生一個遞歸方法（第20.5節(jié)）。使用遞歸獲取目錄大?。ǖ?0.6節(jié)）。使用遞歸解決漢諾塔問題（第20.7節(jié)）。使用遞歸繪制分形（第20.8節(jié)）。理解遞歸和迭代之間的聯(lián)系和區(qū)分（第20.9節(jié)）。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跟蹤遞歸階乘動畫執(zhí)行factorial(4)15跟蹤遞歸階乘動畫執(zhí)行factorial(3)16跟蹤遞歸階乘動畫執(zhí)行factorial(2)17跟蹤遞歸階乘動畫執(zhí)行factorial(1)18跟蹤遞歸階乘動畫執(zhí)行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斐波那契數(shù)斐波那契

數(shù)列:01123581321345589…

下標(biāo):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斐波那契數(shù)（續(xù)）29遞歸的特點所有的遞歸方法都具有以下特點：使用一個或多個基礎(chǔ)情況（最簡單的情況）來停止遞歸。每次遞歸調(diào)用都會簡化原始問題，讓它不斷地接近基礎(chǔ)情況，直到它變成這種基礎(chǔ)情況為止。通常，要使用遞歸解決問題，就要將這個問題分解為子問題。如果子問題像原始問題一樣，那你可以遞歸地應(yīng)用同樣的方法去解決子問題。本質(zhì)上講，每個子問題幾乎與原始問題是一樣的，只是規(guī)模小一些。30使用遞歸解決問題考慮打印一條消息n次的簡單問題?？梢詫⑦@個問題分解為兩個子問題：一個是打印消息一次，另一個是打印消息n-1次。第二個問題與原始問題是一樣的，只是規(guī)模小一些。這個問題的基礎(chǔ)情況是n==0?？梢允褂眠f歸來解決這個問題，如下所示：publicstaticvoidnPrintln(Stringmessage,inttimes){if(times>=1){System.out.println(message);nPrintln(message,times-1);}//Thebasecaseistimes==0}31以遞歸的思路進(jìn)行思考如果以遞歸的思路進(jìn)行思考，本書前面章節(jié)中的許多問題都可以用遞歸來解決。例如：對程序清單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方法要為每次遞歸調(diào)用創(chuàng)建一個新字符串，因此它不夠高效。為避免創(chuàng)建新字符串，可以使用輔助方法：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找出列表中的最小數(shù)，然后將它與第一個數(shù)進(jìn)行交換。忽略最后一個數(shù)，對剩下的較小一些的列表進(jìn)行遞歸排序。34二分查找RecursiveBinarySort情況1：如果關(guān)鍵字比中間元素小，那么只需在前一半的數(shù)組元素中進(jìn)行遞歸查找。情況2：如果關(guān)鍵字和中間元素相等，則匹配成功，查找結(jié)束。情況3：如果關(guān)鍵字比中間元素大，那么只需在后一半的數(shù)組元素中進(jìn)行遞歸查找。35遞歸地實現(xiàn)/**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目錄大小前面的例子可以不用遞歸很容易地解決。對于本節(jié)給出的這個問題，要是不使用遞歸是很難解決的。這里的問題是求出一個目錄的大小。一個目錄的大小是指該目錄下所有文件大小之和。目錄d可能會包含子目錄。假設(shè)一個目錄包含文件f1、f2、…、fn以及子目錄d1、d2、…、dn，如圖所示：37目錄大小目錄的大小可以如下遞歸定義：DirectorySize38漢諾塔n個盤子被標(biāo)記為1、2、3、...、n，而三個塔標(biāo)記為A、B和C。任何時候盤子都不能放在比它小的盤子的上方。初始狀態(tài)時，所有的盤子都放在塔A上。每次只能移動一個盤子，并且這個盤子必須在塔頂位置。39漢諾塔（續(xù)）40漢諾塔的解決方法漢諾塔問題可以分解為三個子問題。41漢諾塔的解決方案借助塔B將前n-1個盤子從A移到C。將盤子n從A移到B。借助塔A將n-1個盤子從C移到B。TowersOfHanoi42練習(xí)題20.3最大公約數(shù)gcd(2,3)=1gcd(2,10)=2gcd(25,35)=5gcd(205,301)=5gcd(m,n)方法1：

窮舉，從(n,m)中的較小值開始遍歷到1，檢查數(shù)值是否為m和n的公約數(shù)，如果是，這個數(shù)值就是m和n的最大公約數(shù)。方法2：Euclid算法方法3:遞歸方法43方法2：Euclid算法//Getabsolutevalueofmandn;t1=Math.abs(m);t2=Math.abs(n);//ristheremaind