Функции пользователя. Рекурсивные функции

5.2 Функции пользователя. Рекурсивные функции

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

Функция отличается от процедуры только тем, что всегда возвращает в точку вызова одно скалярное значение. При этом функция, как процедура, может содержать параметры-значения или быть без оных. Общая форма записи заголовка функции:

FUNCTION имя (список параметров: тип): тип;

или

FUNCTION имя: тип;

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

Итак, заголовок функции отличается от заголовка процедуры не только сменой слова PROCEDURE на FUNCTION, но и удалением из списка параметров параметра-результата с присвоением его типа имени функции:

PROCEDURE <имя процедуры>(аргументы; VAR параметр-результат: тип);

| |

ѕѕѕѕѕ¬ѕѕѕѕ¬ѕѕѕѕ

FUNCTION <имя функции> (аргументы): тип;

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

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

Известно, что Паскаль имеет набор стандартных функций. Однако этот набор ограничен. Пользователь может по желанию расширить список функций, создав свои функции - функции пользователя. Так, например, в Паскале есть SQR(X) = X2, а вот функции F(X)= Xn, где n принадлежит множеству целых чисел Z, нет. Используя определенное ранее понятие функции, можно создать для этого универсальную функцию, которая давала бы степени произвольного вещественного числа с любым целым показателем.

Определим вещественную функцию POWER, которая должна иметь два параметра-аргумента - для показателя и для основания степени:

function POWER (FACTOR:real;EXPONENT:integer):real;

var COUNT: integer; TFACTOR: real;

begin

¦ if EXPONENT = 0 then POWER:= 1

¦ else begin

¦ ¦ TFACTOR:= FACTOR;

¦ ¦ for COUNT:= 2 to ABS(EXPONENT) do

¦ ¦ TFACTOR:= TFACTOR*FACTOR;

¦ ¦ if EXPONENT<0 then POWER:= 1/TFACTOR

¦ ¦ else POWER:= TFACTOR

¦ end

end;

Теперь можно эту функцию вызывать следующим образом:

а) РI:=POWER(3.14,1);

б) WRITELN("PI=",POWER(3.14,1):5:2);

в) IF X > 2*POWER(6.2,3) THEN WRITE('ДА');

г) A:= POWER(X,2) + POWER(X,3) + POWER(X,4).

К функциям можно обращаться тремя способами: из тела основной программы, из тела другой функции, из тела самой функции, т.е. функция, может вызывать саму себя. Функции называются рекурсивными, если в описании функции происходит вызов самой себя, а процесс обращения - рекурсией. Продемонстрируем использование рекурсии на примере вычисления значения факториала произвольного натурального числа N.

В математике известно рекурсивное определение факториала:

n! = 1, при n = 0;

n! = (n-1)!Чn, при n > 0.

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

function FACTORIAL(VALUE:integer):integer;

begin

iF VALUE=0 then FACTORIAL:=1

else FACTORIAL:= VALUE*FACTORIAL(VALUE-1)

end;

Теперь можно обращаться к этой функции в теле основной программы, как показано в следующем примере:

program FINDFACTORIAL;

var N:integer;

begin

writeln('Введите число');

readln(N);

if N<0 then writeln('Нет факториала')

else writeln('Фактрориал',N,'равен',FACTORIAL(N))

end.

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

FACTORIAL:= VALUE*FACTORIAL(VALUE-1), где происходит вызов определяемой функции. Здесь идентификатор FACTORIAL в левой части оператора обозначает имя переменной для хранения значения функции, а в правой - имя вызываемой функции.

Важным моментом при составлении любой рекурсивной функции является организация выхода из рекурсии. В некоторых простых случаях должно существовать не рекурсивное решение. Рекурсивный процесс должен шаг за шагом так упрощать задачу, чтобы в конце концов для нее появилось не рекурсивное решение. В этих функциях должны проверяться значения аргумента для принятия решения о завершении. В нашем случае условием завершения рекурсии является VALUE=0.

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

Рассмотрим рекурсивный процесс на примере вычисления факториала для N = 3. Получим следующие шаги:

