CODEWITHSUNDEEP
c++
ESCM
ESCM

Reputation: 262

Why the function get the same value getting the factorial?

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.

Upvotes: 0

Views: 81

Answers (3)

Vlad from Moscow
Vlad from Moscow

Reputation: 310980

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

Upvotes: 0

Michael Chourdakis
Michael Chourdakis

Reputation: 11158

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.

Upvotes: 1

Konrad Rudolph
Konrad Rudolph

Reputation: 545618

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.

Upvotes: 1

Related Questions