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

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

В Object Pascal допустимо обращение подпрограммы к самой себе (рекурсивное обращение). При таком обращении параметры, которые использует подпрограмма, заносятся в стек и сохраняются там до конца работы подпрограммы. Рекурсивные подпрограммы являются исключительно удобным, нередко незаменимым инструментом построения эффективных алгоритмов. Оборотной стороной рекурсивных процедур является опасность переполнения стека, что часто ограничивает возможность написания таких алгоритмов.

В качестве иллюстрации приведем пример простой и чрезвычайно эффективной процедуры сортировки (расстановки элементов в порядке неубывания) фрагмента целочисленного одномерного массива A:

procedure QuickSortPart(var A: array of Integer; iLo, iHi: Integer);

var

Lo, Hi, Mid, T: Integer;

begin

Lo := iLo;

Hi := iHi;

Mid := A[(Lo + Hi) div 2]; {средний элемент фрагмента}

repeat {деление фрагмента на левую и правую части}

while A[Lo] < Mid do Inc(Lo);

while A[Hi] > Mid do Dec(Hi);

if Lo <= Hi then

begin

T := A[Lo];

A[Lo] := A[Hi];

A[Hi] := T;

Inc(Lo);

Dec(Hi);

end;

until Lo > Hi;

if Hi > iLo then QuickSortPart(A, iLo, Hi); {сортировка левой части}

if Lo < iHi then QuickSortPart (A, Lo, iHi); {сортировка правой части}

end;

Процедура QuickSortPart сортирует фрагмент одномерного массива A, начинающийся индексом iLo и заканчивающийся индексом iHi. Процедура основана на методе половинного деления. В соответствии с этим методом сначала выбирается элемент, расположенный в середине сортируемого фрагмента, затем элементы меньшие его отправляются в левую часть фрагмента, прочие – в правую часть. Далее сортируются левая и правая части разделенного массива как отдельные фрагменты по той же схеме, т. е. к каждой из них применяется та же процедура QuickSortPart. Именно обращение процедуры к самой себе и делает ее рекурсивной.

Ниже приведена обычная (нерекурсивная) процедура QuickSort сортировки всех элементов массива, которая выполняется обращением к рекурсивной процедуре QuickSortPart, где фрагмент – весь массив A.

procedure QuickSort (var A: array of Integer);

begin

QuickSortPart(A, Low(A), High(A));

end;

15.9. Параметры и конструкторы открытых массивов

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

array of type (предпочтительнее array[X .. Y] of type)

Например, операторы

procedure NullChar(A: array of Char);

begin

for i:= Low(A) to High (A) do A[i]:= '0';

end;

объявляют процедуру NullChar, которая содержит один параметр – открытый символьный массив А любого размера. В теле процедуры используется оператор цикла, который заполняет каждый элемент массива символом '0'. Для определения нижней границы индекса использована стандартная функция Low, для верхней – High.

Если к такой процедуре обратиться оператором NullChar(z), где тип переменной z = array[5 .. 55] of Char, то весь массив z будет заполнен символами "нуль".

Конструкторы открытых массивов допускают конструирование значений таких массивов прямо внутри оператора обращения к подпрограмме.

Пример:

var I, J: Integer;

procedure Add (A: array of Integer);

В этом случае можно обратиться к процедуре Add, например, так:

Add ([5, 7, I, I + J]);

16. Структура программы

В среде Delphi программа как единое целое представляется в виде проекта. В новой версии языка Object Pascal для представления проекта используется пять основных типов файлов:

dpr-файл головной программы;

текстовые pas-файлы;

откомпилированные dcu-файлы;

res-файлы ресурсов;

dfm-файлы ресурсов экранных форм;

готовые к использованию программные exe-файлы.

Исходная программа, написанная в среде Delphi на языке Object Pascal всегда состоит из нескольких модулей, каждый из которых размещается в отдельном текстовом файле. Один модуль является головной программой. Он начинается словом Program и размещается в файле с расширением .dpr. Все остальные модули являются подчиненными и начинаются словом Unit. Такие модули размещаются в файлах с расширением .pas. Все модули заканчиваются оператором End, после которого ставится символ "точка".

Всякий модуль может использовать другие модули, к числу которых могут относиться текстовые файлы, res- и dfm-файлы ресурсов или откомпилированные файлы Unit-модулей. Сcылка на необходимые к использованию модули содержится в секциях Uses. Текстовые или скомпилированные файлы обычно содержат необходимые для использующего их модуля величины – константы, типы, переменные, процедуры и функции. Файлы ресурсов необходимы для подключения констант, описывающих используемые внешние ресурсы.

