-6

So, recently i was doing a problem on factorials in one of the competitive coding websites where i used recursion. But on submitting it rejects my solution whereas on using a simple for loop it just accepts it. I have read many places that recursion is comparatively slower than loops, but i am still not sure if my code is rejected because of recursion or there is something really wrong. My code works fine in the IDE though.

This is my code using recursion.

UPDATE: Ok guys i asked one of my friends what could be the reason. so the reason is that the range of n was given to 1000 in the question. And if i am using recursion then factorial has to store that data which wouldnt be possible (if n==1000) because int cannot store that much(factorial of 1000) i.e why recursion wasn't accepting. I am new to S.O sorry if the question was not correctly explained I'll try asking in more detail next time so that i dont get downvotes.

 int factorial(int n)
    {
        
        if(n>1)
        {
            return n*factorial(n-1);
        }
        else
        {
            return 1;
        }
    }

int main() {
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
       cout<< factorial(n);
    }
    return 0;
Akshat kant
  • 49
  • 5
  • 2
    Are you sure you used `int` in your loop version? I ask because a factorial will quickly overflow a 32 bit integer. Looks like if `n` is greater than 12 you have an overflow because 13! which is `6227020800` is too large for a 32 bit int. Reference: https://en.wikipedia.org/wiki/Factorial – drescherjm Aug 07 '21 at 14:24
  • 1
    *My code works fine in the IDE though.* -- [Are you sure?](http://coliru.stacked-crooked.com/a/b76c9884b2d038f4). BTW, the probable reason for all of the downvotes you're getting is because you didn't do a simple test, just like the one I linked to. – PaulMcKenzie Aug 07 '21 at 16:11
  • If `n` is `1000` it clearly won't work correctly on either method. `1000!` is a very big number. Much larger than the largest `int` variable of the language or the system. You need to use a big int library or write one of your own. Most likely 20 is the largest `n` that will work without a big int library. – drescherjm Aug 08 '21 at 14:22
  • This may help: [https://stackoverflow.com/questions/269268/how-to-implement-big-int-in-c](https://stackoverflow.com/questions/269268/how-to-implement-big-int-in-c) – drescherjm Aug 08 '21 at 14:26

1 Answers1

0

Your code looks like it's working and as you said, your tests confirmed it. So, we are wondering what may be the reason of the rejection. To keep this objective, let's speak in objective terms. So, what are the objective disadvantages of recursion over a loop?

The stack

Function calls are stored in a memory section called the stack. When you write a recursive function that has too many self-calls, either due to a bad endsign (the function does not know when to stop) or due to a genuine need to repeat the operation many times, then you waste a lot of memory by storing all the calls in the stack. There is a limit of the stack, which, if surpassed, a stackoverflow error happens (see the name of this site). Instead, the iterative, loop-based approach in the case of factorials, it can use an index (the number to multiply by at a given moment) and the result (so far). So, instead of storing in the stack as many function calls as the input and wasting lots of resources, you get your solution based on 2 numbers:

while (n > 1) product *= n--;

Okay, you still have a possible issue with data overflow due to the factorial reaching very large numbers very quickly.

Maintainability

Programmers more frequently get into a dead end when they write recursive functions than when they write loops.

Lajos Arpad
  • 64,414
  • 37
  • 100
  • 175
  • 2
    Since factorial is overflows the an integer or a long int very quickly I doubt we have a stack overflow. – drescherjm Aug 07 '21 at 14:38
  • @drescherjm why would we exclude the case when n is very large, like 100 000? In that case, the data overflow causes chaotic, undesired results, true, but you get a SO as well. – Lajos Arpad Aug 07 '21 at 14:39
  • 1
    `n` can only be 20 or less for the code to work without overflowing the bounds of a 64 bit integer. At 21 you are larger than a 64 bit integer. I agree with you if a big math library is used but the code uses `int` and not a big math library. – drescherjm Aug 07 '21 at 14:40
  • @drescherjm Let me explain it differently then. Yes, after very few steps, the code will behave incorrectly due to data overflow. But that does not stop the algorithm from reaching stackoverflow. Yes, after a few steps multiplying the product with n will yield a smaller value than before due to data overflow. But data overflow does not stop the recursion and it will continue to run until an SO is thrown. – Lajos Arpad Aug 07 '21 at 15:13
  • @drescherjm or, to put it differently: do you think that the function shared in the question will stop running once data overflow happens, or, rather, do you think that it will continue to run with the chaotic data that is reached? My point is that the stop sign is that n is no longer higher than 0, hence, if n is 100 000, then the program will attempt to run the function 100 000 times, regardless of any data overflow issues that might obfuscate the data while the recursion is in progress. Data overflow will happen before SO, but SO will happen eventually as well. – Lajos Arpad Aug 07 '21 at 15:15
  • Yes it won't stop running at an integer overflow. The OP claimed that loop version was accepted by the online judge so `n` had to be small to get the correct answer unless the online judge didn't care about the value of the factorial returned at all and was only looking for a stack overflow or the code taking too long. – drescherjm Aug 07 '21 at 15:21
  • @drescherjm true. If the online judge cared about the algorithm, then he/she might have decided to ignore the chance for data overflow and maybe he/she was focusing more on memory management and program stability. – Lajos Arpad Aug 07 '21 at 15:25
  • 1
    the `int` will much faster overflow than the stack, and technically signed integer overflow is UB, so the stackoverflow isnt that relevant – 463035818_is_not_an_ai Aug 07 '21 at 15:27
  • @463035818_is_not_a_number SO is an extreme manifestation of the basic problem of recursion, which is: storing a function call upon each function call. Even after the 5th call, we have stored 5 functions on the stack, which is not yet causing a SO, but it's nonetheless memory waste. – Lajos Arpad Aug 07 '21 at 16:48