1.3 递归算法

小游戏：汉诺塔或梵塔问题。

有3个基座A、B、C，开始时A基座上有n个大小不同的盘子，大盘子在下、小盘子在上叠在一起，问：要把A基座上的n个盘子移到C基座上，每次只能移动一个，并且移动过程中始终保持大盘子在下、小盘子在上，能做到吗？如能做到，要移动几次？

（1）设n个大小不同的盘子按规则移动，需要移动f （n）次，请动手做一做，算出以下答案。

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

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

证明：

所以，{f（n）+1}构成一个等比数列，首项为 f（1）+1=2，公比为2，则

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

（3）解决这个问题能否由计算机实现？过程怎样？——可用递归算法编程实现。