recursion

This is a discussion on recursion within the C Programming forums, part of the General Programming Boards category; yesterday i was just checking out the factorial(recursion) program once again to see something.The output for the program upto 12 ...

  1. #1
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105

    recursion

    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

    Code:
    #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));
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,968
    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>.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    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
    Last edited by claudiu; 04-19-2010 at 11:23 PM.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,968
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    It overflows at 14. I just tested it.

  6. #6
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105
    Quote Originally Posted by laserlight View Post
    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??

  7. #7
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105
    Quote Originally Posted by claudiu View Post
    It overflows at 14. I just tested it.
    so mine overflows at 13.does it depends on the compiler??

  8. #8
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    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.

  9. #9
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105
    Quote Originally Posted by claudiu View Post
    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.

  10. #10
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 08:45 PM
  2. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 09:56 AM
  3. stack and recursion help needed!
    By LouB in forum C++ Programming
    Replies: 3
    Last Post: 07-01-2002, 02:19 PM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 08:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 01:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21