经典的就是 Hanoi 了。
public class TowersOfHanoi
{
public static void moves(int n, boolean left)
{
if (n == 0) return ;
moves(n-1, !left);
if(left) StdOut.println(n + " left");
else StdOut.println(n + " right");
moves(n-1, !left);
}
public static void main(String[] args)
{
int n = Integer.parseInt(args[0]);
moves(n, true);
}
}
就以 Hanoi 塔问题来说 (假设初始圆盘都在中间，需要把所有圆盘移到左边)
圆盘数量为 0 时，那么什么都不用动，问题解决. 假设圆盘数量为 n-1 时问题解决了，那么圆盘数量为 n 时：可以把上面 n-1 个圆盘从中间移动到右边，然后把第 n 个圆盘从中间移动到左边，然后再把那 n-1 个圆盘从右边移动到左边，问题也解决了。
是不是和数学归纳法的证明过程一个模子出来的？写出了递归程序，也可以依样画葫芦用归纳法 (不过一般不是数学归纳法，而是更一般的良序归纳法) 来证明它写对了。很多 LISP 和 ML 的理论书里对递归有更深刻的讨论，有精力的话推荐看看...
