Рекурсивные функции и процедуры
Если одна процедура (Pr2) вызывает в своем разделе выполнения другую (Pr1), то вызываемая процедура должна быть описана во внешней программе перед описанием вызывающей процедуры, либо внутри вызывающей процедуры. Возможны и циклические случаи: если процедура вызывает сама себя — прямая рекурсия, если обе процедуры вызывают в своих разделах выполнения друг друга — косвенная рекурсия. Приведем… Читать ещё >
Рекурсивные функции и процедуры (реферат, курсовая, диплом, контрольная)
Если одна процедура (Pr2) вызывает в своем разделе выполнения другую (Pr1), то вызываемая процедура должна быть описана во внешней программе перед описанием вызывающей процедуры, либо внутри вызывающей процедуры. Возможны и циклические случаи: если процедура вызывает сама себя — прямая рекурсия, если обе процедуры вызывают в своих разделах выполнения друг друга — косвенная рекурсия.
Если процедура вызывает сама себя (прямая рекурсия), то она описывается как обычно. Рекурсия традиционно применяется для итерационного расчета значения функции с использованием результатов предыдущего шага. Например, для расчета выражений вида: X! (X факториал), XN (X в степени N), вычисляемых по формулам: XN= XN-1 * k, где k — постоянная или переменная величина. В общем случае рекурсия применяется при расчете функции от функции: FN(x) = FN-1(x). При этом процесс происходит в два этапа: обратное движение с запоминанием цепочки расчета в оперативной памяти и прямое движение — расчет с использованием полученной цепочки. Рекурсивные процедуры требуют больше памяти для запоминания промежуточных результатов, чем обычные циклические операторы, поэтому рекурсии используются реже. В случае рекурсивных процедур следует обязательно предусмотреть условие окончания вызова процедуры.
Приведем пример традиционного использования рекурсии. Пусть требуется рассчитать число осколков, полученных в результате деления тела за «N» миллисекунд, если каждый осколок делится на два за одну миллисекунду. Тогда при N=0 число осколков = 1, при N>0 число осколков = 2N = 2*2(N-1).
Функция, возвращающая число осколков, будет иметь вид:
Function K_O (N: word): Longint;
begin.
if N=0 then K_O:=1 {условие окончания рекурсии}.
else K_O:=2*K_O (N-1) {рекурсивный вызов}.
end;
Пример функции, возвращающей число осколков, без использования рекурсии:
Function K_O (N: word): Longint;
var N1: Longint; i: word;
begin.
N1:=1; for i:=1 to N do N1:= 2*N1; K0:= N1.
end;
Если к каждому осколку добавляется два осколка, то число осколков = (1+2)N= 3*3(N-1).
Во внешней программе число осколков (переменная «NN») расчитывается вызовом функции:
NN:= K_O (t);
где t — значение фактического параметра времени.