Why the function get the same value getting the factorial?

Question

I made a recursive function in C++ to get a factorial.

unsigned factorial(unsigned n, int j = 1) {
 j++;
 if(j < n) {
     return j * factorial(n, j);
 }
 return n;
}

It works. However, if i remove the return n; the function still working and i don't know why.

For simplicity, i got a control flow of factorial(5) with return n; removed, that is the following:

factorial (5,1) returns 2 * factorial (5,2)

factorial (5,2) returns 3 * factorial (5,3)

factorial (5,3) returns 3 * factorial (5,4)

And in the last, i.e factorial(5,4) since in the condition if(j < n), j = 5 and n = 5, the condition not satisfies and therefore factorial(5,4) must return 1 by default. Thus, the total recursive function must return 2 * 3 * 4 * factorial(5,4) = 2 * 3 * 4 * 1 = 4! and not 5!.

Thanks in advance.

What did you expect to happen when you removed `return n;`? Without the `return` your program has *undefined behaviour*, which means exactly what it says. — john, Apr 15 '20 at 21:33
But how is 'it's still working' incompatible with undefined behaviour? If the behaviour is not defined, then anything can happen, including still working. — john, Apr 15 '20 at 21:34
Does this answer your question? [Function with missing return value, behavior at runtime](https://stackoverflow.com/questions/2598084/function-with-missing-return-value-behavior-at-runtime) — Yunnosch, Apr 15 '20 at 21:34
No, C++ says that your program has *undefined behaviour*, Dev C++ could make this program do **anything** and Dev C++ would still be correct. — john, Apr 15 '20 at 21:37
Your mistake is that you think a bad program must show an error when it runs. That's not true. Bad programs only have *undefined behaviour*. — john, Apr 15 '20 at 21:38
The program did not undefined behaviour, it behaved as if it had not removed return n. Executed in Dev C++ — ESCM, Apr 15 '20 at 21:40
The C++ standard lays down behaviour for valid C++ programs. But for invalid C++ programs it just says the bahaviour is undefined, it doesn't say that they must not work. It's prefectly OK and normal for an invalid C++ program to work. It's not a compiler error if this happens, because *undefined behaviour* includes working. — john, Apr 15 '20 at 21:43

Konrad Rudolph · Accepted Answer · 2020-04-15T21:37:21.550

However, if i remove the return n; the function still working

Absolutely not. The code no longer works, and is in fact invalid (functions must return a value on all code paths, not doing so causes undefined behaviour). The effect of undefined behaviour may, under certain circumstances, look as if the code “works”. But its behaviour is actually arbitrary, and cannot be relied on.

It’s just that the C++ compiler is not required to note this error, and some silently accept the code, even though it’s invalid.

That said, all modern compilers will warn you about this code. You should always compile with warnings enabled, and ideally with warnings treated as errors, to flag such wrong code. For example, in clang and GCC it’s best practice to specify the command line flags -pedantic -Wall -Wextra. I additionally strongly recommend specifying the flag -Werror.

Thanks for your answer. You know how to avoid this error in Dev C++? — ESCM, Apr 15 '20 at 21:37

score 1 · Answer 2 · answered Apr 15 '20 at 21:43

1

The above answers about UD are correct, only I want to add a note on why this may seem working. Functions in C++ might return a value in the RAX register. The previous calculation may have left RAX with the answer. So it seems that it works by optimization.

Ie I put the value to RBX and then I would do mov rax, rbx to implement the return, but by chance RAX already got that value.

answered Apr 15 '20 at 21:43

Michael Chourdakis

10,345
3
42
78

This is indeed a likely explanation, but it doesn’t capture why it then fails arbitrarily. For instance, on godbolt with GCC 9.3 it works for some inputs and fails for others (well within range of the registers). – Konrad Rudolph Apr 15 '20 at 21:47

Vlad from Moscow · Answer 3 · 2020-04-15T21:47:34.770

Without the return statement the function has undefined behavior. For example this program outputted nothing when I run it.

#include <iostream>

unsigned factorial(unsigned n, int j = 1) {
 j++;
 if(j < n) {
     return j * factorial(n, j);
 }
// return n;
}

int main() 
{
    std::cout << factorial( 2, 1 ) << '\n';

    return 0;
}

Moreover even with the return statement the function is invalid because for example for the first argument equal to 0 it returns 0 instead of 1.

The recursive function can be defined as it is shown in the demonstrative program below.

#include <iostream>

unsigned long long factorial( unsigned n ) 
{
    return n  < 2 ? 1 : n * factorial( n - 1 );
}

int main() 
{
    const unsigned int N = 20;
    for ( unsigned int i = 0; i <= N; i++ )
    {
        std::cout << i << ": " << factorial( i ) << '\n';
    }

    return 0;
}

The program output is

0: 1
1: 1
2: 2
3: 6
4: 24
5: 120
6: 720
7: 5040
8: 40320
9: 362880
10: 3628800
11: 39916800
12: 479001600
13: 6227020800
14: 87178291200
15: 1307674368000
16: 20922789888000
17: 355687428096000
18: 6402373705728000
19: 121645100408832000
20: 2432902008176640000

Why the function get the same value getting the factorial?

3 Answers3