九连环的递归算法（C和C++）

一、九连环简介

九连环游戏是中国人自己发明的，它的历史非常悠久，据说是起源于战国时期。九连环主要是由一个框架和九个圆环组成：每个圆环上连有一个直杆，而这个直杆则在后面一个圆环内穿过，九个直杆的另一端用一块木板或圆环相对固定。

二、九连环的规律

通过玩九连环你就会发现存在这样一个规律：

（1）第 1环可以自由上下
（2）而上/下第 n环时（n>1),则必须满足：
 （a）第 n-1个环在架上
 （b）前 n-2个环全部在架下

三、拆解/安装的过程

正确的拆解是先以第 9环为目标，先拆下它，简化为拆一个 8连环。接着再也第 8 环为目标，拆下它，简化为拆一个 7连环。以此类推，直至全部拆解。

其实安装和拆解是一个道理，因为他们均是使用上面说的规律来完成的。

正确是安装也是先以第 9环为目标，先装上它，简化为装一个 8连环。接着再也第 8 环为目标，装