Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Please tell me why the same piece of code behaves differently in C++ and JAVA.

Ok first I implement a function to calculate the factorial of an Int RECURSIVELY

In JAVA:

int f(int x)
    {

        if(x==1)return 1;
        return(x*f(x-1));
    }

System.out.println(f(5)); -----> outputs 120, ok that makes sense.

JAVA METHOD 2:

int f(int x)
    {

        if(x==1)return 1;
        return(x*f(--x));
    }

System.out.println(f(5)); -----> outputs 120, ok that makes sense too.

But here is a twist in C++:

C++ METHOD 1:

int f(int x)
{
    if(x==1)return 1;
    return (x*f(x-1));

}

cout << f(5) ; -----> outputs 120, ok now keep reading!

C++ METHOD 2:

int f(int x)
{
    if(x==1)return 1;
    return (x*f(--x));

}

cout << f(5) ; -----> outputs 24. This is surprising. But Why??

I have tried tracing this multiple times and have failed. It makes sense in java because each recursive call gets its own piece of memory and pre decrement operator -- will decrease and yield the decreased value. Why does it work as expected in JAVA but not In C++?

share|improve this question
2  
This is likely a something with a sequence point. --x may be evaluated before it is used for x *. –  MichaelT May 1 '13 at 21:03
1  
Flagged for migration to SO, good question but it's specific about a particular detail of how C++ works. List the C++ implementation you're working in too, in case it's relevant. –  Jimmy Hoffa May 1 '13 at 21:12
2  
If I were reviewing this bit of code, I'd tell you not to use the decrement operator if the variable wasn't going to be used again. –  Blrfl May 1 '13 at 21:32
    
The JVM is a stack based machine where as C++ target register machines. The order of evaulation is undefined for C++. –  James May 1 '13 at 22:41
add comment

closed as off topic by Jimmy Hoffa, Rein Henrichs, Robert Harvey, BЈовић, Kilian Foth May 2 '13 at 6:49

Questions on Programmers Stack Exchange are expected to relate to software development within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

up vote 9 down vote accepted
f1(int x)
{
  if(x = 1) return 1;
  return (x * f1(--x));
}

vs

int f2(int x)
{
    if(x==1)return 1;
    return (x * f2(x-1));
}

The inner bit of the f1 code compiles to (gcc -S ...):

.L2:
    subl    $1, -4(%rbp)
    movl    -4(%rbp), %eax
    movl    %eax, %edi
    call    f1
    imull   -4(%rbp), %eax

While f2 compiles to

.L2:
    movl    -4(%rbp), %eax
    subl    $1, %eax
    movl    %eax, %edi
    call    f2
    imull   -4(%rbp), %eax

You can see that the operations of the subl and movl are in a different order between the two. In paticular, f1 is subtracting first before the value is moved for it to be used in calculation.

f1 has a side effect of modifying the value of x when it invokes --x. This side effect is being order so that it happens to the value before the multiply is being evaluated with the same value.

In f1, you have:

First invocation
x = 5; x * f1(--x) --> x = 4 ; x * f1(4)

Second invocation
x = 4; x * f1(--x) --> x = 3 ; x * f1(3)

Third invocation
x = 3; x * f1(--x) --> x = 2 ; x * f1(2)

Fourth invocation
x = 2; x * f1(--x) --> x = 1 ; x * f1(1)

Now, you populated these values up:

x = 1 ; x * f1(1) ; 1 * 1 --> return 1

x = 2 ; x * f1(2) ; 2 * 1 --> return 2

x = 3 ; x * f1(3) ; 3 * 2 --> return 6

x = 4 ; x * f1(4) ; 4 * 6 --> 24

This is because you are in an undefined area of the compiler when you do x * --x. To allow certain optimizations, some things have to be undefined. This is one of them - the compiler is allowed to process it any way it wants.

Don't use --x or x-- unless you want the change in the assignment.


so I was thinking that x will be always evaluated before --x. please tell me why I am wrong here? The compiler should not therefore try to optimize in these types of situations

From wikipedia:

A sequence point defines any point in a computer program's execution at which it is guaranteed that all side effects of previous evaluations will have been performed, and no side effects from subsequent evaluations have yet been performed.

There is no sequence point in the expression x * --x, so that there is no spot at which the c compiler will guarantee that the evaluation happens in a certain order.

The associativity of an operator has to deal with how an expression is parsed.

Consider 4 * 3 + 2. The associativity and precedence of * and + guarntees that this is parsed as (4 * 3) + 2.

Math operators are left associatve, while assignment are right associative. While 4 + 3 + 2 + 1 is parsed as (((4 + 3) + 2) + 1) - it doesn't matter too much with this. Assignments are right associatve. a = b = c = 4 becomes (a = (b = (c = 4))). Notice which way the parentheses group.

This has no bearing on the question of which side of a mathematical term is evaluated first in the context of x * --x.

share|improve this answer
    
Thank You so Much for your detailed answer! I now understand it much better! –  superspacemarines May 2 '13 at 0:46
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.