Стандартные функции

End.

Begin

Begin

Begin

Begin

Begin

f:=1;

For i:=1 to n do f:=f*i;

Factorial:=f

End;

Для простоты здесь не включен контроль отрицательных чисел и переполнения разрядной сетки при больших значениях n.

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

Вычисление факториала по рекурсивному алгоритму определяется так:

n! = n ´ (n – 1)!

Иными словами, чтобы вычислить n!, нужно факториал от n – 1 умножить на n.

Вычислим рекурсивно 4!

4! = 4 ´ (4-1)! = 4 ´ 3!

3! = 3 ´ (3-1)!= 3 ´ 2!

2! = 2 ´ (2-1)! = 2 ´ 1!

По определению факториала, 1! = 1. Так что, построив рекурсивную цепочку, мы можем вычислить искомое значение. Соответствующая функция на Паскале может выглядеть таким образом:

Function Factorial(n:Integer):Integer;

Var f:Integer;

If n<=1 then f:=1

else f:=Factorial(n-1); {рекурсивный вызов}

Factorial:=f

End;

Циклов в этой функции нет, зато есть рекурсивный вызов. Функция вызывает сама себя, если значение параметра больше 1 (но значение параметра при каждом рекурсивном вызове уменьшается на единицу).

Встречаются алгоритмы, которые реализуются в виде процедур и функций, взаимно вызывающих друг друга. Такие алгоритмы называют взаимно-рекурсивными.

При описании двух и более взаимно-рекурсивных процедур и функций возникает трудность, состоящая в том, что согласно правилам видимости имен, любой программный элемент может быть доступен по имени только после того, как он описан. Если есть две взаимно-рекурсивных процедуры А и В, и процедура А описана раньше, чем процедура В, то вызов процедуры В изнутри процедуры А будет предшествовать описанию процедуры В. Если сначала описать процедуру В, а затем А, то вызов процедуры А изнутри процедуры В также будет предшествовать описанию процедуры А. Для преодоления этой трудности в Паскале предусмотрено опережающее описание процедур и функций. Такое описание состоит из заголовка процедуры или функции, за которым следует слово Forward.

опережающее описание::= (<заголовок функции> | <заголовок процедуры>) ";" "Forward".

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

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

Program Reciprocal;

Var i,j: Integer; R:Real;

Procedure A(S:Real;Var i,j:Integer);Forward;

Function B(T:Real):Real;

Var N,M:Integer;

..... {пропускаем фрагмент программы}

A(T,N,M);

..... {пропускаем фрагмент программы}

End;

Procedure A; {формальные параметры описаны ранее, поэтому здесь они не повторяются}

Var E:Real;

..... {пропускаем фрагмент программы}

S:=B(E);

..... {пропускаем фрагмент программы}

End;

..... {пропускаем фрагмент программы}

A(R,i,j);

..... {пропускаем фрагмент программы}

Стандартные функции и стандартные процедуры, рассматриваемые далее, встроены в систему программирования. Их не нужно описывать перед использованием, они предоставлены в готовом виде. Поэтому их также называют предопределенными.

Дата добавления: 2014-01-11