遞歸——自己定義自己
GNU是什么的縮寫汁尺？
“GNU is Not Unix”
這里面的GNU又是什么的縮寫？
“GNU is Not Unix”
遞歸是一種奇妙的思考方法商虐，它“使用自己來(lái)定義自己”何荚。
漢諾塔
- 思考：有三根細(xì)圓柱(A,B,C)，A柱上套著6個(gè)圓盤剃毒。這些圓盤大小各異，按從大到小的順序自下而上擺放搂赋，現(xiàn)在要把A柱上的6個(gè)圓盤全部移動(dòng)到B上赘阀，并且在移動(dòng)的時(shí)候遵守下述規(guī)則：
- 一次只能移動(dòng)柱子最上端的一個(gè)圓盤
- 小圓盤上不能放大圓盤
將1個(gè)圓盤從一根柱子移動(dòng)到另一根柱子，算移動(dòng)1次脑奠，那么將6個(gè)圓盤全部從A移動(dòng)到B最少需要移動(dòng)幾次呢基公？
漢諾塔
解題思路：
- 先嘗試解決3個(gè)圓盤的問(wèn)題，需要7次
- 仔細(xì)思考宋欺，無(wú)論如何轰豆，想移走k層的圓盤，都必須把k-1層的圓盤全部移走
- 因?yàn)锳BC三個(gè)柱子在不同的場(chǎng)景下會(huì)發(fā)揮不同的職能齿诞，我們假設(shè)x,y,z三個(gè)柱子酸休，x為起點(diǎn)，y為目標(biāo)祷杈，z為中轉(zhuǎn)
- 解出n層塔的步驟斑司，即是利用z將n個(gè)圓盤從x移動(dòng)到y(tǒng)
- 當(dāng)n=0時(shí)，不用做任何動(dòng)作
- 當(dāng)n>0時(shí)但汞，
- 首先宿刮，將n-1個(gè)圓盤從x，經(jīng)由y中轉(zhuǎn)特占，移動(dòng)到z(解出n-1層)
- 然后糙置，將1個(gè)圓盤從x移動(dòng)到y(tǒng)
- 最后云茸，將n-1個(gè)圓盤從z柱是目，經(jīng)過(guò)x中轉(zhuǎn)，移動(dòng)到y(tǒng)(解出n-1層)
- 從以上步驟得出結(jié)論标捺，為了解出n層的漢諾塔懊纳，我們要使用n-1層的解法揉抵，我們將解出“n層漢諾塔”所需的最少移動(dòng)步驟表示為：
H(n)，例如嗤疯，移動(dòng)0個(gè)圓盤的次數(shù)為0冤今，那么：
H(0)=0，H(1)=1
H(n)=H(n-1)+1+H(n-1)
n的解法數(shù)=n-1的解法數(shù)+移動(dòng)最大的圓盤的次數(shù)+n-1的解法數(shù)
- 我們將這種H(n)和H(n-1)的關(guān)系式稱為遞推公式(recursion relation, recurrence)
H(0)=0
H(1)=0+1+0=1
H(2)=1+1+1=3
H(3)=3+1+3=7
H(4)=7+1+7=15
H(5)=15+1+15=31
H(6)=31+1+31=63
H(n)=2^n-1推導(dǎo)式可以被數(shù)學(xué)歸納法證明
編程部分(略)
- 關(guān)鍵步驟
- 找出遞歸結(jié)構(gòu)
- 建立地推公式
再談階乘
- n! = n x (n-1)! ←發(fā)現(xiàn)遞歸結(jié)構(gòu)
- 0!=1的原因茂缚，就是為了完成遞歸定義
- 階乘的遞歸定義和數(shù)學(xué)歸納法比較類似戏罢，n=0時(shí)相當(dāng)于數(shù)學(xué)歸納法的步驟1(基底)，n>=1時(shí)相當(dāng)于步驟2(歸納)脚囊。若用多米諾骨牌來(lái)打比方龟糕，“正確地定義0!”就相當(dāng)于“確保推倒第1張多米諾骨牌”。
遞歸和歸納
- 遞歸和歸納本子上是相同的悔耘，都是將復(fù)雜問(wèn)題簡(jiǎn)化讲岁。
- 遞歸和歸納，只是方向上不同衬以』貉蓿“從一般性前提推出個(gè)別性結(jié)論”是遞歸，“從個(gè)別性前提推出一般性結(jié)論”是歸納看峻。
