Various results in Java and C ++ using + = in recursion

Question

The simplest Java code, the following, has strange output, but the same logical code in C and C ++ has the correct output. I am trying to use JDK 1.7 and JDK 1.3 (relative JRE), there is always a strange conclusion.

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)); } } 

The result is 1, which should be 8. Relative C / C ++ code is as follows:

 #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; } 

Adding test Java code:

 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)); } } 

Answer 1

I'm going to run this for fun (3) for the sake of a complete answer. For those who are not interested in why this works for C ++, but not for Java, please ignore my answer.

Here is what Java does:

inside fun (3)

 sum += sum + fn(n-1) // sum is 0 

becomes

 sum = 0 + fun(2) // sum is 0 

Then inside fun (2)

 sum = 0 + fun(1) // sum is 0 

Then inside fun (1)

 return 1 // sum is 0 

Back inside fun (2)

 sum = 0 + 1; // sum is 0 

becomes

 sum = 1; // sum will soon become 1 

Back inside fun (3)

 sum = 0 + 1; // sum is 1 

becomes

 sum = 1; // sum gets reset to 1 

Here is what C ++ does:

inside fun (3)

 sum += fn(n-1) // sum is 0 

becomes

 sum = sum + fn(2) // sum is 0 

Then inside fun (2)

 sum = sum + fn(1) // sum is 0 

Then inside fun (1)

 return 1 // sum is 0 

Back inside fun (2)

 sum = sum + 1 // sum is 0 

becomes

 sum = 0 + 1 => sum = 1 // sum will soon become 1 

Back inside fun (3)

 sum = sum + 1 // sum is 1 

becomes

 sum = 1 + 1 // sum will soon become 2 

What you should do: I do not know why C ++ evaluates sum after executing a function call, and not earlier. I do not know if this meets the specifications. But I know that you should not depend on it in any language. The right decision:

 int fun(int n) { if (n == 1) return 1; else return n + f(n - 1); } 

Answer 2

The problem is this line:

  sum += fun(n - 1); 

which updates the sum variable.

Assuming you're just trying to sum numbers from 1 to N, then he should do a calculation that calculates f(N) in terms of f(N - 1) . This does not require you to reference sum ... and, of course, you do not need to update it.

(I try NOT to tell you that the answer is ... because you learn more if you yourself understand.)

---

By the way, in your algorithm there is nothing specific Java related to the flaw ...

---

It is worth noting that the real problem is not related to the static and instance variables. The real problem is that such a recursive function should not use any variable. Now in this example you can get away with it, but if the recursion includes something like this: f(N) = f(N-1) + f(N-2) you may find that different call trees interfere with each other to a friend.

A better solution in this case is to write a method as:

 int fun(int n) { if (n == 1) return 1; else return n + f(n - 1); } 

As I said, you do not need to reference or update the sum variable.

Answer 3

Current answers to this question do not fall into the root of the problem. The behavior in Java is due to the fact that:

 sum += fun(n - 1); 

is equivalent to:

 sum = sum + fun(n - 1); 

where sum is evaluated to fun(n - 1) , and the value is saved. We can see this by going to the JLS section 15.26.2. Compound Assignment Operators , which states:

The compound assignment expression E1 op = E2 is equivalent to E1 = (T) ((E1) op (E2))

and then the left operand is evaluated, and then the right operand is processed and the operation is performed. So, sum is evaluated before each iteration of recursion and 0 completely back.

It also means that if you switched the line to this:

 sum = fun(n - 1) + sum ; 

it will create the desired effect, since fun will be rated first.

In C ++:

 sum += fun(n - 1); 

also equivalent to:

 sum = sum + fun(n - 1); 

this is described in the draft section of the C ++ 5.17 standard . Assignment and compound assignment operators that state:

The behavior of an expression of the form E1 op = E2 is equivalent to E1 = E1 op E2, except that E1 is evaluated only once. [...]

The main difference is that the evaluation procedure for the left and right sides is not specified, as described in section 1.9 paragraph 15 of the program, which states:

Except where noted, estimates of the operands of individual operators and subexpressions of individual expressions are not affected. [...]

and therefore 1 and 8 will both be valid results in C ++. We can see this live gcc gives us 8 and clang gives us 1 .

Answer 4

Try the following:

 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)); } } 

Answer 5

 public static int fun(int n) { if (n == 1) return 1; else return n + fun(n - 1); } 

By the way, if you want to do it the same way as in C code, just define the sum as "Integer" instead of "int"

Answer 6

You really need to go through your logic. It makes no sense. Is it a "strange" way out that f (5) = 8? (in fact, you accidentally wrote a function that computes 2 ^ (n-2), but it seems next to a dot)

I cannot explain to you where any syntax is incorrect - its algorithm itself. He just does not do what you intended to do. The big red flag that should stand out to you: the variable n is not even added to the sum! When you cause fun (5), this 5 is not even used. He just went to f (4).

It seems to me that your logic is this: a recursive loop from n-> 1 and add it to the sum. In this case, your function should be:

 void fun(int n){ if(n == 0) return; sum += n; fun(n-1); } 

or something like that. But this is not a very ... recursive way to do something. You will be much better without any variables. Non-base-case: return n + fun (n-1).

Also in the future, when you say that some code has “strange output”, you should probably provide 1) strange output, and 2) what you expected from the output. We all just guess what you wanted to write.

Answer 7

 return n <= 1 ? n : n + fun(n-1); 

Answer 8

Try

  static int getsum(int num){ int sum = 0; if(num == 1){ return num; }else{ sum = num+getsum(num-1); } return sum ; }