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

動(dòng)畫factorial(0)=1;factorial(n)=n*factorial(n-1);8計(jì)算階乘factorial(3)=3*factorial(2)=3*(2*factorial(1))

動(dòng)畫factorial(0)=1;factorial(n)=n*factorial(n-1);9計(jì)算階乘factorial(3)=3*factorial(2)=3*(2*factorial(1))=3*(2*(1*factorial(0)))

動(dòng)畫factorial(0)=1;factorial(n)=n*factorial(n-1);10計(jì)算階乘factorial(3)=3*factorial(2)=3*(2*factorial(1))=3*(2*(1*factorial(0)))=3*(2*(1*1)))

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