Ошибка переполнения стека в этой рекурсии

Question

Что не так с этой рекурсией в Java ?

public class findPyt
{
    public static int sum = 0;
    public static void main(String[] args)
    {
        findP(3, 4, 5);
    }

    public static void findP(int a, int b, int c)
    {
        sum = a+b+c;

        if (sum == 1000)
        {
            System.out.println("The Triplets are: "+ a +","+ b +","+ c);
        }
        else
        {
            findP(a*2, b*2, c*2);
        }
    }
}

Я получаю это исключение:

Exception in thread "main" java.lang.StackOverflowError
    at hello.findP(hello.java:12)
    at hello.findP(hello.java:19)

Когда я пытаюсь сделать то же самое в Ruby , я получаю это:

SystemStackError: stack level too deep


def pythagoreanTriples(a=3, b=4, c=5)

    if (a+b+c) == 1000
      puts "The Triplets are: "+ a +","+ b +","+ c
    else
    pythagoreanTriples(a*2, b*2, c*2)
    end
end

Answer 1

Попробуйте изменить sum == 1000 на sum >= 1000.Не существует тройной суммы, равной точно 1000, поэтому она пропускает условие завершения.

Кроме того, ваш код Ruby не соответствует вашему Java-коду (вы пропускаете else).Даже если он найдет сумму в 1000, он распечатает сообщение и продолжит повторяться до тех пор, пока не потерпит крах.

Answer 2

Что ж, если вы посмотрите на свой метод, который выполняет рекурсию, единственным выходным условием является случай, когда sum == 1000. Ваши текущие входные значения 3, 4 и 5. Эта сумма равна 12. Условие не выполняется истина, поэтому он пытается следующий набор, где сумма = 24. Затем 48, 96 и так далее. Сумма никогда не будет 1000, поэтому рекурсия никогда не закончится.

Answer 3

3 + 4 + 5 равно 12.

a * 2 + b * 2 + c * 2 = (a + b + c) * 2

12 * 2 * 2 =12 * 4

Теперь посмотрим: ваша программа остановится, когда сумма будет равна 1000. Этого никогда не произойдет, последовательность будет такой:

12 24 48 96 192 384 768 1536 ...

Если какое-то целочисленное переполнение не спасет вас, вы никогда не достигнете 1000. И, так как вы используете рекурсию, в конечном итоге происходит переполнение стека (если вам удалось решить проблему без рекурсии, этобесконечный цикл)

Answer 4

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

Например, обработка списка таким способом в Java может привести к тому, что ваш код будет ограничен обработкой только списков ограниченной длины до переполнения стекаи даже когда он работает, вы получите более низкую производительность и более высокое потребление памяти.Но возможность сбоя (скажем, более 1-10 миллионов элементов, поскольку стек по умолчанию составляет 8 МБ), более важна.

Если вы программируете на Scala вы или другие функциональные языки, этостиль будет уместным и эффективно поддерживается.

Answer 5

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

Answer 6

Кстати, вы умножаете на два.Вам нужно поднять до степени два, так что ^ 2 или ** 2.

Я основываю это на слове "pythagoreanTriples" в коде.