recursion

[rakeshkool27]

yesterday i was just checking out the factorial(recursion) program once again to see something.The output for the program upto 12 was correct but for number >12 it gave wrong output. Confused with it i used the long integer for it also.why is it so??Can you find out the problem

#include<stdio.h>
long int factorial(int);//function prototype
int main()
{
	int num;
	long otpt;
	FILE *fp=fopen("Output.txt","a");//file to keep track of output
	printf("\nPLEASE ENTER THE VALUE WHOSE FACTORIAL IS REQUIRED:\n");
	scanf("%d",&num);
	while(num>20||num<1)//range should be between 1 & 20
	{
		printf("\nERROR-PLEASE ENTER BETWEEN 1 & 20:  ");
		scanf("%d",&num);
	}
	otpt=factorial(num);
	fprintf(fp,"INPUT:  %d",num);
	fprintf(fp,"\nOUTPUT:  %ld\n\n",otpt);
	printf("\nTHE FACTORIAL IS: %ld",otpt);
	fclose(fp);
	return 0;
}
long int factorial(int x)
{
	if(x<=1)
		return 1;
	else
		return(x*factorial(x-1));
}

[laserlight]

Compute 13! in some other way (manually, using a scientific calculator, using a calculator program with sufficient precision, etc) and compare the result with INT_MAX and LONG_MAX from <limits.h>.

[claudiu]

I just tested your factorial function and it worked fine. factorial(12) is in the hundreds of millions so not nearly big enough to overflow a long int. However factorial (13) is basically adding at least another digit so it's getting close if not actually overflowing.

EDIT: factorial(13) is about 1.9 Billion

[laserlight]

Come to think of it, another way is to compute 12! using your function, then compare the result with INT_MAX/13 and LONG_MAX/13. If 12! is greater than LONG_MAX/13, you know that 13! must be greater than LONG_MAX.

[claudiu]

It overflows at 14. I just tested it.

[rakeshkool27]

Compute 13! in some other way (manually, using a scientific calculator, using a calculator program with sufficient precision, etc) and compare the result with INT_MAX and LONG_MAX from <limits.h>.

aha...I found out the value
INT_MAX 2147483647

LONG_MAX 2147483647L

and 13!= 6227020800
and 6227020800 > INT_MAX.

So this might be the reason,isn't it???
So whether the INT_MAX VALUE CAN BE CHANGED or not??

[rakeshkool27]

It overflows at 14. I just tested it.

so mine overflows at 13.does it depends on the compiler??

[claudiu]

Ok so for me factorial(13) = 1 932 053 504
and factorial(14) is out of the long range. I don't know where you got that value that seems way too much.

Just use a normal calculator like the one in Accessories if u are using Windows or the one that comes with any Linux distro.

[rakeshkool27]

Ok so for me factorial(13) = 1 932 053 504
and factorial(14) is out of the long range. I don't know where you got that value that seems way too much.

Just use a normal calculator like the one in Accessories if u are using Windows or the one that comes with any Linux distro.

nah,just check out your answer again. I used the accessories calaculator.

[claudiu]

Yeah you are right. I don't know what I was doing wrong before probably mis-clicking. It's late overhere.

It overflows when you said, so there you go, that's the answer to your dilemma. Factorials as you just noticed get big really fast.