如何用Java递归算法改写九连环公式为长尾词求解法？

本文共计1280个文字，预计阅读时间需要6分钟。

在先前有过一些关于递归的东西的敲打和链接开启，后来想到小时候自己玩的一个玩具——九连环。小时候一边玩一边用笔记下来解开这个公式的经过，那是十多年前的事情了。

在之前有写到过一点点有关递归的东西点击打开链接，然后想到小时候自己玩的一个玩具——九连环。小时候自己曾经一边玩一边用笔记下来解开这个东西的公式，那是十几年前的事情了。前两天突然想起来，九连环的基本操作就是一个递归，一个感觉起来非常标准的递归过程。

九连环的玩法规则用一句话来概括就是：如果你想要卸掉某一环或者装上某一环，只需要保留这一环前面一环，再之前所有的环都卸掉。（例如你想要卸掉或者装上第9环，那么保留第8环，第8环之前的所有的环都卸掉）其中第一环可以直接卸掉。（其实第一第二这两环可以一起装上一起卸掉，我们在逻辑上只是规定第一环可以自由移动）

那么按照递归的思想来实现这个问题，还是比较简单的。与之前提到的不同的是：这次对于某一环的操作不是一种，牵扯到装上和卸掉两种基本操作，所以针对九连环要设置一个标记状态——state：九连环在上，state=1；九连环在下，state=0 。这个在Node类中实现。（如同c++中的struct）

其中num属性表示环号，state表示环的状态。

第二个需要准备的就是利用ArrayList实现的一个栈，来将所有state=1的环压入栈中。九连环规则中要求：要想对某一环进行操作，要保证这一环的前一环state=1 且在栈顶。