| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Want to get organized in 2022? Let Dokkio put your cloud files (Drive, Dropbox, and Slack and Gmail attachments) and documents (Google Docs, Sheets, and Notion) in order. Try Dokkio (from the makers of PBworks) for free. Available on the web, Mac, and Windows.

View
 

Factorial

Page history last edited by Kenneth Finnegan 13 years, 9 months ago

Calculating factorials is one of the most classic examples used in teaching recursion.  The code to do so is quite simple:

int factorial(int i) {

     if(i)

          return i * factorial(i-1);

     return 1;

}

 

The realistic problem with this is that factorials get really big, really fast.  Only 13! is so large that it overflows a 32 bit int.  Unless you're dealing with 64 bit numbers, it makes more sense to use a lookup table.  The work just isn't worth it.

 

Code:

int factorial(int i) {

     if (i<0 || i>12) {

          fprintf(stderr, "Factorial input out of range\n");

          exit(EXIT_FAILURE); // You could also return an error code like -1

     }

     static const int factorials[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600};

     return factorials[i];

 


Extensions:

If you need larger factorials, use a 64 bit number (long long or int64_t).  You could still use a lookup table for improved performance.

 


Sources:

I can't remember where I read this trick.

Comments (0)

You don't have permission to comment on this page.