Функция Аккермана и рекурсия

Question

Я пытался написать рекурсивную функцию Аккермана на Java. Но я думаю, что я где-то ошибся! Может ли кто-нибудь взглянуть, проверить и, возможно, указать мне правильное направление исправления моего кода? Спасибо!

Проблема с кодом заключается в том, что после того, как я написал его, я подумал, что если 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

Я думаю, что ваша первая версия почти верна.Я бы немного его изменил:

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.

Answer 2

Эта часть неверна:

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

Это должно быть A (м - 1, 1)

Answer 3

Интересно, что все ответы на ваш вопрос указывают на вашу ошибку в первой версии, но ничего не говорят о большой ошибке во второй версии

 else if (n == 0) {
        return m + 1;
    } 

Что для положительных целых чисел эквивалентно по условию с

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

Таким образом, ваша функция вернет m + 1, но не ackermann (m-1, 1), который должен для второго случая ((m> 0) && (n == 0)).

Answer 4

Правило 'if m = 0' применяется для всех значений n, поэтому A (0, 0) равно 1.

Предложение 'else' может использоваться только в том случае, если m и n оба являются отрицательнымипри входе в функцию, которая может быть диагностирована как исключение.Действительно, если m или n отрицательно, вы должны диагностировать ошибку.В качестве альтернативы, поскольку A (m, n) никогда не возвращает ноль в противном случае, 0 может быть принято за сигнал об ошибке.

Обратите внимание, что глубина стека, необходимая для оценки A (m, n), совпадает с ответом- и A (m, n) становится очень большим очень быстро.Не пытайтесь оценить A (4, 4);вашему компьютеру не хватает памяти.

Answer 5

Первый фрагмент в порядке, за исключением того, что он возвращает ackermann(m-1, n) вместо ackermann(m-1, 1) во втором случае.Случай по умолчанию, который никогда не должен происходить, должен выдавать IllegalStateException в случае, если это действительно происходит.