4.2. Формы рекурсий.

Простая линейная рекурсия.

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

Параллельная рекурсия.

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

Заметим, что параллельность является лишь текстуальной, но никак не временной: вычисление ветвей в стеке производится последовательно. В отличие от линейной рекурсии, при которой структура рекурсивных вызовов линейна, нелинейная рекурсия ведет к древовидной структуре вызовов. Вызовы лавинообразно ведут к экспоненциальному нарастанию возникающих рекурсивных вызовов – «каскаду вызовов», отсюда еще одно название – каскадная рекурсия.

Взаимная рекурсия.

Если процедура или функция вызывает себя сама, это называют прямой рекурсией. Но может встретиться ситуация, когда подпрограмма обращается к себе опосредованно, путем вызова другой подпрограммы, в которой содержится обращение к первой. В этом случае мы имеем дело с косвенной, или взаимной, рекурсией.

Рассмотрим следующий пример практического использования косвенной рекурсии:

Найти определитель заданной квадратной матрицы.

A – матрица NxN

S – сумма

I, J, K – параметры цикла

B – матрица (N – 1)x(N – 1)

P – (-1)^{1 + J}

Пример на Turbo Pascal:

type

MATR = array [1..10, 1..10] of Real;

function DET(N: Integer; A: MATR): Real;

var

I, J, K: Integer;

B: MATR;

S: Real;

P: Integer;

begin

if N = 2 then

DET := A[1, 1] * A[2, 2] - A[1, 2] * A[2, 1]

else

begin

S := 0;

P := 1;

for J := 1 to N do

begin

for I := 1 to N - 2 do

for K := 1 to N - 1 do

if K < J then

B[I, K] := A[I + 1, K]

else

B[I, K] := A[I + 1, K + 1];

S := S + P * A[1, J] * DET(N - 1, B);

P := -P;

end;

DET := S;

end;

end;

var

I, J, M: Integer;

C: MATR;

begin

ReadLn(M);

Randomize;

for I := 1 to M do

for J := 1 to M do

C[I, J] := Random(10);

WriteLn(DET(M, C):3:3);

ReadLn;

end.

В QBasic матрица C будет передаваться по ссылке, и когда будет осуществляться рекурсивный вызов функции возникнет проблема.

5. Модули в языке turbo pascal. Модуль пользователя.

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

Модули в языке Паскаль делятся на стандартные и модули пользователя.

5.1. Стандартные модули.

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

В систему Turbo Pascal 7.0 включены следующие стандартные модули:

• System – является основной библиотекой среды Turbo Pascal, обеспечивающей работу программ пользователя и всех остальных модулей системы, подключается автоматически к программе/модулю, и указывать его в Uses не следует. Объявленные в модуле константы, переменные и подпрограммы считаются поэтому встроенными и представляют собой все встроенные средства стандарта языка, а также некоторые дополнительные средства общего назначения (управления вводом-выводом, работы со строками, статической и динамической памятью и т.д.).

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

• Graph – содержит средства управления графическим режимом работы экрана, с помощью которых можно создавать разнообразные графические изображения, сопровождаемые текстовыми надписями с использованием различных шрифтов.

• Printer – обеспечивает быстрый доступ к печатающему устройству; в модуле определяется файловая переменная Lst типа Text, которая связывается с принтером (логическим устройством PRN), после подключения модуля она может быть использована в качестве файловой переменной в процедурах Write и WriteLn.

• Strings – содержит подпрограммы, позволяющие работать с ASCIIZ-строками (последний байт строки содержит нуль-символ с кодом 0), а также преобразовывать их в строки типа String и наоборот; введение таких строк позволяет совместить программы, написанные на языке Turbo Pascal, с программами, использующими среду Windows, а также установить соответствие с другими языками (например, с Си, ассемблером и т. д.).

• Dos – содержит средства, позволяющие использовать не предусмотренные в стандарте языка возможности операционной системы MS DOS, - средства управления вычислительным процессом и операционной средой, в том числе обслуживания прерываний, запуска EXE-файлов, проверки состояния диска, управления таймером, специальные средства обработки файлов.

• WinDos – позволяет использовать возможности операционной системы, не предусмотренные в стандарте языка, при использовании ASCIIZ-строк (используется вместо модуля Dos).

• Overlay – предназначен для организации оверлейных программ (с перекрытием), которые при их выполнении загружаются и выгружаются из оперативной памяти отдельными частями – секциями; необходим при разработке громоздких программ, требующих большго объема оперативной памяти.

• Turbo3, Graph3 – введены для совместимости с более ранней версией Turbo Pascal 3.0.