1) N = 3, где N<>0, следовательно, FACTORIAL:=3*FACTORIAL(2);

2) N = 2, где N<>0, следовательно, FACTORIAL:=2*FACTORIAL(1);

3) N = 1, где N<>0, следовательно, FACTORIAL:=1*FACTORIAL(0);

4) N =0, следовательно, FACTORIAL:=1,

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

В выражение 1*FACTORIAL(0) вместо FACTORIAL(0) подставляется его значение 1, вычисляется произведение 1*1 и оно становится значением FACTORIAL(1). В выражение 2*FACTORIAL(1) вместо FACTORIAL(1) подставляется значение 1, вычисляется 2*1 и становится значением FACTORIAL(2). В выражение 3*FACTORIAL(2) вместо FACTORIAL(2) подставляется значение 2, вычисляется 3*2 и становится значением переменной FACTORIAL, которая возвращает в основную программу значение 3!.

Весь этот двухэтапный рекурсивный процесс реализуется в памяти ЭВМ с помощью организации в ней стека рекурсии. Дело в том, что для хранения значений переменной N (а значит, и переменной VALUE) отводится не одна ячейка, а стек с именем N. В этот стек последовательно заносятся значения 3, 2, 1, 0, причем значение 0 есть признак конца заполнения стека. Затем начинает работать цикл с телом FACTORIAL:= FACTORIAL * N, где значения N выбираются последовательно из стека в порядке 1,2,3. Исходным же значением переменной FACTORIAL является 1, как значение 0!.

Работа стека представлена на следующей схеме:

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

Данная функция явно носит рекурсивный характер, исходя из ее определения: Xn = 1, если n = 0;

Xn = (Xn-1)*X, если n > 1.

function POWER(FACTOR:real; EXPONENT:integer): REAL;

begin

if EXPONENT < 0

then POWER:=1/POWER(FACTOR,abs(EXPONENT))

else if EXPONENT > 0

then POWER:= FACTOR*POWER(FACTOR,EXPONENT-1)

ELSE POWER:=1

end;

ЗАМЕЧАНИЕ. Помимо рекурсивных функций в языке Паскаль можно определять по тому же принципу и рекурсивные процедуры. Подробно о них будет сказано в следующих разделах, а пока покажем, как рекурсивная функция может быть переделана в рекурсивную процедуру на примере вычисления факториала:

procedure FACTORIAL(VALUE:integer; var F: integer);

begin

iF VALUE=0 then F:=1

else begin FACTORIAL(VALUE-1,F);

F:=F*VALUE

end;

end;

Здесь уже, в отличие от функции FACTORIAL, для вычисления N! необходимо вызвать эту процедуру с помощью оператора процедуры FACTORIAL(N,FN), где FN - переменная для возвращения из процедуры значения N!.

Похожие работы

Основы программирования на языке Паскаль

Скачать

168304

7

26

... .....-46.780 Program Prim24; Var r1,r2:real; BEGIN r1:=-46.78; r2:=-46.78; writeln('r1=',r1:12:3,' r2=',r2:9:4); writeln('_______________________________'); readln; END. 6. Массивы   6. 1. Описание массивов В языке Паскаль можно обрабатывать не только отдельные переменные, но и их совокупности. Одной из таких совокупностей (структурированных) данных является массив. ...

Алгоритмические языки и программирование Системное программное обеспечение Технология программирования"

Скачать

112819

0

0

... . Объясните, для чего служат разрешения и привилегии в Windows NT. Зав. кафедрой --------------------------------------------------   Экзаменационный билет по предмету СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ Билет № 22 Перечислите возможности и инструменты системы программирования Microsoft Developer Studio. Укажите для чего предназначается буфер в системах ввода-вывода, ...

Основные понятия алгоритмического языка

Скачать

91405

0

0

... с внешнего устройства (из входного файла) в основную память ЭВМ, операция вывода - это пересылка данных из основной памяти на внешнее устройство (в выходной файл). Файлы на внешних устройствах часто называют физическими файлами. Их имена определяются операционной системой. В программах на языке Паскаль имена файлов задаются с помощью строк. Например, имя файла на диске может иметь вид: ...