рефераты конспекты курсовые дипломные лекции шпоры
- Раздел Информатика
- /
- Рекурсивные процедуры и функции
Реферат Курсовая Конспект
Рекурсивные процедуры и функции
Рекурсивные процедуры и функции - раздел Информатика, Информатика и программирование на языке Паскаль Рекурсивным Называется Объект, Который Частично Определяется ...
Рекурсивным называется объект, который частично определяется через самого себя. Рекурсивные определения используются во многих областях науки и, особенно, в математике.
Рассмотрим функцию определения факториала (n!); факториал – это произведение первых n натуральных чисел. Такое произведение можно вычислить с помощью программы, использующей оператор цикла for. Однако, существует другое определение факториала, в котором используется рекуррентные формулы:
(1) 1!=1;
(2) для любого n>0, n!=n*(n-1)!
Определения, использующие рекуррентные формулы, называют рекурсивными определениями. Рекурсивные определения упрощают процесс вычислений. Например, в случае определения членов ряда Фибоначчи:
Рекурсивное определение значительно проще приведенной выше формулы и имеет следующий вид:
(1) F(1)=1;
(2) F(2)=1;
(3) Для любого n>2, F(n)=F(n-1)+F(n-2).
Рассмотрим рекурсивный алгоритм на примере накопления произведений. Пусть требуется написать программу, которая определяет произведение натуральных чисел от 1 до n:
P=n!=1*2*…*n.
Постановка задачи.
Входные данные:
n>0 – целое число.
Выходные данные:
P= n! – целое число.
Аномалии. n<0, в программе не рассматриваются.
Метод решения: для определения произведения использовать рекуррентные формулы:
1. 1!=1;
2. для любого n>0, n!=n*(n-1)!
Блок-схема рекурсивной функции fact для определения факториала представлена на рис 9.10, а блок-схема основной программы – на рис. 9.11.
 | |||||
| |||||
 |
Текст программы на языке Паскаль.
Program Exam10;
Var
Ch, Proiz: integer;
Function Fact(n: integer): integer;
Var R: integer;
Begin
If n>0 then Fact:=n*Fact(n-1)
Else Fact:=1;
End;
Begin
Writeln('Input Ch>0 :');
Readln(Ch);
If Ch>0 then
begin
Proiz := Fact(Ch);
Writeln('Ch','!=',Proiz)
end
Else Writeln('Error! Ch<0');
Write('PRESS ANY KEY!!!');
Readln;
End.
Результаты тестирования.
1. Исходные данные:
Ch=3
Ch!=1*2*3=6
Результаты, выданные программой.
Input Ch>0 :
Ch!=6
PRESS ANY KEY!
2. Исходные данные:
Ch=-3
Результат- сообщение «Error! Ch<0».
Результаты, выданные программой.
Input Ch>0 :
-3
Error! Ch<0
PRESS ANY KEY!!!
Рекурсивный процесс предполагает прямой ход или рекурсивный спуск и обратный ход или рекурсивный возврат.
Прямой ход.
При каждом рекурсивном обращении к функции создается новый экземпляр памяти всех локальных переменных и параметров этой функции, который запоминается в некоторой области памяти. Глубина рекурсии определяется количеством выполненных рекурсивных вызовов. Цепочка вызовов рекурсивных подпрограмм создает в памяти связанную последовательность областей памяти, организованных по принципу стека: доступной является область, размещенная последней. Прямой ход завершается тем вызовом подпрограммы, в котором истинно условие выполнения ее нерекурсивной части.
Рекурсивный процесс выполнения функции Fact для Ch=3 имеет глубину рекурсии, равную 3, как показано в таблице ниже.
| Текущий уровень рекурсии | Рекурсивный спуск (прямой ход) | Рекурсивный возврат (обратный ход) | ||
| Ch=3 Fact:=3*Fact(2-1) | Fact:=3*2(=6) | 
| |
| Ch=2 Fact:=2*Fact(2-1) | Fact:=2*1(=2) | |||
| Ch=1 Fact:=1 | Ch=1 Fact:=1 |
Обратный ход начинается с выполнения нерекурсивной части подпрограммы; после этого область стека, относящаяся к данному вызову удаляется и выполняется возврат к предыдущему вызову и т. д. Обратный ход завершается возвратом значения в программу, вызывавшую рекурсивную функцию.
В рекурсивной процедуре или функции должно быть условие выполнения нерекурсивных операторов для обеспечения завершения рекурсии, иначе возможны бесконечные рекурсивные вызовы и аварийное завершение программы из-за переполнения доступной памяти для стека.
В языке Паскаль допускается использование рекурсивных процедур. Рассмотрим пример рекурсивной процедуры на примере процедуры определения наибольшего общего делителя двух целых чисел.
– Конец работы –
Эта тема принадлежит разделу:
Информатика и программирование на языке Паскаль
Московский государственный горный университет... Кафедра Системы автоматизированного проектирования... КАРПОВИЧ Е Е...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Рекурсивные процедуры и функции
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
| Твитнуть |
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Реклама
Информация в виде рефератов, конспектов, лекций, курсовых и дипломных работ имеют своего автора, которому принадлежат права. Поэтому, прежде чем использовать какую либо информацию с этого сайта, убедитесь, что этим Вы не нарушаете чье либо право.
© copyright 1999 - 2024 allRefs.net. Все права защищены. Страница сгенерирована за: 0.019 сек.
Новости и инфо для студентов