0

factorial program using recursion in C:

long fact(int n)
{
    if (n == 1)
       return 1;
    else
    {
       return n*fact(n - 1);
    }
}

The program works perfectly for numbers up to 12. But for numbers bigger than that the fact gives a wrong value.

The range of long is sufficient for such numbers then what is the reason that factorial is not getting calculated for the numbers greater than 12?

Lundin
  • 195,001
  • 40
  • 254
  • 396
Ross
  • 617
  • 2
  • 9
  • 23
  • 2
    Add to your program `#include ` and `printf("max:%ld\n", LONG_MAX);`, that should explain it. – Pascal Cuoq Jun 30 '14 at 08:47
  • but the return type is long rite? – Ross Jun 30 '14 at 08:47
  • @Ross Please use Divide and Conquer approach to solve this and use double to store the result – SNR Jun 30 '14 at 08:47
  • 1
    How are you printing the _long_? – devnull Jun 30 '14 at 08:49
  • 1
    Not all systems have 64-bit `long` datatype (not even on a 64-bit computer/OS). On those systems the max value you can get from a `long` is a little over 2 billion. Anything more than that limit causes overflows. – Some programmer dude Jun 30 '14 at 08:49
  • @Ross: int*int will result an int. So change the type of parameter to Double. – SNR Jun 30 '14 at 08:52
  • You are asking about factorial of big numbers. So a billion is a big number. Take a minute or two to think about what the factorial of a billion is. – gnasher729 Jun 30 '14 at 08:52
  • @Houssni Please don't edit posts to change the meaning of the code and please don't edit posts with minor changes that add nothing of value. Rollback. – Lundin Jun 30 '14 at 09:00
  • possible duplicate of [Overflow in factorial](http://stackoverflow.com/questions/23463794/factorial-overflow) – Mohit Jain Jun 30 '14 at 09:00
  • @Lundin I did not change the meaning of the code, the code was identical, I found it more readable the way I editted it. But sorry for the damage. –  Jun 30 '14 at 09:03
  • 1
    @Houssni Apart from the edit being too minor, editing code to suit your personal preference of coding style is not ok. Coding style is subjective and there is no obvious right or wrong. You should only edit code to fix indention and such, where there is no indention in place. – Lundin Jun 30 '14 at 09:06
  • @Lundin I understand, I will keep that in mind next time :) –  Jun 30 '14 at 09:16
  • "The range of long is sufficient for such numbers" -- What makes you think so? And how do you know you're getting the wrong value? Include the code that determines that. – Jim Balter Jun 30 '14 at 09:19
  • @SNR There's no int*int here, it's int*long, and there's no Double type in C. – Jim Balter Jun 30 '14 at 09:21
  • @gnasher729 "Take a minute or two to think about what the factorial of a billion is"? Why? The OP is trying to find the factorial of 12, not of a billion. – Jim Balter Jun 30 '14 at 09:23
  • @Jim Balter I know I am getting the wrong value because I am verifying the answer on the calculator. And by sufficient I was referring to the numbers close to 12. And it comes out that from 13 onwards 32 bit is not sufficient – Ross Jun 30 '14 at 10:48
  • "I am verifying the answer on the calculator" -- verifying *what* answer? The code you posted provides no way to determine what the resulting value is. See `devnull`s important question above. "it comes out that from 13 onwards 32 bit is not sufficient" -- so, again, why did you claim it was? – Jim Balter Jul 01 '14 at 03:12

1 Answers1

1

The range of long is sufficient for such numbers

No, that's not always true. long is only guaranteed to be at least 32-bit, but the value of 13! is 6227020800, or 0x17328CC00, which can not be held in a 32-bit integer.

Try using long long instead.

Jim Balter
  • 16,163
  • 3
  • 43
  • 66
Yu Hao
  • 119,891
  • 44
  • 235
  • 294