CODEWITHSUNDEEP
crecursion
Balraj Allam
Balraj Allam

Reputation: 611

C - recursive function for sum of n natural numbers

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?

Upvotes: 4

Views: 1854

Answers (3)

Pradeep Yenkuwale
Pradeep Yenkuwale

Reputation: 300

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

Upvotes: -1

Tobias K.
Tobias K.

Reputation: 3082

--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.

Upvotes: 4

Antti Haapala -- Слава Україні
Antti Haapala -- Слава Україні

Reputation: 133899

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...

Upvotes: 13

Related Questions