1.3 遞歸算法

小游戲：漢諾塔或梵塔問(wèn)題。

有3個(gè)基座A、B、C，開始時(shí)A基座上有n個(gè)大小不同的盤子，大盤子在下、小盤子在上疊在一起，問(wèn)：要把A基座上的n個(gè)盤子移到C基座上，每次只能移動(dòng)一個(gè)，并且移動(dòng)過(guò)程中始終保持大盤子在下、小盤子在上，能做到嗎？如能做到，要移動(dòng)幾次？

（1）設(shè)n個(gè)大小不同的盤子按規(guī)則移動(dòng)，需要移動(dòng)f （n）次，請(qǐng)動(dòng)手做一做，算出以下答案。

f（1）=　　 f（2）=　　　f（3）=　　　f（4）=

（2）試猜想f （n）=2f （n-1）+1是否成立？f（n）=2n?1是否成立？

證明：

所以，{f（n）+1}構(gòu)成一個(gè)等比數(shù)列，首項(xiàng)為 f（1）+1=2，公比為2，則

f（n）+1=2×2n?1=2n，即 f（n）=2n?1。

（3）解決這個(gè)問(wèn)題能否由計(jì)算機(jī)實(shí)現(xiàn)？過(guò)程怎樣？——可用遞歸算法編程實(shí)現(xiàn)。