Recursion flaw — where is this code going wrong?

Question

I'm trying to sum integers, but I don't know where the flaw is in this code just tell me where is the flaw in this code, don't give other ways to solve this question

The output should be 6 but the code gives 4.

int SUM(int n) { 
    cout<<n<<endl; 

    if(n!=1) 
    return n + SUM(--n); 

    return n; 
}
int main() { 

    cout<<SUM(3)<<endl;

}

`return n + SUM(--n);` is highly suspicious, as you're referencing n, but mutating it somewhere else in the same expression. It's probably sequencing differently from what you expect. — user1937198, Sep 19 '15 at 00:50
Why decrement instead of just passing `n-1` as the argument? You have an order of evaluation problem as written — it is undefined how things are calculated, but the decrement probably occurs before the `n` on the LHS of the addition is evaluated, leading to the result you see. — Jonathan Leffler, Sep 19 '15 at 00:51
Bad luck! Undefined behaviour is undefined, and one of the possible ways undefined behaviour can work is 'as expected'. And sometimes it doesn't work as expected. Don't use undefined behaviour. — Jonathan Leffler, Sep 19 '15 at 00:53
Note that you also got an answer from Jeremy Friesner, and user1937198 also pointed out the same problem. — Jonathan Leffler, Sep 19 '15 at 00:55

score 4 · Answer 1 · answered Sep 19 '15 at 00:50

4

return n + SUM(--n);

I believe the flaw is in the above line. Decrementing n is probably not what you wanted to do; more likely you wanted to do this:

return n + SUM(n-1);

answered Sep 19 '15 at 00:50

Jeremy Friesner

70,199
15
131
234

1

To elaborate, there is no guarantee by the compiler that the `--n` operation happens *after* the `n + SUM(...)` operation. Thus, such a simple looking expression results in undefined behaviour. If n=3 prior to this line, you could be returning `3 + SUM(2)` **or** `2 + SUM(2)`. – Ephemera Sep 19 '15 at 01:23
1

One of the interesting factoids is that there's a sequence point after the arguments to the function and the function designator have been evaluated (and another before the function returns), and very often having a sequence point around fixes undefined behaviour. However, in this case, it does not guarantee whether the LHS or the RHS of the expression is evaluated first, and if (as seems to be the case) the RHS is evaluated first, then `n` is decremented before the LHS is evaluated. (See also [In C99, is `f()+g()` undefined or merely unspecified?](http://stackoverflow.com/questions/3951017)) – Jonathan Leffler Sep 19 '15 at 02:51

Recursion flaw — where is this code going wrong?

1 Answers1