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

Язык Си в примерах

---

1. Компиляция программ
2. Простейшая программа «Hello World»
3. Учимся складывать
4. Максимум
5. Таблица умножения
6. ASCII-коды символов
7. Верхний регистр
8. Скобочки
9. Факториал
10. Степень числа
11. Треугольник Паскаля
12. Корень уравнения
13. Система счисления
14. Сортировка
15. Библиотека complex
16. Сортировка на основе qsort
17. RPN-калькулятор
18. RPN-калькулятор на Bison
19. Простая грамматика
20. Задача «Расчёт сопротивления схемы»
21. Простая реализация конечного автомата
22. Использование аргументов командной строки
23. Чтение и печать без использования stdio
24. Декодирование звукозаписи в формате ADX
25. Другие примеры
26. XCC C

Факториалом числа 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));
    }
}

Это определение основано на следующей рекуррентной формуле:

$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 <stdio.h>

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

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

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

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

#include <stdio.h>

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

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

Задания

1. Улучшите программы, добавив к ним диагностику ошибки во входных данных: если n < 0, то программа должна ясно сообщать о неопределенности факториала для отрицательных чисел.
2. Опытным путем определите максимальные значения аргумента и результата для программ выше. Исследуйте влияние на эти значения замены используемого в программах числового типа int на short, long и long long. Обратите внимание, что при этом также потребуется соответственно изменить строку формата (первый аргумент) функции printf.
3. После выполнения первых двух заданий Вы поймете, что максимальной натуральной число по которому возможно вычислить факториал с использованием 4-х байтовых беззнаковых чисел это 12 (всего навсего). Настоящий программист не будет использовать рекурсии и умножать в цикле, а использует предвычисленный статический массив готовых данных. Попробуйте и сравните быстродействие.

См. также

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