Вычисление факториала.

Факториал числа n! определяет количество способов размещения n предметов в некотором ряду. Так, при n=3 имеется три способа для размещения первого предмета. Если он уже зафиксирован, то существует два способа установки второго предмета и один для третьего. Таким образом, 3!=3*2*1=6. Приведем таблицу для нескольких первых значений факториала:

4!=24

5!=120

6!=720

7!=5040

8!=40320

Характерной особенностью этой величины является ее экспоненциальное возрастание. При больших значениях n справедлива следующая оценка Стирлинга:

.

Некоторые важные свойства факториала можно найти в справочной литературе, а мы подробнее остановимся на рекурсивном алгоритме его вычисления. Запишем факториал в виде

n! = n (n-1)! (1)

В такой записи задача вычисления факториала сводится к ней самой же, путем изменения исходных данных, т.е. «новое» значение n! выражено через «старое» (n-1)!. Кроме того, условие 0! =1 позволяет завершить вычислительный процесс. Составим рекурсивную функцию:

function Factorial(n:integer):real;

begin

if n=0

then Factorial:=1

else Factorial:=n* Factorial(n-1)

end;

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

function Factorial(n:integer):real;

var i, y:longint;

begin

y:=1;

if n=0

then Factorial:=1

else begin

for i:=2 to n do y:=y*i;

Factorial:=y

end

end;

Как правило, программы, записанные в виде рекурсивных процедур и функций, отличаются простотой и компактностью записи текста. Рекурсия – мощный инструмент в руках программиста. Однако им необходимо умело пользоваться, знать его сильные и слабые стороны.

Принцип работы рекурсивных подпрограмм подобен работе стека. Прямой ход рекурсии – операция засылки информации в стек (операция Push): Обратный ход рекурсии – последовательное извлечение данных из стека (операция Pop):

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

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

Поэкспериментируйте с подпрограммами вычисления факториала.

Дата добавления: 2015-07-26