Язык Си в примерах/Факториал

Факториалом числа n называют произведение первых n натуральных чисел:

n!=1\cdot 2\cdot \ldots \cdot n=\prod _{i=1}^{n}i.

Ниже мы рассмотрим примеры программ, содержащих вычисляющую факториал заданного числа функцию factorial.

Реализация рекуррентной формулы

#include <stdio.h>

static int
factorial (int n)
{
  return (n < 2) ? 1 : n * factorial (n - 1);
}

int
main (void)
{
  int n;
  while (scanf ("%d", &n) == 1) {
    printf ("%d\n", factorial (n));
  }
  return 0;
}

Определение функции factorial выше основано на следующей рекуррентной формуле:

n!=n\cdot (n-1)!,\quad 0!=1.

Для вычисления факториала n! эта функция вызывает саму себя с аргументом n − 1.

Тернарный оператор (? :) в выражении (n < 2) ? 1 : n * factorial (n - 1) для возвращаемого значения (return) «обрывает» рекурсию, когда аргумент функции становится меньшим 2. В противном случае, функция factorial постоянно бы вызывала саму себя, и во время выполнения программы мы получили бы сообщение об ошибке «переполнение стека» или «превышена глубина рекурсии». Для того, чтобы этого не было, необходимо, чтобы при некоторых значения аргумента, функция не вызывала саму себя, а вычисляла свое значение «самостоятельно».

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

Использование хвостовой рекурсии

Возможность рекурсии ограничена предельной глубиной стека возврата. В некоторых случаях, однако, реализация языка программирования может самостоятельно свести рекурсию к итерации.

В примере ниже, мы воспользуемся хвостовой рекурсией, сведение которой к итерации хотя и не требуется стандартом, но все же реализуется, например, компилятором C, входящим в распространенный комплект GCC. Для этого, нам потребуется определить вспомогательную функцию factorial_1, вычисляющую значение p n!, где p, n — аргументы функции.

Обратите внимание, что в этом примере мы не приводим ни определения функции main, ни директив препроцессора #include подключения используемых нами заголовков — их следует заимствовать из предыдущего примера.

static int
factorial_1 (int n, int p)
{
  return (n < 2) ? p : factorial_1 (n - 1, p * n);
}

static int
factorial (int n)
{
  return factorial_1 (n, 1);
}

Явно итеративный вариант

Наконец, в варианте ниже мы вовсе исключим рекурсию из определения функции factorial, явно сведя ее к итерации.

static int
factorial (int n)
{
  int r;
  for (r = 1; n > 1; r *= (n--))
    ;
  return r;
}

В отличие от первого варианта (но аналогично варианту с хвостовой рекурсией) в данном примере нам потребовалась дополнительная локальная переменная. В случае «нехвостовой» рекурсии — роль такой переменной фактически играет растущий стек возврата. Отметим, впрочем, что в данной конкретной задаче это не столь важно.

Вариант «произвольный»

Стандарт требует поддержки реализацией числовых типов разрядности 8, 16, 32 и 64 бит.^[1] Несложно убедиться, однако, что уже 21! = 51 090 942 171 709 440 000 — что превышает предельные значения для 64-битового числа — как со знаком (9 223 372 036 854 775 807), так и без знака (18 446 744 073 709 551 615).

Если по каким-либо причинам требуется вычислить точные значения факториала для чисел от 21 и выше, следует использовать библиотеки операций с числами произвольной разрядности — как, например, GNU MP.^[2]

#include <stdio.h>
#include <gmp.h>

static void
factorial (long n, mpz_t r)
{ 
  mpz_init_set_si (r, 1);
  for (; n > 1; n--) {
    mpz_mul_si (r, r, n);
  }
}

int
main (void)
{
  int n;
  mpz_t r;
  while (scanf ("%d", &n) == 1) {
    factorial (n, r);
    gmp_printf ("%Zd\n", r);
  }
  return 0;
}

Задания

Улучшите программы, добавив к ним диагностику ошибки во входных данных: если n < 0, то программа должна ясно сообщать о неопределенности факториала для отрицательных чисел.
Опытным путем определите максимальные значения аргумента и результата для «стандартных» программ выше. Исследуйте влияние на эти значения замены используемого в программах числового типа int на short, long и long long. Обратите внимание, что при этом также потребуется соответственно изменить строку формата (первый аргумент) функции printf.
Определите также максимальные значения аргумента и результата для этих программ при использовании чисел с плавающей запятой — числовых типов double, float, long double.

См. также

Реализации алгоритмов/Факториал (на различных языках)

Примечания

↑ 7.20.1.2 Minimum-width integer types(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.
↑ The GNU MP Bignum Library(англ.) Проверено 2015-04-04 г.

[int-least-1] 7.20.1.2 Minimum-width integer types(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.

[gmp-2] The GNU MP Bignum Library(англ.) Проверено 2015-04-04 г.

[1]

[2]