Ошибка с рекурсией, которую я не могу понять. JAVA

Содержание

Вопрос или проблема
Ответ или решение
Проблема
Код и его анализ
Ошибки в коде
Исправленный код
Объяснение исправлений
Заключение

Вопрос или проблема

В Java я работаю с рекурсией и уверен, что у меня проблема с базовым случаем. Я использую Eclipse, и ошибка, которую я получаю, заполняет консоль, так что я не могу увидеть соответствующую информацию.

Вот мой код:

public boolean smallestDifference(Node node, int subSum1, int subSum2) { //
    //int difference;
    //int test;
    node = headNode;
    boolean addSub1 = false;
    boolean addSub2 = false;

    if (node == null) {
        System.out.println("Наименьшая разница:");
        System.out.println(subSum1 - subSum2);

    }

    if (subSum1 <= subSum2) {
        return smallestDifference(node.next, subSum1 + node.value, subSum2);
    } else {
        return smallestDifference(node.next, subSum1, subSum2 + node.value);
    }
}

Вызов в основном методе:

    linkedList.smallestDifference(linkedList.headNode, 0,0);

Ваш код рекурсии не содержит критерия завершения. Должен быть какой-то код, который возвращает true/false перед нижним условием.

if (node == null) {
    System.out.println("Наименьшая разница:");
    System.out.println(subSum1 - subSum2);
    // Вы должны вернуть логическое значение здесь, чтобы завершить рекурсию
}

Ваша рекурсия не завершилась, поэтому, даже если node равен null, она все равно продолжает выполнять нижнее условие. Это приводит к бесконечному циклу.

Это …

    node = headNode;

… определенно неправильно. Неясно, какую цель вы преследовали, если таковая вообще была, но то, что она на самом деле делает, так это гарантирует, что каждый вызов метода игнорирует аргумент, полученный в его параметре node, в пользу поля headNode объекта.

Это усложняет проблему, описанную @FerryTo в их ответе, поскольку даже если вы добавите оператор return в оператор if (node == null), чтобы сделать его базовым случаем, каждый рекурсивный вызов будет учитывать headNode, в то время как вы, вероятно, хотите, чтобы каждый из них учитывал преемника ранее рассмотренного. Вероятно, вы просто хотите удалить это присваивание.

Каждая из этих проблем по отдельности будет приводить к незавершающейся рекурсии, что также объясняет длинный трассировку стека. Когда рекурсия в конечном итоге исчерпывает доступное пространство стека, трассировка стека будет содержать сотни или даже тысячи уровней.

Ответ или решение

Чтобы разобраться с вашей проблемой, давайте проанализируем предоставленный код на наличие ошибок, связанных с рекурсией, и выделим основные моменты, требующие исправления.

Проблема

Ваш метод smallestDifference должен вычислять наименьшую разницу между двумя суммами, но у него отсутствует корректное условие завершения (базовый случай). В результате, при достижении конца связанного списка, рекурсия не останавливается, и это приводит к бесконечному циклу.

Код и его анализ

Вот ваш первоначальный код:

public boolean smallestDifference(Node node, int subSum1, int subSum2) { 
    node = headNode; // ошибка
    boolean addSub1 = false;
    boolean addSub2 = false;

    if (node == null) {
        System.out.println("Smallest difference:");
        System.out.println(subSum1 - subSum2);
        // Пропущен return здесь
    }

    if (subSum1 <= subSum2) {
        return smallestDifference(node.next, subSum1 + node.value, subSum2);
    } else {
        return smallestDifference(node.next, subSum1, subSum2 + node.value);
    }
}

Ошибки в коде

Отсутствие условия завершения: В блоке if (node == null) вы не возвращаете значение. Это означает, что метод будет продолжать выполняться после того, как обход связного списка завершится.
Использование headNode: Присваивание node = headNode в начале метода отменяет все переданные аргументы, всегда начиная с головы списка. Это крайне нежелательно для рекурсивного обхода, так как текущее состояние node не обновляется.
Проблема бесконечности рекурсии: Поскольку не было условия окончания (не возвращая значения из if (node == null)), метод был вызван многократно без остановки.

Исправленный код

Предлагаю следующий пересмотренный код:

public boolean smallestDifference(Node node, int subSum1, int subSum2) { 
    // Убираем присваивание headNode
    if (node == null) {
        System.out.println("Smallest difference:");
        System.out.println(Math.abs(subSum1 - subSum2)); // Возвращаем абсолютное значение разницы
        return true; // Базовый случай завершает рекурсию
    }

    if (subSum1 <= subSum2) {
        return smallestDifference(node.next, subSum1 + node.value, subSum2);
    } else {
        return smallestDifference(node.next, subSum1, subSum2 + node.value);
    }
}

Объяснение исправлений

Добавлено условие завершения: Теперь метод возвращает true, когда достигает конца списка.
Убрано присваивание headNode: Это позволяет рекурсивно передавать правильный node в каждую итерацию.
Использование абсолютного значения разницы: Для корректного отображения наименьшей разницы, выводим именно абсолютное значение.

Заключение

Эти изменения должны решить вашу проблему с рекурсией и позволить вашему методу корректно вычислять наименьшую разницу. Всегда старайтесь проверять условия завершения в рекурсивных методах, чтобы избежать бесконечных зацикливаний. Надеюсь, этот ответ помог вам разобраться с вашими ошибками, и ваш код теперь будет работать корректно!