Рекурсия
Рекурсия.С понятием рекурсии мы уже встречались: рекуррентные соотношения довольно часто встречаются в математических выражениях. Рекурсия в определении состоит в том, что определяемое понятие определяется через само это понятие. Примером здесь может служить определение высказывания (см. лекция 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 будет закончено.Так мы будем сворачивать эту цепочку фреймов в последовательности, обратной той, в которой мы их порождали, по...
Другие файлы:
Рекурсия и функции
Определение функции, ее прототип. Рекурсия - частичное определение объекта через себя. Рекурсивная функция произведения 2-х целых чисел. Задача о вычи...
Информатика. Творчество. Рекурсия.
Программирование на языке Паскаль
Понятие программы и ее основные составляющие. Операторы ввода и вывода. Разветвляющиеся алгоритмы. Цикл как многократное выполнение одинаковых действи...
