Различные результаты в Java и C++ с использованием += в рекурсии
Очень простой следующий Java-код имеет странный вывод, но тот же логический код на C и C++ имеет правильный вывод. Я пытаюсь с JDK 1.7 и JDK 1.3 (относительно JRE), странный вывод всегда есть.
public class Test {
public static int sum=0;
public static int fun(int n) {
if (n == 1)
return 1;
else
sum += fun(n - 1); // this statement leads to weird output
// { // the following block has right output
// int tmp = fun(n - 1);
// sum += tmp;
// }
return sum;
}
public static void main(String[] arg) {
System.out.print(fun(5));
}
}
Вывод равен 1, что должно быть 8. Относительный код C/C++ выглядит следующим образом:
#include<stdio.h>
int sum=0;
int fun(int n) {
if (n == 1)
return 1;
else
sum += fun(n - 1);
return sum;
}
int main()
{
printf("%d",fun(5));
return 0;
}
Добавление тестового кода Java:
class A {
public int sum = 0;
public int fun(int n) {
if(n == 1) {
return 1;
} else {
sum += fun(n - 1);
return sum;
}
}
}
public class Test {
public static void main(String arg[]){
A a = new A();
System.out.print(a.fun(5));
}
}
8 ответов
Я собираюсь пройти через это в шутку (3) ради полного ответа. Для тех из вас, кому не интересно, почему это работает для C++, но не для Java, пожалуйста, проигнорируйте мой ответ.
Вот что делает Java:
внутри веселье (3)
sum += sum + fn(n-1) // sum is 0
становится
sum = 0 + fun(2) // sum is 0
Тогда внутри весело (2)
sum = 0 + fun(1) // sum is 0
Тогда внутри веселье (1)
return 1 // sum is 0
Вернуться внутрь веселья (2)
sum = 0 + 1; // sum is 0
становится
sum = 1; // sum will soon become 1
Вернуться внутрь веселья (3)
sum = 0 + 1; // sum is 1
становится
sum = 1; // sum gets reset to 1
Вот что делает C++:
внутри веселье (3)
sum += fn(n-1) // sum is 0
становится
sum = sum + fn(2) // sum is 0
Тогда внутри весело (2)
sum = sum + fn(1) // sum is 0
Тогда внутри веселье (1)
return 1 // sum is 0
Вернуться внутрь веселья (2)
sum = sum + 1 // sum is 0
становится
sum = 0 + 1 => sum = 1 // sum will soon become 1
Вернуться внутрь веселья (3)
sum = sum + 1 // sum is 1
становится
sum = 1 + 1 // sum will soon become 2
Что вы должны сделать: я не знаю, почему C++ оценивает sum после вызова функции, а не раньше. Я не знаю, если это в спецификациях. Но я знаю, что вы не должны зависеть от этого на любом языке. Правильное решение будет:
int fun(int n) {
if (n == 1)
return 1;
else
return n + f(n - 1);
}
Проблема в этой строке:
sum += fun(n - 1);
который обновляет переменную sum,
Предполагая, что вы просто пытаетесь суммировать числа от 1 до N, тогда он должен делать вычисления, которые вычисляют f(N) с точки зрения f(N - 1), Это не требует от вас ссылки на sum... и, конечно, вам не нужно его обновлять.
(Я стараюсь НЕ говорить вам, что ответ... потому что это вы узнаете больше, если вы поймете это самостоятельно.)
Между прочим, в вашем алгоритме нет ничего специфического для Java.
Стоит отметить, что реальная проблема не связана со статическими переменными и переменными экземпляра. Реальная проблема заключается в том, что рекурсивная функция, подобная этой, не должна использовать переменную любого типа. Теперь в этом примере вы можете сойти с рук, но если рекурсия включает в себя что-то вроде этого: f(N) = f(N-1) + f(N-2) Вы можете обнаружить, что разные деревья вызовов мешают друг другу.
Более правильное решение в этом случае - написать метод следующим образом:
int fun(int n) {
if (n == 1)
return 1;
else
return n + f(n - 1);
}
Как я уже сказал, вам не нужно ссылаться или обновлять sum переменная.
Текущие ответы на этот вопрос не доходят до корня проблемы. Поведение в Java связано с тем, что:
sum += fun(n - 1);
эквивалентно:
sum = sum + fun(n - 1);
где sum оценивается раньше fun(n - 1) и значение сохраняется. Мы можем увидеть это, перейдя в раздел JLS 15.26.2. Составные операторы присваивания, которые говорят:
Составное выражение присваивания в форме E1 op= E2 эквивалентно E1 = (T) ((E1) op (E2))
и затем оценивается левый операнд, а затем оценивается правый операнд и выполняется операция. Так sum оценивается перед каждой итерацией рекурсии и 0 весь путь назад.
Это также означает, что если вы переключили линию на это:
sum = fun(n - 1) + sum ;
это даст желаемый эффект с fun будет оцениваться в первую очередь.
В C++:
sum += fun(n - 1);
также эквивалентно:
sum = sum + fun(n - 1);
это описано в проекте стандарта C++ 5.17 Операторы присваивания и сложного присваивания, в которых говорится:
Поведение выражения вида E1 op= E2 эквивалентно E1 = E1 op E2, за исключением того, что E1 оценивается только один раз.[...]
Основным отличием является то, что порядок оценки левой и правой стороны не указан, что рассматривается в разделе 1.9 Пункт 15 выполнения программы, в котором говорится:
Если не указано иное, оценки операндов отдельных операторов и подвыражений отдельных выражений не являются последовательными.[...]
так что 1 а также 8 оба будут действительными результатами в C++. Мы можем видеть, что этот live gcc дает нам 8, а clang дает нам 1.
public static int fun(int n) {
if (n == 1)
return 1;
else
return n + fun(n - 1);
}
Кстати, если вы хотите сделать это так же, как в коде C, просто определите сумму как "Integer" вместо "int"
Попробуй это:
public class Test {
public static int fun(int n) {
System.out.println("processing n " + n );
if (n == 1)
return 1;
else{
return n + fun(n - 1);
}
}
public static void main(String[] arg) {
System.out.print(fun(5));
}
}
Вы действительно должны пройти через свою логику там. Это не имеет никакого смысла. Является ли "странный" вывод, что f(5) = 8? (вы на самом деле случайно написали функцию, которая вычисляет 2^(n-2), но это не относится к делу)
Я не могу объяснить вам, где какой-то синтаксис неправильный - это сам алгоритм. Это просто не делает то, что вы намеревались сделать. Большой красный флаг, который должен выделиться: переменная n даже не добавляется напрямую к сумме! Когда вы вызываете fun(5), эти 5 даже не используются. Это просто передается в F (4).
Мне кажется, что ваша логика была такой: рекурсивный цикл из n->1, и добавить это к сумме. В этом случае ваша функция должна была быть:
void fun(int n){
if(n == 0)
return;
sum += n;
fun(n-1);
}
или что-то типа того. Но это не очень... рекурсивный способ делать вещи. Вы были бы намного лучше без переменных вообще. Не базовый случай: вернуть n+fun(n-1).
Также в будущем, когда вы скажете, что какой-то код имеет "странный вывод", вы, вероятно, должны предоставить и 1) странный вывод, и 2) ожидаемый результат. Мы просто догадываемся о том, что вы хотели написать.
Попробуй это
static int getsum(int num){
int sum = 0;
if(num == 1){
return num;
}else{
sum = num+getsum(num-1);
}
return sum ;
}