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++?
4
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.
1