4

Below is the recursive function for sum of natural numbers up to n.

int calculateSum(int n) {
    if (n == 0){
        return 0;
    }else{
        return n + calculateSum(--n); //Replacing --n with n-1 works
    }
}

Input: 5

If I use --n then the output is 10, but when I replace --n with n - 1 then the correct result is returned (15). Why the difference?

Antti Haapala -- Слава Україні
  • 129,958
  • 22
  • 279
  • 321
Balraj Allam
  • 611
  • 6
  • 24

3 Answers3

13

As surprising as it might be, the behaviour of the expression 

n + calculateSum(--n);

is undefined, because --n not only evaluates to the value of n after being decremented by 1, it also changes n to the new value. The change (a side effect), however, is unsequenced in relation to the other evaluation of n (a value computation) on the left. And according to C11 Appendix J.2., the behaviour is undefined, when

A side effect on a scalar object is unsequenced relative to either a different side effect on the same scalar object or a value computation using the value of the same scalar object (6.5).

More of the same class of errors in this question.

You can consider yourself lucky when you got a wrong value, because your compiler could have also generated code that would return the "correct value"... given the phase of the moon, and the optimization settings, or the number of lines in the calling function...

Antti Haapala -- Слава Україні
  • 129,958
  • 22
  • 279
  • 321
4

--n also modifies the local variable n; the expression n-1 just returns the decremented value to pass it on to the recursive call, but does not modify your input-parameter.

In detail for the first iteration with input 5:

  • Correct is return 5 + calculateSum(5-1);
  • With --n you would also decrement from n and end up with 4 + calculateSum(4)

@user3386109 & @Yunnosch worded it this way: With --n you calculate the sum 0...(5-1) instead of 0...5.

See @Antti answer, it explains that it's actually undefined behaviour.

Tobias K.
  • 2,997
  • 2
  • 12
  • 29
  • 3
    Please go on with the explanation. How does this cause the observed behaviour? – Yunnosch Aug 07 '18 at 06:02
  • I added what can happen in the first iteration. Also see @Antti answer, it explains that it's actually undefined behaviour. – Tobias K. Aug 07 '18 at 06:10
  • 1
    @Yunnosch It does explain 10, because it's calculating 4+3+2+1+0 instead of 5+4+3+2+1. Of course, that doesn't change the fact that it's undefined behavior. – user3386109 Aug 07 '18 at 06:11
  • Damn, my mistake. Sorry. – Yunnosch Aug 07 '18 at 06:15
  • 1
    However, I recommend to move the mentioning of UB (via referring to Anttis answer, or directly) into the answer, instead of keeping it in a comment (which theoretically will be deleted at some point). – Yunnosch Aug 07 '18 at 06:17
  • 1
    In case you want to rub in my thinking mistake (you have earned that privilege ;-) ), explain that with `--n` the value of calculateSum(4) is the sum of all integers 0...(4-1), not 0...4. I was blind on that eye and therefor failed to understand your otherwise good explanation. You might make your answer more impressive that way. (You already have my upvote by the way, I appreciate people who find my mistakes.) – Yunnosch Aug 07 '18 at 06:27
-1

The following code snippet (a Function), you can call it in the main function which will return the sum of n natural numbers recursively

int NNumbers(int n)
{
    if(n != 0)
        return n + NNumbers(n-1);
    else
        return n;
}

In your code you are decrementing the value of n and then you are calculating the sum (i,e. Pre-Decrement), since the input is 5, it decrements 1 at each iteration and and then it will go for addition of natural numbers. so you are getting the result 10 instead of 15

Hope this helps for you :)

Thank you

marc_s
  • 732,580
  • 175
  • 1,330
  • 1,459
Pradeep Yenkuwale
  • 181
  • 3
  • 12
  • OP was already aware of the correct solution and only asked for an explanation of the result of the wrong method. This is therefor not answering the question. – Yunnosch Aug 07 '18 at 06:28
  • yes @Yunnosch i just submitted my answer before explanation, please have a look at my explanation and correct me if i am going wrong anywhere – Pradeep Yenkuwale Aug 07 '18 at 06:31
  • 2
    Sorry, but I do not see how this answer gives any additional insight in comparison to the older answers and it still consists mostly of a solution that was not asked for. – Yunnosch Aug 07 '18 at 06:35
  • If anything the explanation is misleading, mostly since there's no mention of UB (merely adding that mention won't make this more insightful than either of the other answers). – George Aug 07 '18 at 07:09