What is the difference between the two in recursion?
This is a recursive function I wrote that can figure out ways to change the coin and it can work just fine.
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 does it start getting wrong answers if I change the code between the two comments like this:
/*** 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?
PS While it's not a good way to write like this (way 2), I'm just wondering why it can't work.
EDIT:
Although we don't know what will do in the first place, A
or B
, I tried to do some experiments.
The conclusion is that neither return A+B;
nor return B+A;
will they get the right answers.
source to share
Read the "Undefined Behavior and Consistency" link provided by @delnan for more information. But the simplest explanation is that there is no sequence point between A + B. As such, there is no guarantee as to which of the first grades A and B will be graded first. This is why path 1 and path 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 recursive calls to cc () will occur randomly, sometimes (resolved at compile time not at runtime) along path A and sometimes along path B. As such, the order of the calls is all confusing.
You might want to add a print statement at the top of the function that will print the sequence number and arguments on a new line. Then execute it with methods 1 and 2 using the same original data. Collect the output in two text files. Download these two files and see for yourself where things go wrong.
source to share