Ackermann函数和递归

Question

我试图用Java编写递归的Ackermann函数.但我觉得我在某个地方出错了!任何人都可以看看,检查并指出我正确的方向纠正我的代码？谢谢!

我对代码的问题是,在我写完之后,我想,如果n == 0和m == 0,那么这个区域没有？这会属于if(m == 0)还是需要它自己的if语句？

我的以下解决方案是否正确 如果我以不同的顺序给它相同的数字,它给出了不同的结果,我不确定这是否是这种情况.

public static int ackermann(int m, int n) {

        if (m == 0) {

            return n + 1;

        } else if ((m > 0) && (n == 0)) {

            return ackermann(m-1, n);

        } else if ((m > 0) && (n > 0)) {

            return ackermann(m-1, ackermann(m,n-1));

        } else {

            return 0;

        }

    }

我想了一下,我想我错了.如果你无法弄清楚我做了什么我给了每个if语句相反,因为我认为如果以不同的方式给出m和n值,则下面的代码将起作用.它显然没有,但有人可以尝试解释我哪里出错了？

public static int ackermann(int m, int n) {

        if (m == 0) {

            return n + 1;

        } else if (n == 0) {

            return m + 1;

        } else if ((m > 0) && (n == 0)) {

            return ackermann(m-1, n);

        } else if ((n > 0) && (m == 0)) {

            return ackermann(n-1, m);

        } else if ((m > 0) && (n > 0)) {

            return ackermann(m-1, ackermann(m,n-1));

        } else if ((n > 0) && (m > 0)) {

            return ackermann(n-1, ackermann(n, m-1));

        } else {

            return 0;

        }

    }

Answer 1

这部分是错的:

    } else if ((m > 0) && (n == 0)) {
        return ackermann(m-1, n);

应该是A(m - 1,1)

Answer 2

我认为你的第一个版本几乎是正确的.我稍微修改一下:

public static int ackermann(int m, int n) {
    if (m < 0 || n < 0) {
        throw new IllegalArgumentException("Non-negative args only!");
    }

    if (m == 0) {
        return n + 1;
    } else if (n == 0) {
        return ackermann(m-1, 1); // Corrected!
    } else {
        // perforce (m > 0) && (n > 0)
        return ackermann(m-1, ackermann(m,n-1));
    }
}

该m == 0 && n == 0案件应包括在m == 0案件中.

编辑:请注意,Ackermann函数仅针对非负参数定义.特别是ackermann(0, -1)应该抛出异常.因此,您不能只将您的最后一个else子句转换为throw.