Рекурсия.

С понятием рекурсии мы уже встречались: рекуррентные соотношения довольно часто встречаются в математических выражениях. Рекурсия в определении состоит в том, что определяемое понятие определяется через само это понятие. Примером здесь может служить определение высказывания (см. лекция 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).

		24

Рис. 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 будет выполнено.

Рекомендуем скачать другие рефераты по теме: реферат книга, доклад по обж.





1  2  3  4 | Следующая страница реферата