Пиши Дома Нужные Работы

Обратная связь

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

 

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

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

 

 


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

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

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

Задание. Определить наибольший общий делитель двух целых чисел.

Постановка задачи.

Входные данные:

A , B – целые, положительные числа.

Выходные данные:

Nod – наибольший общий делитель A и B.

Метод решения: рекурсивный алгоритм Евклида.

 

Алгоритм. Выдача наибольшего общего делителя двух целых чисел.

Входные данные.

СКАЛЯР A , B – целые, положительные числа.

Выходные данные.

СКАЛЯР Nod – целое число.

Начало

A:=0

B:=0

ЦИКЛ_ПОКА(A<=0 ИЛИ B<=0)

Вывод(‘Input A,B : ’)

ввод(A,B)

КОНЕЦ_ЦИКЛА

Findnod(A,B,Nod)

Вывод(‘Nod(A,B)= ’,Nod)

Конец

 

Алгоритм. Процедура определения наибольшего общего делителя двух целых чисел (findnod).

Входные данные.

СКАЛЯР A , B – целые, положительные числа.

Выходные данные.

СКАЛЯР Nod – целое число.

Промежуточные данные.

СКАЛЯР R – целое число. {остаток от деления }

Начало

ЕСЛИ (A mod B <>0)

R:= A mod B

A:=B

B:= R

Findnod(A,B,Nod)

ИНАЧЕ

Nod:=B

КОНЕЦ_ЕСЛИ

Конец


Блок - схема программы

           
   
 
 
 
   
Рис. 9.12



Блок-схема процедуры findnod.

           
   
 
 
 
   
Рис. 9.13



Программа на языке Паскаль, использующая процедуру.


Program Exam7;

Var

A, B, Nod: integer;

procedure findnod (A, B: integer; Var Nod: integer);

Var R: integer;

Begin

If A mod B <>0 do

Begin

R:= A mod B;

A:=B; B:=R;

Findnod(A,B,Nod);

End

Else

Nod:=B;

End;

Begin A:=0; B:=0;

While (A<=0) or (B<=0) do begin

Writeln('Input A,B <>0 :');

Readln(A,B);

End;

findnod(A,B,Nod);

Writeln('Nod(A,B) = ',Nod);

Readln;

End.

 

Результаты тестирования.

1. Исходные данные:

A=84

B=36

Результат: Nod(A,B)=12

d) Тестовый пример 2:

A=84

B=56

Результат: Nod(A,B)=28

Результаты, выданные программой.

 

3. Тестовый пример1

Input A,B <>0 :

Nod(A,B) = 12

 

4. Тестовый пример 2

Input A,B <>0 :

Nod(A,B) = 28

 

Программа на языке Паскаль, использующая функцию.

Program Exam11;

Var

A, B, Nod: integer;

Function findnod (A, B: integer): integer;

Var R: integer;

Begin

R:=1;

While R<>0 do

Begin

R:=A mod B;

A:=B; B:=R;

End;

findnod :=A;

End;

Begin A:=0; B:=0;

While (A<=0) or (B<=0) do begin

Writeln('Input A,B <>0 :');

Readln(A,B);

End;

Nod := findnod(A,B);

Writeln('Nod(A,B) = ',Nod);

Readln;

End.

 

Результаты тестирования.

1. Тестовый пример 1

Исходные данные:

A=84

B=36

Результат: Nod(A,B)=12

2. Тестовый пример 2

Исходные данные:

A=84

B=56

Результат: Nod(A,B)=28

Результаты, выданные программой.

Тестовый пример1

Input A,B <>0 :

Nod(A,B) = 12

 

Тестовый пример 2

Input A,B <>0 :

Nod(A,B) = 28

 

 


Модули

 

Одним из слабых мест механизма подпрограмм в Borland Pascal 7.0 является то, что они встроены в тело программы. Подпрограммы нельзя отдельно компилировать, отлаживать и использовать другими программами. Для того, чтобы можно было подпрограммы отдельно компилировать и вызывать многими программами, необходимо использовать модули.

Модуль представляет собой совокупность различных компонент раздела описаний (констант, типов, переменных, подпрограмм), предназначенную для использования другими модулями и программами. Сам по себе модуль не является выполняемой программой (модуль нельзя запустить на выполнение). Однако он хранится и компилируется отдельно.

Модуль имеет свой заголовок:

Unit <имя модуля>;

и два раздела: интерфейсную часть (interface) и исполняемую часть (implementation).

Общая структура модуля имеет следующий вид:

Unit <имя модуля>;

Interface

<объявления видимых объектов модуля: типов, констант, переменных, заголовков подпрограмм >

implementation

<описания скрытых объектов: процедур и функций>

begin

<операторы инициализации модуля[6]>

end.

 

Интерфейсная часть может включать следующие компоненты:

Interface

Uses <список используемых модулей >;

<раздел объявления констант (Const)>

