С понятием рекурсии мы уже встречались: рекуррентные соотношения довольно часто встречаются в математических выражениях. Рекурсия в определении состоит в том, что определяемое понятие определяется через само это понятие. Примером здесь может служить определение высказывания (см. лекция 5, определение 5.1). Рекурсия в вычислениях выступает в форме рекуррентных соотношений, которые показывают, как вычислить очередное значение, используя предыдущие.
Например, рекуррентное соотношение
xi =xi -2 +xi -1 , где x1 =1 , x2 =2
задает правило вычисления так называемых чисел Фибоначчи.
Другим примером рекуррентных соотношений могут служить правила вычисления членов арифметической прогрессии
Возможно вы искали - Реферат: Развитие Интернета в Китае
an +1 =an +d , где d - разность прогрессии,
либо геометрической прогрессии
an +1 =qan , где 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
elsewriteln (’значение 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. Там показано описание рекурсивной процедуры для распечатки (вывода на печать) строки символов в порядке, обратном их вводу.
Procedure BackPrint ;
var символ : char ;
begin read (символ) ;