Рекурсивные функции

Функции пользователя

 

Известно, что Паскаль имеет набор стандартных функций. Однако этот набор ограничен. Пользователь может по желанию расширить список функций, создав свои функции - функции пользователя. Так, например, в Паскале есть 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;

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

a) F:=POWER(5.25, 3);

b) WRITELN("D = ",POWER(5.25,-2):5:2);

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

d) 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!.

В заключение покажем, что часто рекурсивные функции строятся гораздо проще, чем "обычные", хотя вполне понятно, что не всякая функция может быть переделана на рекурсивную. Сделаем это на примере уже построенной ранее функции 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!.