Факториал числа N записывается как N! (читается N факториал). Значение О!
равно 1. Остальные значения определяются следующим образом:
N! = N * (N - 1) * (N - 2) * ... * 2 * 1
В табл. 5.1 приведены первые 10 значений функции факториала.
Таблица 5.1. Значения функции факториала
Функцию факториала можно определять с помощью рекурсии:
О! = 1
N! = N * (N - 1)!, для N > 0.
Преобразовать это определение в рекурсивную функцию очень просто:
function Factorial(num : Integer) : Integer;
begin
if (num<=0) then
Factorial := 1
else
Factorial := num*Factorial(num-1);
end;
Функция сначала проверяет число на условие N < 0. Для чисел меньше 0 фак-
ториал не определен, но это условие проверяется для подстраховки. Если бы функ-
ция проверила только условие равенства числа нулю, то для отрицательных чисел
рекурсия была бы бесконечной.
Если входное значение меньше или равно 0, функция возвращает значение 1.
В противном случае значение функции равно произведению входного значения на
факториал от входного значения, уменьшенного на единицу.
Существуют два фактора, которые гарантируют, что эта рекурсивная функция
в конце концов остановится. Во-первых, при каждом последующем вызове значе-
ние параметра num уменьшается на единицу. Во-вторых, значение num ограничено
нулем. Когда значение доститет 0, функция заканчивает рекурсию. Такое усло-
вие, как num < 0, которое останавливает рекурсию, называется основным условием
или условием остановки (base Ease или stopping case).
При каждом вызове подпрограммы система сохраняет некоторые значения
в стеке, как описывалось в главе 3. Поскольку этот стек имеет очень важное значе-
ние, иногда его называют просто стеком. Если рекурсивная процедура вызывает-
ся много раз, она может заполнить весь стек и вызвать ошибку переполнения сте-
ка (Out of stack space).
Количество вызовов рекурсивной функции зависит от объема памяти компь-
ютера и количества данных, которые программа помещает в стек. В Delphi под-
программа обычно может вызывываться много раз перед тем, как возникнет ошибка
переполнения стека. В одном тестов программа исчерпала стековое простран-
ство только после 2356 рекурсивных вызовов. |
Главная
Каталог файлов
