TURBO PASCAL

1. 12. 2.  Рекурсивные функции и процедуры

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

            Схема линейного взаимодействия процедур:                                                       

         Pr_1  - раздел описания Pr_1                     Pr_2 - раздел описания Pr_2       

    Pr_2  - раздел описания Pr_2                          Pr_1    - раздел описания Pr_1    

         Вызов Pr_1 в процедуре Pr_2                                  Вызов Pr_1 в процедуре Pr_2        

        Внешняя программа                                                 Внешняя программа                 

            Схема циклического взаимодействия процедур:              

                     прямая рекурсия                                                                                     косвенная рекурсия

        раздел описания программы                                   Pr_2 - заголовок Pr_2  Forward;   

                                                                                                Pr_1  - раздел описания Pr_1  

                                                                                                Вызов Pr_2 в процедуре Pr_1        

          Pr_1   - раздел описания Pr_1                                         

                                                                                                Pr_2  - раздел описания Pr_2  

          Вызов Pr_1 в процедуре Pr_1                                  Вызов Pr_1 в процедуре Pr_2        

              Внешняя программа                                                    Внешняя программа                 

            Если процедура вызывает сама себя ( прямая рекурсия ),  то она описывается как обычно.  Рекурсия традиционно применяется для итерационного расчета значения функции с использованием результатов предыдущего шага.  Например,  для расчета выражений вида:  X! ( X  факториал ),   X^N ( X в степени N ),  вычисляемых по формулам: X_N= X_N-1 * k,  где k - постоянная или переменная величина.  В общем случае рекурсия применяется при расчете функции от функции: F_N(x) = F_N-1(x).  При этом процесс происходит в два этапа: обратное движение с запоминанием цепочки расчета в оперативной памяти и прямое движение - расчет с использованием полученной цепочки.  Рекурсивные процедуры требуют больше памяти для запоминания промежуточных результатов,  чем обычные циклические операторы,  поэтому рекурсии используются реже.  В случае рекурсивных процедур следует обязательно предусмотреть условие окончания вызова процедуры. 

            Приведем пример традиционного использования рекурсии.  Пусть требуется рассчитать число осколков,  полученных в результате деления тела за "N" миллисекунд,  если каждый осколок делится на два за одну миллисекунду.  Тогда при N=0 число осколков = 1,  при N>0 число осколков = 2^N = 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 N_1: Longint;  i: word;

begin

       N_1:=1;   for i:=1 to N  do   N_1:= 2*N_1;  K_0:= N_1 

end;

Если к каждому осколку добавляется два осколка,  то число осколков = (1+2)^N= 3*3^(N-1).

            Во внешней программе число осколков (переменная "NN") расчитывается вызовом функции:

     NN:= K_O(t);   где t - значение фактического параметра времени.

На первую страницу

(с) Все права защищены.

По всем интересующим вопросам прошу писать электронный адрес