19

Possible Duplicates:
Calculating large factorials in C++
Howto compute the factorial of x

How do you implement the factorial function in C++? And by this I mean properly implement it using whatever argument checking and error handling logic is appropriate for a general purpose math library in C++.

Community
  • 1
  • 1
Jonathan Allen
  • 68,373
  • 70
  • 259
  • 447
  • more similar questions: http://stackoverflow.com/questions/4349505/trying-to-implement-power-and-factorial-functions-recursively-c http://stackoverflow.com/questions/4977715/calculating-and-printing-factorial-at-compile-time-in-c http://stackoverflow.com/questions/1966077/calculate-the-factorial-of-an-arbitrarily-large-number-showing-all-the-digits –  Apr 19 '11 at 19:48
  • 2
    Your profile shows that you're a C# programmer; I doubt the C++ design would be that different. – chrisaycock Apr 19 '11 at 19:48
  • 1
    Strangely, none of the suggested duplicates looks to me like it's really an exact duplicate of this one. One is asking about using big nums, another using template metaprogramming, and one specifically about a recursive implementation. None of them is just the basic question of how to implement factorial. – Jerry Coffin Apr 19 '11 at 19:53
  • @Jerry: If you can calculate the factorial of a large number, then the rest will fall into place. http://stackoverflow.com/questions/1966077/calculate-the-factorial-of-an-arbitrarily-large-number-showing-all-the-digits –  Apr 19 '11 at 20:16
  • @0A0D: while true, it looked to me like those questions really came down to "how do I write and/or where do I find bignum code?", and factorial was almost incidental -- it's just a function that happens to produce large integers. – Jerry Coffin Apr 19 '11 at 20:24
  • @Jerry: here's another one: http://stackoverflow.com/questions/3786207/howto-compute-the-factorial-of-x –  Apr 19 '11 at 20:24
  • @0A0D: Now, that one I'll buy as being an exact duplicate (and have voted to close accordingly). – Jerry Coffin Apr 19 '11 at 20:26
  • 1
    None of those are exact duplicates because they all ignore my main question about error handling. – Jonathan Allen Apr 21 '11 at 23:40

3 Answers3

38

Recursive:

unsigned int factorial(unsigned int n) 
{
    if (n == 0)
       return 1;
    return n * factorial(n - 1);
}

Iterative:

unsigned int iter_factorial(unsigned int n)
{
    unsigned int ret = 1;
    for(unsigned int i = 1; i <= n; ++i)
        ret *= i;
    return ret;
}

Compile time:

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

void foo()
{
    int x = Factorial<4>::value; // == 24
    int y = Factorial<0>::value; // == 1
}
Hovhannes Grigoryan
  • 1,151
  • 1
  • 8
  • 11
26

Besides the obvious loops and recursions, modern C++ compilers support the gamma function as tgamma(), closely related to factorial:

#include <iostream>
#include <cmath>
int main()
{
    int n;
    std::cin >> n;
    std::cout << std::tgamma(n+1) << '\n';
}

test run: https://ideone.com/TiUQ3

Cubbi
  • 46,567
  • 13
  • 103
  • 169
  • That is useless in teaching how to do error handling in this kind of function. – Jonathan Allen Apr 21 '11 at 23:41
  • 4
    @Jonathan Allen: What kind of "error handling"? If you were asking how to restrict the acceptable arguments to permit only the unsigned integers for which the result is exactly representable as a value of a given type, then the answer would be an implementation of `boost::math::factorial`. – Cubbi Apr 22 '11 at 13:14
  • @Cubbi I believe http://ideone.com wrecked your code. – Jonathan Mee Jan 18 '16 at 12:17
  • @Cubbi So I have no right to ask this, but we're discussing one of your http://en.cppreference.com edits, and I thought you might be willing to come clarify for us: http://stackoverflow.com/q/38402133/2642059 – Jonathan Mee Jul 15 '16 at 22:21
0

You might want to take a look at boost/math/special_functions/factorials.hpp if you have Boost installed. You can read about it at: Boost Factorial

yasouser
  • 5,113
  • 2
  • 27
  • 41