数学 递归程序有点不好写阿?

匿名 · 2012年10月30日 · 最后由 discover 回复于 2013年10月23日 · 8718 次阅读

经典的就是 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);
    }
}

看过一个国外大学公开课,那个老头说什么抓住一个固定的规律,然后怎么怎么的,反正不难的

写递归程序只是方法,不是目的。

如果学过数学归纳法, 那么写递归程序就毫无鸭梨...

匿名 #4 · 2012年10月30日

#3 楼 @luikore 你能自己写出这个 hanoi tower 算法么?

就以 Hanoi 塔问题来说 (假设初始圆盘都在中间, 需要把所有圆盘移到左边)

圆盘数量为 0 时, 那么什么都不用动, 问题解决. 假设圆盘数量为 n-1 时问题解决了, 那么圆盘数量为 n 时: 可以把上面 n-1 个圆盘从中间移动到右边, 然后把第 n 个圆盘从中间移动到左边, 然后再把那 n-1 个圆盘从右边移动到左边, 问题也解决了.

是不是和数学归纳法的证明过程一个模子出来的? 写出了递归程序, 也可以依样画葫芦用归纳法 (不过一般不是数学归纳法, 而是更一般的良序归纳法) 来证明它写对了. 很多 LISP 和 ML 的理论书里对递归有更深刻的讨论, 有精力的话推荐看看...

匿名 #6 · 2012年10月31日

#5 楼 @luikore 我对 recursion 也不是很懂,推荐几本书把

推荐书...那就 SICP 吧

学函数式编程就能学会了

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册