How would you write a non-recursive algorithm to calculate factorials?

Question

How would you write a non-recursive algorithm to compute n!.

Answer 1

Rewrite the recursive solution as a loop.

Answer 2

public double factorial(int n) {
    double result = 1;
    for(double i = 2; i<=n; ++i) {
        result *= i;
    }
    return result;
}

Answer 3

long fact(int n) {
    long x = 1;
    for(int i = 1; i <= n; i++) {
        x *= i;
    }
    return x;
}

Answer 4

int fact(int n){
    int r = 1;
    for(int i = 1; i <= n; i++) r *= i;
    return r;
}

Answer 5

Pseudo code

total = 1
For i = 1 To n
    total *= i
Next

Answer 6

fac = 1 ; 
for( i = 1 ; i <= n ; i++){
   fac = fac * i ;
}

Answer 7

int total = 1
loop while n > 1
    total = total * n
    n--
end while

Answer 8

in pseudocode

ans = 1
for i = n down to 2
  ans = ans * i
next

Answer 9

public int factorialNonRecurse(int n) {
    int product = 1;

    for (int i = 2; i <= n; i++) {
        product *= i;
    }

    return product;
}

Answer 10

Unless you have arbitrary-length integers like in Python, I would store the precomputed values of factorial() in an array of about 20 longs, and use the argument n as the index. The rate of growth of n! is rather high, and computing 20! or 21! you'll get an overflow anyway, even on 64-bit machines.

Answer 11

Since an Int32 is going to overflow on anything bigger than 12! anyway, just do:

public int factorial(int n) {
  int[] fact = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 
                362880, 3628800, 39916800, 479001600};
  return fact[n];
}

Answer 12

assuming you wanted to be able to deal with some really huge numbers, I would code it as follows. This implementation would be for if you wanted a decent amount of speed for common cases (low numbers), but wanted to be able to handle some super hefty calculations. I would consider this the most complete answer in theory. In practice I doubt you would need to compute such large factorials for anything other than a homework problem

#define int MAX_PRECALCFACTORIAL = 13;

public double factorial(int n) {
  ASSERT(n>0);
  int[MAX_PRECALCFACTORIAL] fact = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 
                362880, 3628800, 39916800, 479001600};
  if(n < MAX_PRECALCFACTORIAL)
    return (double)fact[n];

  //else we are at least n big
  double total = (float)fact[MAX_PRECALCFACTORIAL-1]
  for(int i = MAX_PRECALCFACTORIAL; i <= n; i++)
  {
    total *= (double)i;  //cost of incrimenting a double often equal or more than casting
  }
  return total;

}

Answer 13

Here's the precomputed function, except actually correct. As been said, 13! overflows, so there is no point in calculating such a small range of values. 64 bit is larger, but I would expect the range to still be rather reasonable.

int factorial(int i) {
    static int factorials[] = {1, 1, 2, 6, 24, 120, 720, 
            5040, 40320, 362880, 3628800, 39916800, 479001600};
    if (i<0 || i>12) {
        fprintf(stderr, "Factorial input out of range\n");
        exit(EXIT_FAILURE); // You could also return an error code here
    }
    return factorials[i];
}

Source: http://ctips.pbwiki.com/Factorial

Answer 14

In the interests of science I ran some profiling on various implementations of algorithms to compute factorials. I created iterative, look up table, and recursive implementations of each in C# and C++. I limited the maximum input value to 12 or less, since 13! is greater than 2^32 (the maximum value capable of being held in a 32-bit int). Then, I ran each function 10 million times, cycling through the possible input values (i.e. incrementing i from 0 to 10 million, using i modulo 13 as the input parameter).

Here are the relative run-times for different implementations normalized to the iterative C++ figures:

            C++    C#
---------------------
Iterative   1.0   1.6
Lookup      .28   1.1
Recursive   2.4   2.6

And, for completeness, here are the relative run-times for implementations using 64-bit integers and allowing input values up to 20:

            C++    C#
---------------------
Iterative   1.0   2.9
Lookup      .16   .53
Recursive   1.9   3.9

Answer 15

I would use memoization. That way you can write the method as a recursive call, and still get most of the benefits of a linear implementation.

Answer 16

long fact(int n) { long fact=1; while(n>1) fact*=n--; return fact; }

long fact(int n) { for(long fact=1;n>1;n--) fact*=n; return fact; }

Answer 17

At run time this is non-recursive. At compile time it is recursive. Run-time performance should be O(1).

//Note: many compilers have an upper limit on the number of recursive templates allowed.

template struct Factorial { enum { value = N * Factorial::value }; };

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

// Factorial<4>::value == 24 // Factorial<0>::value == 1 void foo() { int x = Factorial<4>::value; // == 24 int y = Factorial<0>::value; // == 1 }

Answer 18

I love the pythonic solution to this:

def fact(n): return (reduce(lambda x, y: x * y, xrange(1, n+1)))