求解最小步数的递推关系

题目描述：
糖和抖m在玩个游戏，规定谁输了就要请谁吃顿大餐：抖m给糖a b c三个驻，并在a柱上放置了数量为n的圆盘，圆盘的大小从上到下依次增大，现在要做的事就是把a柱的圆盘全部移到c柱，移动的过程中保持小盘在上，大盘在下，且限定圆盘只能够移动到相邻的柱子，即a柱子上的圆盘只能够移动到b，b柱子上的圆盘只能够移动到a或者c，c同理。现在请你设计一个程序，计算所需移动的最小步数，帮助糖赢得大餐！

对于本题，本质上和汉诺塔十分相似。我主要想说说怎么去求解其递推关系。

汉诺塔问题

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

我们先来对汉诺塔的步数进行一下递推。
对于n个盘子，我们可以把它分成 $n-1$ 个盘子和最后一个大盘子。设 $F(n)$ 为移动所需步数,那么对于 $n$ 个盘子来说所做的事情就是将 $n-1$ 个盘子借助C柱移动到B柱上,这一过程移动的步数为 $F(n-1)$ ,下一步我们将大盘子移动到C柱上，此时需要一步，最后，我们再将 $n-1$ 个盘子借助A柱移动到C柱上，此时需要的步数仍为 $F(n-1)$ 。综合以上分析， $F(n)=2F(n-1)+1$ 。对两边同时加上1可以凑成一个等比数列，然后就可以求出其通项公式。

对于本题，我们依然可以按照刚才的思路来进行递推。
同样的，对于n个盘子，我们可以把它分成 $n-1$ 个盘子和最后一个大盘子。
同样设 $F(n)$ 为移动所需步数。

将 $n-1$ 个盘子借助B柱移动到C柱上,这一过程移动的步数极为 $F(n-1)$
将大盘子由A柱移动到B柱上，此时需要一步
将 $n-1$ 个盘子借助B柱移动到A柱上,这一过程移动的步数同样为 $F(n-1)$
将大盘子由B柱移动到C柱上，此时需要一步
将 $n-1$ 个盘子借助B柱子移动到C柱上，此时需要的步数仍为 $F(n-1)$ 。
综合以上分析， $F(n)=3F(n-1)+2$ 。同样，对两边同时加上1可以凑成一个等比数列，最后求出其通项公式即为 $3^n-1$ 。