Категория
Информатика
Тип
реферат
Страницы
2 стр.
Дата
13.11.2009
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
18532.zip — 14.29 kb
  • rekursija_18532_1.rtf — 117.63 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Eaeoey 16
E.M.V.
Рекурсия.
С понятием рекурсии мы уже встречались : рекуррентные соотношения довольно часто встречаются в математических выражениях. Рекурсия в определении состоит в том, что определяемое понятие определяется через само это понятие. Примером здесь может служить определение высказывания (см. лекция 5, определение 5.1). Рекурсия в вычислениях выступает в форме рекуррентных соотношений, которые показывают, как вычислить очередное значение, используя предыдущие.
Например, рекуррентное соотношение
x i = x i -2 + x i
-1 , где x 1 =1 , x
2 =2
задает правило вычисления так называемых чисел Фибоначчи.
Другим примером рекуррентных соотношений могут служить правила вычисления членов арифметической прогрессии
a n +1 = a n + d
, где d - разность прогрессии,
либо геометрической прогрессии
a n +1 = q a n
, где 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).



Ваше мнение



CAPTCHA