<раздел объявления типов (Type) >

<раздел объявления переменных (Var)>

<раздел заголовков процедур и функций>.

Список используемых модулей содержит имена стандартных модулей, кроме модуля System, такие как Crt, Graph, Overlay, Dos, и имена модулей, созданных пользователем. Имена в списке разделяются запятыми.

В разделе реализации (implementation) содержатся описания процедур и функций, заголовки которых объявлены в интерфейсной части. Кроме того, в исполнительной части могут быть объявлены типы, константы, переменные, которые используются в подпрограммах, но должны быть недоступны пользователю. В конце текста модуля всегда записывает ключевое слово “end” с точкой.

Традиционные правила области действия глобальных и локальных переменных для модулей не выполняются. Языковая конструкция Unit (модуль) была специально включена в систему Borland Pascal для того, чтобы исключить влияние глобальных переменных, объявленных в главной программе, на описания подпрограмм, входящих в модули, которые эта программа использует.

Поэтому, если все-таки возникает необходимость ввести доступные для всех модулей программы описания, то для этого надо создать модуль глобальных описаний, например:

 

Unit globals;

Interface

Const L=100;

Type Tvector = array[1..L] of integer;

Implementation

End.

 

В этом случае исполнительная часть implementation является пустой.

Рассмотрим пример модуля, содержащего процедуры и функции обработки одномерного массива, тип которого задан в модуле Globals. Этот модуль имеет имя Vector и включает следующие подпрограммы:

o function Vect_Max(Vect:TVector; N:byte): byte; - возвращает индекс максимального элемента массива из N элементов;

o function Vect_Min(Vect:TVector; N:byte): byte; - возвращает индекс минимального элемента массива;

o procedure Print_Vect(Vect:TVector; N:byte); - выдает все элементы массива на экран;

o procedure Vect_Inverse(Var Vect:TVector; i1,i2:byte); - меняет местами максимальный и минимальный элементы одномерного массива.

Кроме того, модуль Vector использует модуль глобальных описаний globals.


Текст модуля Vector.

unit Vector;

interface

Uses globals;

function Vect_Max(Vect:TVector; N:byte): byte;

function Vect_Min(Vect:TVector; N:byte): byte;

procedure Print_Vect(Vect:TVector; N:byte);

procedure Vect_Inverse(Var Vect:TVector; i1,i2:byte);

implementation

function Vect_Max(Vect:TVector; N:byte): byte;

Var Max:integer;

im,i: integer;

begin

Max:=Vect[1]; im:=1;

for i:=1 to N do

if Max<Vect[i] then begin

Max:=Vect[i]; im:=i;

end;

Vect_Max:=im;

end;

function Vect_Min(Vect:TVector; N:byte): byte;

Var Min:integer;

im,i: integer;

begin

Min:=Vect[1]; im:=1;

for i:=1 to N do

if Min>Vect[i] then begin

Min:=Vect[i]; im:=i;

end;

Vect_Min:=im;

end;

procedure Print_Vect(Vect:TVector; N:byte);

Var i: integer;

begin

writeln;

for i:=1 to N do write(Vect[i],' ');

end;

procedure Vect_Inverse(Var Vect:TVector; i1,i2:byte);

Var t: integer;

begin

t:=Vect[i1]; Vect[i1]:=Vect[i2]; Vect[i2]:=t;

end;

end.

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

 

Program Main;

Uses globals,vector;

Var A: TVector;

i,N:byte;

n1,n2:byte;

begin

writeln;

writeln(' Input N<=100');

readln(N);

writeln(' Input array A of N elements :');

for i:=1 to N do read(A[i]);

n1:=Vect_Max(A,N);

n2:=Vect_Min(A,N);

Vect_Inverse(A,n1,n2);

Print_Vect(A,N);

Readln;

end.

 

Тестовый пример. Результаты, выданные программой Main.

 

 

Input N<=100

Input array A of N elements :

1 2 3 4 5 64 7 8 9 19

 

64 2 3 4 5 1 7 8 9 19

 






ТОП 5 статей:
Экономическая сущность инвестиций - Экономическая сущность инвестиций – долгосрочные вложения экономических ресурсов сроком более 1 года для получения прибыли путем...
Тема: Федеральный закон от 26.07.2006 N 135-ФЗ - На основании изучения ФЗ № 135, дайте максимально короткое определение следующих понятий с указанием статей и пунктов закона...
Сущность, функции и виды управления в телекоммуникациях - Цели достигаются с помощью различных принципов, функций и методов социально-экономического менеджмента...
Схема построения базисных индексов - Индекс (лат. INDEX – указатель, показатель) - относительная величина, показывающая, во сколько раз уровень изучаемого явления...
Тема 11. Международное космическое право - Правовой режим космического пространства и небесных тел. Принципы деятельности государств по исследованию...



©2015- 2024 pdnr.ru Все права принадлежат авторам размещенных материалов.