рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Рекурсивные процедуры и функции

Рекурсивные процедуры и функции - раздел Информатика, Информатика и программирование на языке Паскаль   Рекурсивным Называется Объект, Который Частично Определяется ...

 

Рекурсивным называется объект, который частично определяется через самого себя. Рекурсивные определения используются во многих областях науки и, особенно, в математике.

Рассмотрим функцию определения факториала (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.

 

 


           
   
 
   
Рис. 9.10
 
 

Текст программы на языке Паскаль.

 


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

 

 


Обратный ход начинается с выполнения нерекурсивной части подпрограммы; после этого область стека, относящаяся к данному вызову удаляется и выполняется возврат к предыдущему вызову и т. д. Обратный ход завершается возвратом значения в программу, вызывавшую рекурсивную функцию.

В рекурсивной процедуре или функции должно быть условие выполнения нерекурсивных операторов для обеспечения завершения рекурсии, иначе возможны бесконечные рекурсивные вызовы и аварийное завершение программы из-за переполнения доступной памяти для стека.

В языке Паскаль допускается использование рекурсивных процедур. Рассмотрим пример рекурсивной процедуры на примере процедуры определения наибольшего общего делителя двух целых чисел.

– Конец работы –

Эта тема принадлежит разделу:

Информатика и программирование на языке Паскаль

Московский государственный горный университет.. Кафедра Системы автоматизированного проектирования.. КАРПОВИЧ Е Е..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Рекурсивные процедуры и функции

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Москва-2005
    УДК 681.142.2(075.8)     Карпович Е.Е. Информатика и программирование на языке Паскаль. Учебное пособие. -М.: МГГУ, 2005 г. 152

Предмет информатики как науки
Информатика – это техническая наука, изучающая способы создания, хранения, обработки и передачи данных средствами вычислительной техники, а также принципы функционирования этих средств и методы упр

Структура аппаратных средств ПЭВМ
  Персональная ЭВМ–это комплекс программных и аппаратных средств, предназначенных для автоматической обработки информации. П

Программное обеспечение пэвм
  Назначением ЭВМ является выполнение программ. Совокупность программ для персонального компьютера называется программным обеспечением (ПО). ПО ПЭВМ включает в себя три больших класса

Этапы разработки программ
  Разработка программ включает в себя следующие этапы: 1. Анализ и уточнение требований, предъявляемых к программе. Иногда этот этап называют постановкой задачи. 2.

Формы представления алгоритмов
  Ключевым этапом разработки программы является этап разработки алгоритма и структур данных. Результат этого этапа – формализованное описание или представление алгоритма. Под формой п

Алгоритм линейной структуры
  Заданы радиусы оснований R1 и R2, длина образующей L и высота h прямого усеченного конуса. Найти площадь поверхности и объем усеченного конуса.   Постановк

Алгоритм разветвляющейся структуры
  Вычислить значение функции в зависимости от условия по формуле:   Постановка задачи.

Ввод(X)
3.2.3. Алгоритмы циклической структуры.   Пример 1. Опреде

Ввод(K)
       

Ввод(R)
           

Алфавит и лексемы
  Язык Паскаль, как и любой язык программирования имеет свой алфавит, синтаксис и семантику. Алфавит ¾ это набор допустимых в языке символов. Синтаксис ¾ это совокупност

Структура программы на языке Паскаль
  Паскаль-программа включает в себя следующие разделы: § заголовок программы (Program); § раздел указания используемых модулей (Uses); § раздел объявления м

Массивы
  Данными типа «массив» являются массивы. Массив представляет собой фиксированное количество компонент одного и того же типа. Массив определяется именем, количеством размерностей (коо

Множества
  Тип-множество, используемый в языке Паскаль, соответствует понятию множества в математике, и создается с помощью следующего конструктора типа: Type T = set of T0;

Процедуры и функции
  При создании программы решения сложной задачи выполняется декомпозиция (разделение) задачи на подзадачи, а подзадачи – на еще меньшие подзадачи. Каждая подзадача имеет точно определ

Область действия идентификаторов при использовании процедур и функций. Локальные и глобальные переменные
  Областью действия идентификатора называется часть программы, где он может быть использован и определяется местом его объявления. Если идентификаторы объявлены в рамках одной

Передача данных в подпрограмму с помощью параметров. Формальные и фактические параметры
  Как заголовок процедуры, так и заголовок функции может содержать список формальных параметров, который имеет следующий формат: (<описание параметра 1>; < описание

Использование процедур и функций
  Задание. Определить наибольший общий делитель двух целых чисел. Постановка задачи. Входные данные: A , B – целые, положительные числа. Вых

Основные определения
  По способу распределения памяти данных в программах делятся на статические и динамические. Данные статической структуры – это данные, размещение которых в памяти ЭВМ и взаимосвязи м

Объявление и создание динамических структур данных. Указатели
В языке Паскаль имеются средства создания динамических структур данных, которые позволяют изменять количество элементов данных во время выполнения программы, т.е. создавать динамические переменные,

Программа создания и обработки линейного списка
  Линейный список – это структура данных, представляющая собой последовательность компонент, связанных между собой адресами, как показано на рис. 1.

Результаты работы программы
0 -- Exit; 1 -- Create; 2 -- Display; 3 -- Add; 4 -- Delete; Input option (0 -- 4)   0 -- Exit; 1 -- Create; 2 -- Display; 3 -- Add; 4 -- Delete; Input o

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги