Здесь очередной член числовой последовательности вычисляется по его номеру и значениям предыдущих членов этой последовательности.
Например, для вычисления ряда Фибоначчи используется рекуррентное отношение
.
Наиболее часто рекуррентное отношение имеет вид
.
Рекурсивную функцию можно считать обобщением понятия рекурсивного отношения. В такой функции вычисление заданного значения производится с помощью этой же функции ("рекурсия" означает "возвращение"):
.
Классическим примером рекурсивной функции является факториал
.
Рекурсивный способ записи факториала:
Паскаль-программа допускает рекурсивное описание функций. В этом случае в теле такой подпрограммы-функции содержится обращение к этой же функции.
Пример 1. Для факториала имеем:
FunctionFact(n:word):word;
Begin
If n=0 then
Fact:=1
Else
Fact:=n*Fact(n-1);
End { Fact };
В процессе выполнения рекурсивной функции ее параметры-значения складываются в стек. Происходит развертывание, а затем свертывание рекурсивных вызовов.
Пусть мы имеем y = 5! , т.е. y := Fact(5). Схема вычислительных действий:
Fact(5) = 5 * Fact(4) 5 * 24 = 120
½ Fact(4) = 4 * Fact(3) 4 * 6 = 24
½ Fact(3) = 3 * Fact(2) ½ 3 * 2 = 6
½ Fact(2) = 2 * Fact(1) ½ 2 * 1 = 2
¯ Fact(1) = 1 * Fact(0) ½ 1 * 1 = 1
Fact(0) = 1 1
Любое рекурсивное определение функции можно заменить нерекурсивным.
Пример для факториала:
Function Fact(n:word):word;
Var i,k : word;
Begin
k:=1;
For i:=1 to n do
k:=k*i;
Fact:=k;
End{ Fact };
Рекурсивность - это не свойство самой функции, а способ ее описания. Рекурсивное определение короче и нагляднее, но требует в процессе своего выполнения больше времени и памяти.
Пример 2. Алгоритм Евклида.
Function Evklid(m,n:word):word;
Vard : word;
Begin
If n>m then
d:=Evklid(n,m)
Else
If n=0 then
d:=m
Else
d:=Evklid(n, m mod n);
Evklid:=d;
End { Evklid };
Пример 3. Вычисление чисел Фибоначчи.
Function Fib(n:word):word;
Begin
If n=0 then
Fib:=0
Else
If n<=2 then
Fib:=1
Else
Fib:=Fib(n-1)+Fib(n-2);
End { Fib };
Пример 4.
Степенную функцию, рассмотренную в разделе "Вычисление степенной функции", также можно реализовать как рекурсивную.
FunctionPower(x:real; n:word):real;
Begin
Ifn=0 then
Power:=1
Else
If not odd(n) then
Power:=Power(x*x,n div 2)
Else
Power:=x*Power(x,n-1);
End{ Power };
При написании обычных функций необходимо следить, чтобы они случайно не оказались рекурсивными. Особенно опасны в этом отношении функции без параметров.
Пример 5. Предположим, что в программе для одного и того же массива несколько раз вычисляется среднее арифметическое значение его элементов. Тогда такое вычисление можно оформить в виде функции без параметров.
ConstNmax = 400;
TypeAr = array[1..Nmax] of real;
Var n : word;
X : Ar;
Function MidAr;
Var i : word;
Begin
MidAr:=0;
For i:=1 to n do
MidAr:=MidAr+x[i];
MidAr:=MidAr/n;
End{ MidAr };
Здесь имя MidAr в правой части оператора присваивания воспринимается как обращение к функции MidAr. Это приводит к бесконечному рекурсивному вызову функции, следствием чего является прерывание программы с сообщением " 202 Stack overflow error" (переполнение стека), поскольку рекурсивный стек, как и локальные переменные, размещается в сегменте стека.
Чтобы исключить ошибочную рекурсивность функции, рекомендуется присваивать выходное значение имени функции лишь на заключительном этапе ее работы. Для функции MidAr получим:
FunctionMidAr;
Var i : word;
S : real;
Begin
S:=0;
Fori:=1 to n do
S:=S+x[i];
S:=S/n;
MidAr:=S;
End{ MidAr };
В приведенных выше примерах имеет место прямая рекурсия, т.е. обращение к функции содержится в теле самой функции. Может быть также косвенная рекурсия, связывающая две подпрограммы-функции:
Наряду с рекурсивными функциями могут быть и рекурсивные процедуры. В частности, каждую из вышеприведенных функций Fact, Evklid, Fib можно оформить в виде процедуры, перенеся выходное значение в список формальных параметров.
При прямой рекурсии нет нарушения основного принципа Паскаль-программы: любое имя может быть использовано лишь после его описания. При косвенной рекурсии такое нарушение имеет место.
Пусть две процедуры взаимно рекурсивны, т.е. первая вызывает вторую и, в свою очередь, вызывается второй при возврате. Схему их взаимодействия можно было бы представить, например, таким образом:
ProcedureProc1(a,b:real);
Var k,l : integer;
Begin
..........
Proc2(k,l);
..........
End { Proc1 };
Procedure Proc2(Var m:integer; n:integer);
Var p,q : real;
Begin
..............
Proc1(p,q);
.............
End { Proc2 };
Во время трансляции процедуры Proc1 транслятор не может определить, что собой представляет имя Proc2, так как это имя еще не было описано в программе. В этом случае трансляция прерывается и на экран выдается сообщение "Error 3: Unknown identifier" (Неизвестный идентификатор). Тот же результат будет, если переставить местами описания процедур Proc1 и Proc2 (но теперь неизвестным идентификатором считается Proc1).
При трансляции обращения к процедуре компилятору не требуется иметь в своем распоряжении тело этой процедуры. Для выполнения указанной работы достаточно знать заголовок процедуры, содержащий полную информацию о количестве и типах формальных параметров. В связи с этим в Паскаль-программе принята следующая схема записи взаимно рекурсивных процедур.
Одна из процедур, например Proc1, записывается обычным способом. Описание второй процедуры разделяется на две части: опережающее и определяющее. В опережающее описание, которое ставится перед процедурой Proc1, включается заголовок процедуры Proc2 и директива forward, которая указывает транслятору, что тело процедуры Proc2 будет записано позже. Определяющее описание, которое ставится после описания процедуры Proc1, - это имя процедуры и ее блок. Для приведенного выше примера будем иметь:
Procedure Proc2(Var m:integer; n:integer);
forward;
Procedure Proc1(a,b:real);
Vark,l : integer;
Begin
..........
Proc2(k,l);
..........
End{ Proc1 };
ProcedureProc2;
Var p,q : real;
Begin
..............
Proc1(p,q);
..............
End{ Proc2 };
Из примера видно, что в определяющем описании заголовок процедуры записывается без списка формальных параметров, поскольку информация, содержащаяся в этом списке, уже не нужна транслятору.
.
числовой последовательности вычисляется по его номеру 
и значениям предыдущих членов 
этой последовательности.
.
.
.
.
несколько раз вычисляется среднее арифметическое значение 
его элементов. Тогда такое вычисление можно оформить в виде функции без параметров.