Why does the pre-decrement cause strange changes?

Question

I have the following code in C++

int factorial_recursivo(int factorial) {

 if(factorial <= 1) return 1;

 // To show all the factors in each iteration std::cout << factorial << std::endl;

 return factorial * factorial_recursivo(--factorial);

}

However, if i write a number n, the result is the factorial of the number n-1.

If i change the last line of code the factorial_recursivo(--factorial) by factorial_recursivo(factorial - 1) works properly.

Why this happen? I even printed the factors in console and it correctly showed. Per example, with factoria_recursivo(5) i got 5 4 3 2, however the result was 24.

Hint: Do you know precisely *when* that operator gets applied? — tadman, Jun 02 '20 at 03:04
Nothing wrong with that, it's a good question, but the trick is in knowing how that operator works. — tadman, Jun 02 '20 at 03:20
Thanks @tadman. Taking advantage of the fact that you are in the comments, what is the name of the process of "seeing what happens in each iteration?" in a loop or some recursive function, that is, analyze what happens in iteration 1, then in iteration 2, etc. What is the name of doing this? — ESCM, Jun 02 '20 at 03:24
"Debugging" if you're trying to fix a problem. Usually that's done in an interactive debugger so you can step through the code. — tadman, Jun 02 '20 at 03:43
In `factorial * factorial_recursivo(--factorial)` the order in which `factorial` and `factorial_recursivo(--factorial)` are calculated (before multiplying them) is unspecified. To understand what is happening, compare what the results will be with left-to-right evaluation (`factorial` evaluated, then `--factorial` evaluated and its result passed to `factorial_recursivo()`) versus right-to-left (`--factorial` evaluated first [changes `factorial`], its result passed to `factorial_recursivo()`, and then the value of `factorial` is evaluated again, before multiplying) — Peter, Jun 02 '20 at 04:10
Dues this answer your question: https://stackoverflow.com/questions/4176328/undefined-behavior-and-sequence-points — M.M, Jun 02 '20 at 05:02

score 2 · Accepted Answer · edited Jun 04 '20 at 09:45

2

You should do value - 1 instead:

return factorial * factorial_recursivo(factorial-1);

Executing:

return factorial * factorial_recursivo(--factorial);

results in unsequenced modification and access to factorial. On my laptop it actually produces 6 regardless of what I input as a parameter. Thank you M.M for asking me to clarify this in the comments. This is an example of undefined behavior.

Unsequencing occurs when the end result depends on which operand gets executed first. A simple example of this would be: arr[j] = arr2[++j]; The result of this would depend on whichever gets executed first, whether it would be arr[j] or arr2[++j]. .

edited Jun 04 '20 at 09:45

halfer

19,824
17
99
186

answered Jun 02 '20 at 03:06

bhristov

3,137
2
10
26

What do you mean by current frame? – ESCM Jun 02 '20 at 03:10
@EduardoS, by the current frame, I mean everything visible within the current local scope of the function. During recursion, we want to change the inner frame(scope) to narrow down the problem that we are solving. Please let me know how I can help you further. – bhristov Jun 02 '20 at 03:12
Mmm, you are saying that using pre decrement operator will change factorial out of factorial_recursive(--factorial) and therefore the first recursive iteration will be (factorial - 1) * factorial_recursivo(factorial - 1), right¡? – ESCM Jun 02 '20 at 03:20
@EduardoS. Yes, and you will end up having one iteration less because of that, this is why you only get 24 from factorial of 5, instead of 120. – bhristov Jun 02 '20 at 03:23
@bhristov Then you're mistaken. Operands are evaluated left to right. – user207421 Jun 02 '20 at 03:26
Oh, certainly i got 4 * f(4) = 4 * 3 * f(3) = 4 * 3 * 2 * f(2) = 4 * 3 * 2 * f(1) = 4 * 3 * 2 * 1 by the way, do you know what is the name of doing this "analysis" to a cycle or a recursive function? that is, what is the name of "see what happens in each iteration"? – ESCM Jun 02 '20 at 03:28
@EduardoS. I believe that it would be called debugging. I am not sure about what that specific form of it would be called. – bhristov Jun 02 '20 at 03:30
@bhristov It may be, from what I knew debugging is the act of finding errors in a source code. It makes sense, thanks for your help. – ESCM Jun 02 '20 at 03:33
@EduardoS. no problem. I am glad that I could help you. – bhristov Jun 02 '20 at 03:34
1

@user207421, A few operators are in recent years, but not `operator*`. You can find the [evaluation order rules here](https://en.cppreference.com/w/cpp/language/eval_order). (Reiterating a comment from the deleted answer, the simple rule is to forget most of these rules exist and split statements up when there's any uncertainty because as demonstrated, a clever mix is bound to cause confusion regardless of whether it is correct.) – chris Jun 02 '20 at 03:35
1

@user207421 Operands to `a * b` are unsequenced with respect to each other. More references are given under [this answer](https://stackoverflow.com/a/4183735). – dxiv Jun 02 '20 at 03:36
It would be good to edit the answer to explain what you meant about "the value in the current frame". Apparently from comments you treat it as there only being one variable `factorial` that has different frames, but in fact each execution of the function creates its own variable . Also your claim in comments of the code being equivalent to `(factorial - 1) * factorial_recursivo(factorial - 1)` is not correct – M.M Jun 02 '20 at 05:08

score 2 · Answer 2 · answered Jun 02 '20 at 05:04

2

The program has undefined behaviour because the operands of * are unsequenced, and so there are unsequenced read and writes of factorial.

The problem is essentially the same as the cases in this thread: Undefined behavior and sequence points

answered Jun 02 '20 at 05:04

M.M

138,810
21
208
365

Why does the pre-decrement cause strange changes?

2 Answers2