Вышеперечисленные модули, размещенные в *.pas-, *.dcu-, *.res-, *.dfm-файлах, играют вспомогательную роль: они предназначены для компиляции и последующей сборки в полноценный программный модуль – exe-файл, готовый к исполнению на компьютере.

Ниже приведен пример исходных текстов головной программы KdnBread и одного подчиненного (используемого) ею модуля Main.

Program KdnBread; {начало текста головной программы}

{текст содержится в файле 'c:\Borland\Projects\KdnBread.pas'}

uses {ссылки на модули типа unit }

Forms, {ссылка на модуль Forms }

main in 'main.pas' {Form1}; {ссылка на модуль main }

{$R *.RES}

begin

Application.Initialize;

Application.CreateForm(TForm1, Form1);

Application.Run;

end. {конец текста головной программы}

unit Main; {начало текста модуля Main}

{ текст модуля содержится в файле 'c:\Borland\Projects\Main.pas' }

interface {начало интерфейсной части модуля}

uses

Windows, Messages, SysUtils, {ссылки на другие модули }

Graphics, Controls, Forms, StdCtrls;

Type {описание типов}

TForm1 = class(TForm)

Button1: TButton;

L1: TLabel;

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

Var {описание переменных}

Form1: TForm1;

b: boolean;

i: Integer;

IterationPar: Word;

function OneSymbString(c: Char; d: byte): String; {заголовок функции}

implementation {начало процедурного блока модуля}

{$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject); {заголовок процедуры}

begin

if (i > 12) and b then

L1.Caption:='Студент:'+AnsiUpperCase ('Иванов Владимир Иванович');

end; {конец процедуры}

function OneSymbString(c: Char; d: byte): String; {заголовок функции}

begin

Result:=CharStr(c, d);

end; {конец функции}

initialization

IterationPar:= 0;

end. {конец текста модуля Main}

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

16.1. Структура модуля

Модуль имеет следующую структуру:

Unit <имя>;

interface

<интерфейсная часть>

implementation

<выполняемая часть>

initialization

<блок инициирования>

finalization

<блок завершения>

end.

16.2. Раздел Interface

Раздел Interface модуля Unit предназначен для описания внешних компонент: используемых модулей, типов, констант, переменных, заголовков процедур и функций. Так, в вышеприведенном примере в разделе Interface содержатся:

в списке Uses – ссылки на модули Windows, Messages, SysUtils, Graphics, Controls, Forms, StdCtrls;

в секции Type – описание типа экранной формы – класс TForm1;

в секции Var – описание переменных Form1, b, i и описание заголов-ка функции OneSymbStr, предназначенной для создания строки повторяю-щихся d раз символов Ch.

Похожие работы

Объектно-ориентированная среда программирования "Object Pascal" в профильном курсе информатики

Скачать

49877

5

0

... в среде Delphi). Задачи использовались как с данного сайта, так и из других источников – книг и семинарских занятиях по информатике в МГОУ. Курс завершается разработкой игры. Программное обеспечение: свободно распространяемая версия объектно-ориентированной среды программирования Delphi. Методы обучения: метод проектов, лекции, проблемный метод, частично-поисковый метод. Контроль знаний и умений ...

Разработка программы на языке Borland Object Pascal (Ide Borland Delphi)

Скачать

17314

1

5

... // ... if(condition1) { j = 4; goto label1; } // ... for(j = 0; j < 10; j++) { // ... label1: // ... if(condition2) { i = 6; goto label2; } } // ... label2: // ... } 2.2       Разработка программы В среде программирования Borland Delphi создадим новое приложение (пункт меню File New Application). ...

Типы данных в Object Pascal

Скачать

27554

2

0

... так называемые указатели. Указатель - это переменная, которая в качестве своего значения содержит адрес байта памяти. С помощью указателей можно размещать в динамической памяти любой из известных в Object Pascal типов данных. Лишь некоторые из них (Byte, Char, ShortInt, Boolean) занимают во внутреннем представлении один байт, остальные - несколько смежных. Поэтому на самом деле указатель адресует ...

Программирование на Object Pascal в среде Delphi

Скачать

62207

3

0

... групп нулей и единиц. Каждая группа отделяется друг от друга одним или несколькими пробелами. Найти и вывести на экран группы с четным количеством символов. Лабораторная работа №6 Программирование АЛГОРИТМОВ с использованием записей Цель лабораторной работы: создать приложение, в котором используются данные типа запись. 6.1.Пример создания приложения Задание: создать Windows-приложение для ...