一个关于递归算法的问题 想了很久..

码海无涯

一个国王因为听信谗言将一个无辜的数学家关进了监狱。虽然事后发现确属冤枉，但碍于面子，国王不肯认错。为了挽回，于是国王决定用Bytish锁链将其锁在墙上。这种锁链由n（10≤n≤1000）个固定在墙上的铁环和铁棒组成。由于环不是都套在棒上，要想把整副锁链取下是十分困难的。数学家必须自己通过不断取下和套上铁环最终将所有铁环都取下才能获得自由。取下或套上铁环的规则是：

Ø  铁环从1、2、……、n依次编号。

Ø  一次只能把一个环取下或套上。

Ø  编号为1的环无论何时都能取下或套上。

Ø  如果编号为1、……、k-1（1≤k≤n）的环已经从棒上取下，并且k环套在棒上，则可以取下或套上编号为k+1环。

程序要求按照从n、n-1、n-2、……、1的顺序，将移除掉n号环的全部过程作为一个段落输出，然后将移除n-1号环的全部过程也作为一个段落输出，其余依此类推。

题目就是这样。

应该是用递归的方法

    解开有n个环的锁链的过程：

当n=1时，解1

当n=2时，解2 解1

当n=3时，解1 解3 套1 解2 解1

当n=4时，解2 解1 解4 套1 套2 解1 解3 套1 解2 解1

....

题目要求分别输出移除第n号环的过程...移除第n号环的过程是先移除前n-2个环，然后移除第n号环。这个用递归的方法我怎么都想不明白，如果要让移除每个环的过程都相似的话，在移除了第n号环之后是不是还应该把前n-2个环再套上，让锁链恢复到由n-1个环构成的状态，这样才能递归？还有怎么输出结果呢，n的取值很大，最后输出的结果感觉很复杂..

求助！最好能把程序大致编出来让我看一看..指出一下我思路的问题..

码海无涯

没有人来帮帮我吗