Рекурсия.
    С понятием рекурсии мы уже встречались: рекуррентные соотношения довольно часто встречаются в математических выражениях. Рекурсия в определении состоит в том, что определяемое понятие определяется через само это понятие. Примером здесь может служить определение высказывания (см. лекция 5, определение 5.1). Рекурсия в вычислениях выступает в форме рекуррентных соотношений, которые показывают, как вычислить очередное значение, используя предыдущие.
     Например, рекуррентное соотношение
    xi=xi-2+xi-1 , где x1=1 , x2=2
    задает правило вычисления так называемых чисел Фибоначчи.
     Другим примером рекуррентных соотношений могут служить правила вычисления членов арифметической прогрессии
    an+1=an+d , где d - разность прогрессии,
    либо геометрической прогрессии
    an+1=q an , где q - коэффициент прогрессии.
    Эта идея рекурсии реализована и в языке Pascal.
    Определение 16.1. Функция (процедура) на языке Pascal называется рекурсивной, если в ходе своего выполнения она обращается к самой себе.
    Например, мы можем определить вычисление функции n! рекурсивно. Как это сделать, показано на рисунке 16.1
    
    function Factorial (n : integer) : integer ;
    begin if n>0 then Factorial:=Factorial (n-1)?n
    else if n=0 then Factorial:=1
    else writeln ('значение n меньше 0')
    end {Factorial}
    Рис. 16.1. Функция вычисления n! в рекурсивной форме.
    
    Рассмотрим подробно, как будет выполняться обращение к этой функции, напрмер, при n=4.
    На рисунке 16.2 показан процесс вычисления для случая Factorial(4).
    
    
    
    
    
    
    
    
    
    Рис. 16.2. Вычисление функции Factorial(n) для n=4.
    Сначала образуется так называемый рекурсивный фрейм №1 при n=4. Для этого фрейма отводится память и в нем фиксируются все значения переменных тела функции при n=4. Отметим, что в рекурсивном фрейме фиксируются значения всех переменных функции, кроме глобальных.
     Затем происходит вызов Factorial(n) при n=3. Образуется фрейм №2, где фиксируются значения переменных тела функции при n=3. При этом фрейм №1 также хранится в памяти. Из фрейма №2 происходит обращение к Factorial(n) при n=2. В результате этого обращения образуется фрейм №3, где фиксируются значения переменных тела функции при n=2 и т.д. до тех пор, пока при очередном обращении к функции Factorial условие n>0 не примет значение false.
     Это произойдет в фрейме №5. В этом фрейме мы получим значение Factorial =1 и передадим это значение в фрейм №4. После этого фрейм №5 будет уничтожен, так как обращение Factorial(n) при n=0 будет выполнено.
     В фрейме №4 мы вычислим значение Factorial(n) для n=1. После чего мы передадим это значение во фрейм №3, а фрейм №4 будет закрыт, так как обращение к Factorial(n) при n=1 будет закончено.
     Так мы будем сворачивать эту цепочку фреймов в последовательности, обратной той, в которой мы их порождали, пока не свернем фрейм №1. После чего вычисление функции будет окончено.
     Рекурсия возможна не только в случае функций, но и процедур. Пример рекурсии для процедур приведен на рисунке 16.3. ............