-5

Why is it that this first, recursion function for calculating a factorial using an if-statement works without reserving memory?

int factorial(int number) {
    int temp;
    if(number <= 1) return 1;
    temp = number * factorial(number - 1);
    return temp;
}

However, the second statement will compile and throw a segmentation fault.

long long int fact( long long int in ) {
    return in < 2 ?  : in * fact(in--);
}
Bartłomiej Semańczyk
  • 59,234
  • 49
  • 233
  • 358
mreff555
  • 1,049
  • 1
  • 11
  • 21
  • 2
    Not knowing what "using an if statement works without reserving memory" stands for, `in * fact(in--)` is [undefined behavior](http://stackoverflow.com/questions/949433/why-are-these-constructs-using-undefined-behavior) and it is bad because it might pass the same value of `in` as passed to the next call of `fact()`, and if so it will lead to infinite recursion. For that reasom, the second statement will throw a segmentation fault. – MikeCAT Nov 23 '15 at 02:14
  • The first function was copied verbatim from a cplusplus.com tutorial. – mreff555 Nov 23 '15 at 03:58
  • I found this [recursive factorial - C++ Forum](http://www.cplusplus.com/forum/beginner/16482/) and some other threads with google, but none of them were saying such a weird thing that it works without reserving memory. Since this function is not tail-recursive, I think this do will reserve some memory on the stack. – MikeCAT Nov 23 '15 at 04:05
  • The `if` and `ternary operator` affect execution and not variable memory. A good compiler will produce the same code (provided the `if` statement has the same meaning as the ternary operator). Print assembly listing of each function and compare. You may need to experiment with different optimization settings. – Thomas Matthews Nov 23 '15 at 04:38

1 Answers1

2
long long int fact( long long int in ){
    return in < 2 ?  : in * fact(in--);
}

Suffers from the following problems.

Problem 1

You don't have a value in the "true" part of the ternary operator.

    return in < 2 ?  : in * fact(in--);
                   ^^ Missing value

Problem 2

Depending on whether in or fact(in--) is evaluated first, the function could be:

long long int fact( long long int in ){
    int temp1 = in;
    in--
    long long temp2 = in < 2 ?  : (temp1-1) * fact(temp1);
    return temp2;
}

or

long long int fact( long long int in ){
    int temp1 = in;
    in--;
    long long temp2 = in < 2 ?  : temp1 * fact(temp1);
    return temp2;
}

Problem 3

Regardless of how the term in * fact(in--) is evaluated, the value passed to the next invocation of the function is in, not in - 1. Hence, you run into infinite recursion, which causes stack overflow.

Solution

long long int fact( long long int in ){
    return in < 2 ? 1 : in * fact(in-1);
}
R Sahu
  • 204,454
  • 14
  • 159
  • 270