3

This is a recursive function I wrote that can compute the ways of coin change, and it can work perfectly.

int cc(int n, int k)
{
  if (n < 0 || k == 0)
    return 0;
  else if (n == 0)
    return 1;
  else
  {
    /*** WAY 1 : START ***/
    s.stk[++s.top] = k;
    int tmp = cc(n - d[k - 1], k);
    s.top--;
    return tmp + cc(n, k - 1);
    /*** WAY 1 :  END  ***/
  }
}

But, why it starts getting wrong answers if I change the code between two comments as follows:

/*** WAY 2 ***/
return (s.stk[++s.top] = k, cc(n - d[k - 1], k)) + (s.top--, cc(n, k - 1));
//     |<-----             A             ----->|   |<-----    B    ----->|

Aren't they equivalent?

P.S. Though it is not a good way to write like that (way 2), I just wonder why it can't work.

EDIT:

Though we don't know that whether A or B will do first, I tried to do some experiments.

The conclusion is that neither return A+B; nor return B+A; will get correct answers.

Kevin Dong
  • 5,001
  • 9
  • 29
  • 62
  • 1
    They are not. Also, since this is a finished piece of code please put this on code review instead of stack overflow. – bobtheboy Dec 18 '14 at 23:26
  • It seem to UB(undefined behavior). – BLUEPIXY Dec 18 '14 at 23:28
  • Why? Any UB places in this code? – Kevin Dong Dec 18 '14 at 23:29
  • Which one is evaluated first of `A` and `B` when `A + B` is not decided. There are side effects to evaluate the expression in association with it. – BLUEPIXY Dec 18 '14 at 23:31
  • 1
    Ooof, don't write code like that second one. It's way harder to read than the first one and even if it's correct is more difficult to understand and maintain. I doubt there are any benefits of that second one over the first. – templatetypedef Dec 18 '14 at 23:36
  • Anyway, all hese assignments to s.stk and s.top seem to be utterly pointless. Your function never reads from s.stk – gnasher729 Dec 19 '14 at 00:02
  • Yep, I shrink my code for readability. It is much more bigger than above. – Kevin Dong Dec 19 '14 at 00:05
  • @KevinDongNaiJia Are you certain that you covered all possibilities in your experiment to tell whether A+B and B+A would yield the same result? You might not have the correct data set! – RcnRcf Dec 19 '14 at 00:07
  • @RD445 A+B and B+A yields different results, but both of them are wrong. – Kevin Dong Dec 19 '14 at 00:10

1 Answers1

2

Read the "Undefined Behavior and Sequence Points" link given by @delnan for details. But the simplest explanation is that there is no sequence point between A + B. As such there is no guarantee as to which one of A and B would be evaluated first. That's why way 1 and way 2 are not equivalent.

In your case:

A = (s.stk[++s.top] = k, cc(n - d[k - 1], k))
B = (s.top--, cc(n, k - 1))

Now, the recursive calls to cc() will occur randomly, sometimes (decided at compile time not at runtime) on path A and sometimes on path B. As such, the order of calls is all screwed up.

You might want to add a print statement at the top of the function that would print the sequence number and the arguments on a new line. Then execute it with way 1 and way 2 using the same initial data. Collect the output in to two text files. Diff these two files and see for yourself where things go wrong.

RcnRcf
  • 356
  • 1
  • 8
  • Great point. Though we don't know that whether `A` or `B` will do first, I tried to do some experiments. Neither `return A+B` nor `return B+A` will get correct answers. – Kevin Dong Dec 18 '14 at 23:54
  • Sequence points aren't about guaranteeing which is executed first. (i.e. it's not either/or). The lack of sequence points mean that the behaviour is *entirely* undefined. – Oliver Charlesworth Dec 19 '14 at 00:00
  • 1
    @OliverCharlesworth Isn't the undefined aspect, in this case, just to decide whether to compute A before B OR compute B before A! – RcnRcf Dec 19 '14 at 00:04