Erratic recursion in C

Question

I ran this code on C and in Java and I got 65 and 55 respectively. I cannot fathom how C can get 65. Please help.

int recur(int count) 
{
    if(count==10)
        return count;
    else
        return (count+recur(++count));
}

void main()
{
    printf("%d\n",recur(0));
}

Change `++count` to `count + 1`. The preincrement is incrementing `count` before both usages of it on that line. — Paul, Apr 14 '13 at 09:15
Oh, no wonder. Thanks! I was trying to understand recursion and had copied this code from another question on SOF which used increment operators. — xecutioner, Apr 14 '13 at 09:21

score 1 · Answer 1 · edited May 23 '17 at 10:25

1

return (count+recur(++count));

Is Undefined Behaviour. On different compilers you may have different results, even same compiler with different compilation options may result to different output.

edited May 23 '17 at 10:25

Community

1
1

answered Apr 14 '13 at 09:21

alexrider

4,449
1
17
27

This still doesn't help the OP _fix_ the problem. – Cole Tobin Apr 14 '13 at 09:24
@ColeJohnson: As Paulpro said in a comment to the question, if I changed the (++count) to (count+1), the code will run correctly. – xecutioner Apr 14 '13 at 09:28
It should still be part of the answer. An answer is supposed to be complete. Comments aren't gaurenteed to stay forever. – Cole Tobin Apr 14 '13 at 09:30
Yeah, if he had written a more complete explanation, I would've accepted the answer. – xecutioner Apr 14 '13 at 09:36

score 1 · Answer 2 · answered Apr 14 '13 at 09:27

Rewriting the code and testing on codepad with some debug statements shows what's happening. I encourage you to take this approach with running code to see what's happening.

int recur(int count) 
{
    int ret;
    if(count==10)
       ret = count;
    else {
       printf("Count Before = %d\n", count);
       ret =  (count +recur(++count));
    }
    printf("Count after = %d\n", ret);
    return ret; 
}

 void main()
 {
    printf("%d\n",recur(0));
 }

Running it gives this

Count Before = 0
Count Before = 1
Count Before = 2
Count Before = 3
Count Before = 4
Count Before = 5
Count Before = 6
Count Before = 7
Count Before = 8
Count Before = 9
Count after = 10
Count after = 20
Count after = 29
Count after = 37
Count after = 44
Count after = 50
Count after = 55
Count after = 59
Count after = 62
Count after = 64
Count after = 65
65

So you can see that recurse up to 10 first , then add 10, then 9 then 8 etc...

Changing it to i = (count + recur(count + 1))

gives

Count Before = 0
Count Before = 1
Count Before = 2
Count Before = 3
Count Before = 4
Count Before = 5
Count Before = 6
Count Before = 7
Count Before = 8
Count Before = 9
Count after = 10
Count after = 19
Count after = 27
Count after = 34
Count after = 40
Count after = 45
Count after = 49
Count after = 52
Count after = 54
Count after = 55
Count after = 55
55

But now the 10 level of nesting is only reached but added amount is still at 9.

Ie. the pre increment means you're adding an extra 10.

What this does is the following: recur(0) = 1 + recur(1) = 1 + 2 + recur(2) = 1 + 2 + 3 + recur(3) ..... = 1+2+3+4+5+6+7+8+9+10+recur(10) = 65 The problem lies in the fact that the pre-increment operator is the first to be executed in a statement, so it changes the recurring return statement to: return ((count+1) + (recur(count+1))); This causes an ambiguity as the return statement adds (argument+1) twice instead of (argument+(argument+1). The code should remove the increment operator and change it to (count+1). — xecutioner, Apr 14 '13 at 10:24

Erratic recursion in C

2 Answers2