Как Вы записали бы нерекурсивный алгоритм для вычисления факториалов?

Так как Int32 собирается переполниться на чем-либо большем, чем 12! так или иначе просто сделайте:

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

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

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;
}

Я использовал бы memoization. Тем путем можно записать метод как рекурсивный вызов, и все еще извлечь большую часть пользы из линейной реализации.

принятие Вас хотело быть в состоянии иметь дело с некоторыми действительно огромными числами, я кодирую его следующим образом. Эта реализация была бы для того, если бы Вы хотели достойное количество скорости для общих падежей (небольшие числа), но хотели быть в состоянии обработать некоторые супер значительные вычисления. Я считал бы это самым полным ответом в теории. На практике я сомневаюсь, что необходимо было бы вычислить такие большие факториалы для чего-либо кроме проблемы домашней работы

#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;

}

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

Во время выполнения это нерекурсивно. Во время компиляции это рекурсивно. Производительность во время выполнения должна быть O (1).

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

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::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
}

Псевдо код

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

Я люблю pythonic решение этого:

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

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

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

Вот предварительно вычисленная функция, кроме на самом деле корректного. Как сказано, 13! переполнение, таким образом, нет никакого смысла в вычислении такого маленького диапазона значений. 64 бита больше, но я ожидал бы, что диапазон все еще будет довольно разумен.

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];
} 

Источник: http://ctips.pbwiki.com/Factorial

Перепишите рекурсивное решение как цикл.

Если у Вас нет целых чисел произвольной длины как в Python, я сохранил бы предварительно вычисленные значения факториала () в массиве приблизительно 20 longs и использовал бы аргумент n в качестве индекса. Темп роста n! довольно высоко, и вычисление 20! или 21! Вы получите переполнение так или иначе, даже на 64-разрядных машинах.

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

В интересах науки я выполнил некоторое профилирование на различных реализациях алгоритмов для вычисления факториалов. Я создал повторяющийся, ищите таблицу и рекурсивные реализации каждого в C# и C++. Я ограничил максимальное входное значение 12 или меньше, с тех пор 13! больше, чем 2^32 (максимальное значение, способное к тому, чтобы быть сохраненным в 32-разрядном интервале). Затем я выполнил каждую функцию 10 миллионов раз, циклически повторяющихся через возможные входные значения (т.е. увеличивающих i от 0 до 10 миллионов, с помощью i 13 по модулю в качестве входного параметра).

Вот относительное время выполнения для различных реализаций, нормализованных повторяющимся числам C++:

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

И, для полноты, вот относительное время выполнения для реализаций с помощью 64-разрядных целых чисел и позволяя входные значения до 20:

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

в псевдокоде

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

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

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

    return product;
}