(14)-4.6 遞歸方法程序設(shè)計(jì)

遞歸方法

方法定義學(xué)習(xí)目標(biāo)1.理解遞歸方法的原理。2.學(xué)會(huì)使用遞歸求解問(wèn)題。知識(shí)圖譜遞歸從前有座山，山里有座廟，廟里有個(gè)老和尚，正在給小和尚講故事呢！故事是什么呢？從前有座山，山里有座廟，廟里有個(gè)老和尚，正在給小和尚講故事呢！故事是什么呢？從前有座山……遞歸方法遞歸方法就是直接或間接調(diào)用自身的方法。其中方法直接調(diào)用自己稱為直接遞歸；方法A調(diào)用方法B,方法B又調(diào)用方法A稱為間接遞歸。遞歸思想把規(guī)模大、較難解決的問(wèn)題變成規(guī)模較小、容易解決的同一類問(wèn)題。規(guī)模較小的問(wèn)題又可以變成規(guī)模更小的問(wèn)題，依此類推，當(dāng)問(wèn)題小到一定的程度時(shí)，便可以直接得到它的解，從而得到原來(lái)整個(gè)大問(wèn)題的解。遞歸方法充分必要條件待解決的問(wèn)題可以轉(zhuǎn)化為一個(gè)新的、更小的問(wèn)題，而這個(gè)新問(wèn)題的解決方法與原來(lái)問(wèn)題的解決方法相同，只是所處理的對(duì)象有規(guī)律地遞增或遞減。能夠應(yīng)用上面這個(gè)轉(zhuǎn)化過(guò)程使問(wèn)題得到解決。必須要有一個(gè)明確的遞歸結(jié)束條件。注意：(1)解決問(wèn)題所調(diào)用的方法相同，只是每次傳遞的參數(shù)不同，有規(guī)律地遞增或遞減，如果沒(méi)有規(guī)律也就不適用于用遞歸求解。(2)一定要能夠在適當(dāng)?shù)牡胤浇Y(jié)束遞歸調(diào)用。否則，可能會(huì)導(dǎo)致系統(tǒng)崩潰。必須具備以下三個(gè)充分必要條件：斐波那契兔子問(wèn)題有一對(duì)小兔子，從出生后第3個(gè)月起每個(gè)月都生一對(duì)小兔子，小兔子長(zhǎng)到第三個(gè)月后每個(gè)月又生一對(duì)兔子，假如兔子都不死，問(wèn)前24個(gè)月每個(gè)月的兔子總對(duì)數(shù)是多少？------取自中世紀(jì)意大利數(shù)學(xué)家斐波那契的《算盤書》(LeonardoPisano,Fibonacci,LeonardoBigollo,1175年-1250年)斐波那契兔子問(wèn)題分析：列表分析前6個(gè)月的兔子數(shù)。發(fā)現(xiàn)時(shí)間越長(zhǎng)，用列表法解決會(huì)很困難，這里是否有規(guī)律？能方便的解決？斐波那契兔子問(wèn)題仔細(xì)觀察表中的數(shù)據(jù)，發(fā)現(xiàn)第n個(gè)月的兔子總數(shù)等于第n-1個(gè)月兔子與第n-2個(gè)月兔子數(shù)之和。因此我們可以得到遞歸式：

f(n)=f(n-1)+f(n-2)(n>=3)根據(jù)遞歸需滿足的條件，我們還要找出遞歸的結(jié)束條件，即：

f(1)=f(2)=1。斐波那契兔子問(wèn)題斐波那契兔子問(wèn)題運(yùn)行結(jié)果：集合劃分問(wèn)題描述：設(shè)S是一個(gè)具有n個(gè)元素的集合，S={a1,a2,…,an}，現(xiàn)將S劃分成k個(gè)滿足下列條件的子集合s1,s2,…,sk，滿足：

（1）si≠ф

（2）si∩sj=ф（1≤i,j≤k且i≠j）

（3）s1∪s2∪s3∪…∪sk=S

則s1,s2,…,sk是集合S的一個(gè)劃分。它相當(dāng)于把S集合中的n個(gè)元素a1,a2,…,an放入k個(gè)（0<k≤n）無(wú)標(biāo)號(hào)的盒子中，使得沒(méi)有一個(gè)盒子為空。編寫程序請(qǐng)確定n個(gè)元素a1,a2,…,an放入k個(gè)無(wú)標(biāo)號(hào)盒子中去的劃分?jǐn)?shù)s(n,k)。

集合劃分分析：先舉個(gè)例子，假設(shè)S={1,2,3,4},k=3,可得出S有6種不同的劃分方案，即劃分?jǐn)?shù)s(4，3)=6。方案如下：{1,2}∪{3}∪{4},{1,3}∪{2}∪{4},{1}∪{2,3}∪{4}{1,4}∪{2}∪{3},{1}∪{2,4}∪{3},{1}∪{2}∪{3,4},考慮一般情況，對(duì)于任意的含有n個(gè)元素a1,a2,...,an的集合S，放入k個(gè)無(wú)標(biāo)號(hào)的盒子中去，劃分?jǐn)?shù)為s(n,k)，這很難憑直覺(jué)和經(jīng)驗(yàn)計(jì)算劃分?jǐn)?shù)并枚舉劃分所有方案，必須歸納出問(wèn)題的本質(zhì)。集合劃分綜上所述，應(yīng)用加法原理，得出n個(gè)元素的集合{a1,a2,...,an}，劃分為k個(gè)子集的劃分?jǐn)?shù)為以下遞歸公式：s(n,k)=s(n-1,k-1)+k*s(n-1,k)(n>k,k>0)。下面，我們要確定s(n,k)的邊界條件，首先不能把n個(gè)元素不放進(jìn)任何一個(gè)子集中去，即k=0時(shí)，s(n,k)=0；也不可能在不允許空盒的情況下把n個(gè)元素放進(jìn)多于n的k個(gè)集合中去，即k>n時(shí)，s(n,k)=0;再者，把n個(gè)元素放進(jìn)一個(gè)集合或把n個(gè)元素放進(jìn)n個(gè)集合，方案數(shù)都是1，即k=1或k=n時(shí)，s(n,k)=1。集合劃分因此，得到劃分?jǐn)?shù)s(n,k)的遞歸關(guān)系為：s(n,k)=s(n-1,

k-1)

+

k*s(n-1,k)(n>k,k>0)s(n,k)=0(n<k或k=0)s(n,k)=1(k=1或k=n)集合劃分集合劃分運(yùn)行結(jié)果：總結(jié)——本節(jié)內(nèi)容遞歸算法的實(shí)質(zhì)是把問(wèn)題轉(zhuǎn)化為規(guī)?？s小了的同類子問(wèn)題。然后遞歸調(diào)用方法（函數(shù)）來(lái)表示子問(wèn)題的解。遞歸方法解決問(wèn)題的特點(diǎn)：遞歸就是在方法里調(diào)用自身。必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。遞歸算法求解問(wèn)題通常很簡(jiǎn)潔，但遞歸方法的運(yùn)行效率較低。所以一般不提倡使用遞歸方法來(lái)設(shè)計(jì)程序?？偨Y(jié)——作業(yè)編寫程序：使用遞歸的方法計(jì)算輸出1-20的階乘值。

真正的科學(xué)家應(yīng)當(dāng)是個(gè)幻想家；誰(shuí)