Why code is implemented differently on changing order in the assignment statement?

Question

I am calling the factorial function defined in the following manner by reference.

int factorial(int &n) {
    n--;
    if (n>0) return factorial(n)*(n+1);
    else return 1;
}

when I pass the value 5 it returns the value 1 as I'd expected. But when I define the factorial function in the following way it returns the factorial of 5 that is 120.

int factorial(int &n) {
     n--;
     if (n>0) return (n+1)*factorial(n);
     else return 1;
}

I conjectured that the expression is evaluated in linear order and when a function is invoked in the expression all the values of local variables and the component expressions that have been evaluated so far in the original expression are stored and when the function returns control back to the caller these values that are retained are used in computation of the expression and not their modified values.

Is my hypothesis correct? Kindly enlighten me.

After correcting your typo it is clear that n doesn't maintain its value because it is passed by reference. — stefaanv, Mar 21 '16 at 14:19
@NathanOliver you used same n for both functions. Doesn't it matter? — Abdul Rehman, Mar 21 '16 at 14:22
If you made a mistake in your question, [edit it](http://stackoverflow.com/posts/36133311/edit). — n. m. could be an AI, Mar 21 '16 at 14:22
@NathanOliver: [Resetting `n` to 5 makes a difference](http://coliru.stacked-crooked.com/a/6fd60496d5651ccf) — R_Kapp, Mar 21 '16 at 14:24
@R_Kapp Thanks for that, Forgot it was a reference. even when I knew it was. — NathanOliver, Mar 21 '16 at 14:24
@NathanOliver: easy to forget since recursion and reference parameters don't play that well together. — stefaanv, Mar 21 '16 at 14:26
"I am calling the factorial function defined in the following manner". Do you need to define it this way for some reason? If not, change the definition, it's clearly a bug. — n. m. could be an AI, Mar 21 '16 at 14:28
I know there is absolutely no need to call the factorial function by reference. I just wanted to learn more about the exact mechanism of function call. — Siddharth Joshi, Mar 21 '16 at 14:29

Barry · Accepted Answer · 2016-03-21T14:29:13.057

10

I conjectured that the expression is evaluated in linear order [...]

Yes and no. The order of evaluation is typically done in linear order (either first to last or last to first), but is unspecified. When you write factorial(n)*(n+1), the compiler is allowed to evaluate (n+1) first or factorial(n) first. Different compilers will do it differently. Moreover, different versions of the same compiler could even change orderings, so that's not something you should ever rely on. The standardese is in [intro.execution]:

Except where noted, evaluations of operands of individual operators and of subexpressions of individual expressions are unsequenced. [...] If a side effect on a scalar object is unsequenced relative to either another side effect on the same scalar object or a value computation using the value of the same scalar object, and they are not potentially concurrent (1.10), the behavior is undefined.

(The exceptions are things like &&, ||, ,, and ?:)

In this case, you can easily avoid relying on the order dependency completely by just removing the reference:

int factorial(int n) {
    if (n>0) return factorial(n-1)*(n);
    else return 1;
}

Now factorial(n-1) * n and n * factorial(n-1), regardless of which order they're evaluated in, both work and give you the same correct answer. This also has the added benefit that nobody would expect factorial to actually modify its argument anyway:

int i = 6;
int f = factorial(i);
// now i is 1??

edited Mar 21 '16 at 14:29

answered Mar 21 '16 at 14:22

Barry

286,269
29
621
977

What I mean by linear order is that when the expression is evaluated left-associatively and if an expression occurs which invokes a function then the values that have been evaluated are retained after return of control. – Siddharth Joshi Mar 21 '16 at 14:36
@SiddharthJoshi Left-associative means that in `x*y*z`, `x*y` happens first and then `r*z` happens second. It doesn't dictate the order of when `x`, `y`, and `z` are evaluated. – Barry Mar 21 '16 at 14:38
What I want to ask you is that if in place of y there was an expression say `sum(x, z)` and sum modifies the variables then what happens to the value of this expression. Is the original value of `x` used in computing `x*y*z` or the modified values are used. – Siddharth Joshi Mar 21 '16 at 14:40
Further in this case the expression is evaluated in linear order i.e. left-associatively. – Siddharth Joshi Mar 21 '16 at 14:41
@SiddharthJoshi It's undefined behavior. The expression is **not** evaluated in linear order! The order of evaluation is unspecified. Relying on a particular ordering leads to undefined behavior. – Barry Mar 21 '16 at 14:41
Sorry but could you please explain the second quote in your answer through some example. – Siddharth Joshi Mar 21 '16 at 14:46
@SiddharthJoshi Undefined behavior is undefined, it's not an error. It could just lead to your code giving all sorts of random, inexplicable errors. See [undefined behavior and sequence points](http://stackoverflow.com/q/4176328/2069064). – Barry Mar 21 '16 at 14:50
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/106922/discussion-between-siddharth-joshi-and-barry). – Siddharth Joshi Mar 21 '16 at 14:51

Why code is implemented differently on changing order in the assignment statement?

1 Answers1