Calculating Factorial (Recursively & Iteratively)

Discussion in 'C' started by pradeep, Oct 30, 2006.

  1. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,645
    Likes Received:
    87
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    http://blog.pradeep.net.in
    Calculating the factorial of a number is a basic excercise while learning to program in C, many of us have done it iteratively, it can also be done recursively. I am posting both iterative and recursive versions below.

    Code:
     /* Recursive Version */
     unsigned int recursive_factorial(int n) 
      {
          return n>=1 ? n * recr_factorial(n-1) : 1;
      }
       
     /* Iterative Version */
      unsigned int iter_factorial(int n) 
      {
          int f = 1;
          int i;
          for(i = 1; i <= n; i++) 
         {
              f *= i;
          }
          return f;
      }
     
  2. bothie

    bothie New Member

    Joined:
    Nov 14, 2006
    Messages:
    24
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    student
    Location:
    Harare,Zimbabwe
    loved your functions they are just readable
     
  3. deepak.mobisy

    deepak.mobisy New Member

    Joined:
    Oct 24, 2007
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    Thanks for this kind of efoorts.
     
  4. oleber

    oleber New Member

    Joined:
    Apr 23, 2007
    Messages:
    37
    Likes Received:
    2
    Trophy Points:
    0
    Occupation:
    Software Developer (Perl, C/C++ and Java)
    Location:
    Hamburg, Germany
    Home Page:
    http://oleber.freehostia.com/
    Good work ;) but one small comment :p:

    Why having int and unsigned int?

    Just for coherence, and avoiding compilers work:

    Code:
    [color=#808080][i]/* Recursive Version */[/i][/color]
    [color=#993333]unsigned[/color] [color=#993333]int[/color] recursive_factorial[color=#66CC66]([/color][color=#993333]unsigned[/color] [color=#993333]int[/color] n[color=#66CC66])[/color] 
    [color=#66CC66]{[/color]
        [color=#B1B100]return[/color] n >= [color=#CC66CC]1[/color] ? n * recr_factorial[color=#66CC66]([/color]n-[color=#CC66CC]1[/color][color=#66CC66])[/color] : [color=#CC66CC]1[/color];
    [color=#66CC66]}[/color]
    Code:
    [color=#808080][i]/* Iterative Version */[/i][/color]
    [color=#993333]unsigned[/color] [color=#993333]int[/color] iter_factorial[color=#66CC66]([/color][color=#993333]unsigned[/color] [color=#993333]int[/color] n[color=#66CC66])[/color] 
    [color=#66CC66]{[/color]
        [color=#993333]unsigned[/color] [color=#993333]int[/color] f = [color=#CC66CC]1[/color];
        [color=#B1B100]for[/color][color=#66CC66]([/color][color=#993333]unsigned[/color] [color=#993333]int[/color] i = [color=#CC66CC]1[/color]; i <= n; i++[color=#66CC66])[/color] 
        [color=#66CC66]{[/color]
            f *= i;
        [color=#66CC66]}[/color]
        [color=#B1B100]return[/color] f;
    [color=#66CC66]}
    
    [/color]
     
  5. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  6. pr1nc3k1d

    pr1nc3k1d New Member

    Joined:
    Dec 6, 2007
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Romania
    Everything looks good and nice but what's if you want to calculate " 1000! " or the factorial of greater values ? :) The " unsigned int " type can memorize a value between 0 and +4,294,967,295 but " 1000! " is more much greater than the dimension of " long double " which is the greatest data type in C/C++. I think this is a good question. :) I'm waiting suggestions and ideas.
     
  7. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    The greatest has also the limitation for large numbers and I think you are with the greatest "long double"
     
  8. pr1nc3k1d

    pr1nc3k1d New Member

    Joined:
    Dec 6, 2007
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Romania
    Yes, it has, but i'm thinking on an algorithm which not calculates the result,but it generates it into a vector or a list. For example you can get a number with more than 1000 digits as result But if I put every digit of the number into a list I could view it and print it on the screen or into a file. So I think it could be a possible solution for this problem because there is no other data types which could memorize such a number. Opinions ?
     
  9. pr1nc3k1d

    pr1nc3k1d New Member

    Joined:
    Dec 6, 2007
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Romania
    I made it but I don't really like it cuz` it's slow. It took about 6-7 minutes waiting for the result of " 1000! ".

    Code:
    #include <iostream.h>
    #include <conio.h>
    #include <time.h>
    void main ()
    {
    	long int v[259000],i,n;
       double start;
       clrscr();
       v[0]=1;
       for(i=1;i<259000;i++) v[i]=0;
       cout<<"Enter the number: "; cin>>n;
       if(n==0 || n==1 ) cout<<n<<"!="<<"1";
       else
       {
          start = clock ();
       	long int c=0;
       	for(i=1;i<=n;i++)
          {
          	long int j;
         		for(j=0;j<=c;j++)
               v[j]*=i;
             for(j=0;j<=c;j++)
             {
             	if(v[j]>=10)
                {
                	v[j+1]=v[j+1]+v[j]/10;
                   v[j]=v[j]%10;
                   int k1=258999,cont=0;
                   while(v[k1]==0) { cont++; k1--; }
                   c=258999-cont;
                }
             }
            cout<<i<<"!=";
            for(j=c;j>=0;j--)
            		cout<<v[j];
            cout<<endl;
       	}
       start=clock()-start;   
       cout<<"It took "<<start<<" seconds to complete. ";
      }
       getch();
    }
     
  10. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,645
    Likes Received:
    87
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    http://blog.pradeep.net.in
    Goodness gracious! 6-7 mins?? Try to rethink your logic!
     
  11. pr1nc3k1d

    pr1nc3k1d New Member

    Joined:
    Dec 6, 2007
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Romania
    Yes but it prints on the screen the factorials in rows from 1 to a value .

    Here is the new version which prints the results into a file:

    Code:
    #include <stdio.h>
    #include <conio.h>
    #include <fstream.h>
    #include <time.h>
    void main ()
    {
    	long int v[259000];
       int i,n;
       double start;
    	ofstream fp_out;
       fp_out.open("result.txt", ios::out);
       v[0]=1;
       for(i=1;i<259000;i++) v[i]=0;
       printf("Enter the number: ");
       scanf("%d",&n); clrscr ();
       printf("-_-_- :L:O:A:D:I:N:G: -_-_-");
       if(n==0 || n==1 ) fp_out<<n<<"!=  "<<"1";
       else
       {
          start = clock ();
       	long int c=0;
       	for(i=1;i<=n;i++)
          {
          	long int j;
         		for(j=0;j<=c;j++)
               v[j]*=i;
             for(j=0;j<=c;j++)
             {
             	if(v[j]>=10)
                {
                	v[j+1]=v[j+1]+v[j]/10;
                   v[j]=v[j]%10;
                   int k1=258999,cont=0;
                   while(v[k1]==0) { cont++; k1--; }
                   c=258999-cont;
                }
             }
            fp_out<<i<<"!=  ";
            for(j=c;j>=0;j--)
            	   fp_out<<v[j];
    
            fp_out<<endl;
       	}
       start=clock()-start;
       clrscr ();
       printf("-_-_- :C:O:M:P:L:E:T:E:D: -_-_- \n Check out the result file! \n It took  %f ",start);printf(" seconds to complete. ");
      }
    	getch ();
       fp_out.close();
    }
     
  12. pr1nc3k1d

    pr1nc3k1d New Member

    Joined:
    Dec 6, 2007
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Romania
    Here it is. The factorial of the numbers from 1 over to 1000 in 51 seconds.

    Code:
    #include <stdio.h>
    #include <conio.h>
    #include <time.h>
    void main ()
    {
    	long int v[4000];
       int i,n;
       double start=0.0;
       v[0]=1;
       for(i=1;i<4000;i++) v[i]=0;
       printf("Enter the number: ");
       scanf("%d",&n); 
       if(n==0 || n==1 ) printf("%d",&n,"!=1");
       else
       {
          start = clock ();
       	long int c=0;
       	for(i=1;i<=n;i++)
          {
          	long int j;
         		for(j=0;j<=c;j++)
               v[j]*=i;
             for(j=0;j<=c;j++)
             {
             	if(v[j]>=10)
                {
                   v[j+1]=v[j+1]+v[j]/10;
                   v[j]=v[j]%10;
                   int k1=3999,cont=0;
                   while(v[k1]==0) { cont++; k1--; }
                   c=3999-cont;
                }
             }
            printf("%d",i);printf("!=  ");
            for(j=c;j>=0;j--)
            	   printf("%d",v[j]);
    		printf("\n");
       	}
       start=clock()-start;
       start/=1000;
       printf("It took  %f ",start);printf(" seconds to complete. ");
      }
    	getch ();
    }
     
  13. asadullah.ansari

    asadullah.ansari TechCake

    Joined:
    Jan 9, 2008
    Messages:
    356
    Likes Received:
    14
    Trophy Points:
    0
    Occupation:
    Developer
    Location:
    NOIDA
    For big number, You can use Srerling's Approximate Formula>>>>

    (n-1) ! ~ (2 Pi / (n))1/2e-(n) (n)(n)
     
  14. pr1nc3k1d

    pr1nc3k1d New Member

    Joined:
    Dec 6, 2007
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Romania
    Yes, but I wanted the full and correct result, not only an approximation. Here is my result ( the factorials from 1 to 1.000 ) :

    Code:
    1!=  1
    2!=  2
    3!=  6
    4!=  24
    5!=  120
    6!=  720
    7!=  5040
    8!=  40320
    9!=  362880
    10!=  3628800
    11!=  39916800
    12!=  479001600
    13!=  6227020800
    14!=  87178291200
    15!=  1307674368000
    16!=  20922789888000
    17!=  355687428096000
    18!=  6402373705728000
    19!=  121645100408832000
    20!=  2432902008176640000
    21!=  51090942171709440000
    22!=  1124000727777607680000
    23!=  25852016738884976640000
    24!=  620448401733239439360000
    25!=  15511210043330985984000000
    26!=  403291461126605635584000000
    27!=  10888869450418352160768000000
    28!=  304888344611713860501504000000
    29!=  8841761993739701954543616000000
    30!=  265252859812191058636308480000000
    ...................................................................
    998!=  402790050127220994538240674597601587306681545756471103647447357787726238637266286878923131618587992793273261872069265323955622495490298857759082912582527118115540044131204964883707335062250983503282788739735011132006982444941985587005283378024520811868262149587473961298417598644470253901751728741217850740576532267700213398722681144219777186300562980454804151705133780356968636433830499319610818197341194914502752560687555393768328059805942027406941465687273867068997087966263572003396240643925156715326363340141498803019187935545221092440752778256846166934103235684110346477890399179387387649332483510852680658363147783651821986351375529220618900164975188281042287183543472177292257232652561904125692525097177999332518635447000616452999984030739715318219169707323799647375797687367013258203364129482891089991376819307292252205524626349705261864003453853589870620758596211518646408335184218571196396412300835983314926628732700876798309217005024417595709904449706930796337798861753941902125964936412501007284147114260935633196107341423863071231385166055949914432695939611227990169338248027939843597628903525815803809004448863145157344706452445088044626373001304259830129153477630812429640105937974761667785045203987508259776060285826091261745049275419393680613675366264232715305430889216384611069135662432391043725998805881663054913091981633842006354699525518784828195856033032645477338126512662942408363494651203239333321502114252811411713148843370594801145777575035630312885989779863888320759224882127141544366251503974910100721650673810303577074640154112833393047276025799811224571534249672518380758145683914398263952929391318702517417558325636082722982882372594816582486826728614633199726211273072775131325222240100140952842572490801822994224069971613534603487874996852498623584383106014533830650022411053668508165547838962087111297947300444414551980512439088964301520461155436870989509667681805149977993044444138428582065142787356455528681114392680950815418208072393532616122339434437034424287842119316058881129887474239992336556764337968538036861949918847009763612475872782742568849805927378373244946190707168428807837146267156243185213724364546701100557714520462335084082176431173346929330394071476071813598759588818954312394234331327700224455015871775476100371615031940945098788894828812648426365776746774528000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    999!=  402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    1000!=  402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    
     
  15. pr1nc3k1d

    pr1nc3k1d New Member

    Joined:
    Dec 6, 2007
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Romania
    And Sterling's approximation is : n! ~ e^(-n)*n^n*Sqrt(2*PI*n)
     
  16. asadullah.ansari

    asadullah.ansari TechCake

    Joined:
    Jan 9, 2008
    Messages:
    356
    Likes Received:
    14
    Trophy Points:
    0
    Occupation:
    Developer
    Location:
    NOIDA
    Just i am giving hing hint for Sterling Approximate Formula

    > No Algorithm came uptill now except applying some AI .
     
  17. asadullah.ansari

    asadullah.ansari TechCake

    Joined:
    Jan 9, 2008
    Messages:
    356
    Likes Received:
    14
    Trophy Points:
    0
    Occupation:
    Developer
    Location:
    NOIDA
    For big number, 32-bit or 64-bit machine still not computing after some bit. So on that instant we can easily use sterling aproximation formula
     
  18. pr1nc3k1d

    pr1nc3k1d New Member

    Joined:
    Dec 6, 2007
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Romania
    Oh .. :) it's calculating ... as you can see .. :) but you need to put the result into some data type which can hold this large number. Usually data types can't hold them, you're absolutely right but if you generate the result into a vector or a list you can print it on the screen as you see. The result is correct. Just verify the first numbers of the result with the Calculator from your Windows.

    4.02387260077093773543702433923e+2567 << Here it is your aproximation but I wanted the full result.
     
  19. pr1nc3k1d

    pr1nc3k1d New Member

    Joined:
    Dec 6, 2007
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Romania
    the approximation above was for 1000!
     
  20. asadullah.ansari

    asadullah.ansari TechCake

    Joined:
    Jan 9, 2008
    Messages:
    356
    Likes Received:
    14
    Trophy Points:
    0
    Occupation:
    Developer
    Location:
    NOIDA
    You are right But Too much overhead will be on case of storing into vector or some file i.e. into some container. Too much check has to put where calculation is going overflow.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice