最近在重温数据结构和算法分析。刚好手头有个九连环，就想着用递归写写个九连环的解法。九连环解法的基本原则：
第一个环在任何时候都是可以自由上下的如果希望第 n 个环能自由上下，那么 – 第 n-1 个环必须在杆上 – 前面第 n-2 个环全部不在杆上这三个简单规则就构成了递归解法的基础。
%matplotlib qtimport matplotlib.pyplot as pltfrom matplotlib.patches import Circle# 模拟九连环，1表示在杆上，0表示不在ring = [0,1,1,1,1,1,1,1,1,1]UP = 1DOWN = 0steps = 0 fig = plt.figure(figsize=(12,3))def visual(steps,index,action):if action == UP:title = 'setp-%s: %s ring UP'%(steps,index)else:title = 'setp-%s: %s ring DOWN'%(steps,index)plt.cla()ax = fig.add_subplot(111)plt.axis('off')plt.plot([1,35],[7,7],'k-',linewidth=2)for i in range(1,10):y = ring[i]*3+4color = 'red' if ring[i] else 'blue'cir = Circle(xy = (3.5*i, y), radius=1, alpha=0.5,facecolor= color)ax.add_patch(cir)plt.title(title)plt.axis([0,40,0,10])plt.pause(0.5)def ring_updown(index,action):# 如果是第一个环，那么可以自由拆卸global stepsif index == 1:steps += 1ring[index] = actionvisual(steps,index,action)return None# 如果第 n-1 个环不在杆上，需要先装上if ring[index-1] == 0: # n-1 not on the ringring_updown(index-1,UP)# n-2 个环需要全部不在杆上，如果有环在杆上，需要先卸下来for i in range(index-2,0,-1):if ring[i] == 1: # n-2,n-3,... no the ringring_updown(i,DOWN)steps += 1ring[index] = actionvisual(steps,index,action)return Nonefor i in range(9,0,-1):ring_updown(i,DOWN)上面的代码，除去图示的部分，只有10行有效代码。 
一共执行了341步骤。