Подпрограмма – это повторяющая группа операторов, оформленная в виде самостоятельной программой единицы. Она записывается однократно, а в соответствующих местах программы обеспечивается лишь обращение к ней по имени.
Использование подпрограммы позволяет, во-первых, сократить объем программы, во-вторых, улучшает структуру программы с точки зрения ее читаемости и наглядности, в-третьих, уменьшает вероятность ошибок и облегчает процесс отладки.
В языке Паскаль механизм подпрограмм реализуется в виде ПРОЦЕДУР и ФУНКЦИЙ, которые вводятся в программе с помощью своего описания, но их способом их использования.
Процедура- это независимая часть программы, которую можно вызвать по имени для выполнения определенных действий. Процедура не может выступать как операнд в выражении. Упоминание имени процедуры в тексте программы приводит к активизации процедуры и называется ее вызовом. Например,
Delay (10); вызывает задержку выполнения программы на 10мс.
Функция аналогична процедуре, но имеются два отличия: функция передает в точку вызова скалярное значение; имя функции в выражении может выходить как операнд. Например, функция SQR(x)-возведет в квадрат значение целого или вещественного значения X и передаст в точку вызова вычисленное значение квадрата переменной X.
Все процедуры и функции языка Паскаль делятся на две группы:
à Встроенные (стандартные) - входят в состав языка и вызываются для выполнения по строго фиксированному имени.
à Определенные пользователем – разрабатываются и имеются самим пользователем.
При вызове подпрограммы, определенной программистом, работа главной программы на время приостанавливается и начинает выполняться вызванная подпрограмма.
В программе процедуры и функции описываются после раздела ее переменных, но до начала ее основной части, то есть до Begin, начинающего эту часть.
Передача данных из главной программы в подпрограмму и возврат результата выполнения функции осуществляется с помощью параметров.
Параметром называется переменная, которой присваивается какое-либо значение в рамках указанного применения.
Фактические параметры - это параметры, которые передаются подпрограмме при общении с ней.
Формальные параметры – это переменные, фиктивно присутствующие в процедуре и определение тип и место подстановки фактических параметров, над которыми производятся действия.
Параметры – переменные - это те формальные параметры, перед которыми стоит служебные слово Var. Они передаются по ссылке (передается адрес фактического параметра) тогда, когда необходимо передать некоторые новые значения в точку вызова процедуры из программы, то есть когда нужно, чтобы изменения в теле процедуры значений формальных параметров приводило к изменению соответствующих фактических параметров, таким образом, они и получают новое значение.
Параметры – значения - перед ними слово Var не ставится и идет передача по значению, то есть передается только копия значения этих параметров, внутри процедуры можно производить любые действия с данными формальными параметрами (допустимы для его типа), но их любые изменения никак не отражаются на значениях соответствующих фактических параметров, никак не отражаются на значениях соответствующих фактических параметров, то есть какими они были до вызова процедуры, то такими же и останутся после завершения ее работы.
Подпрограмма – относительно самостоятельная часть программы, имеющая свое имя и выполняющая определенные действия.
Подпрограммы повышают надежность и наглядность программ, т.к. позволяют разрабатывать и отлаживать каждый блок программы независимо (например, разными людьми).
Структура подпрограммы почти полностью повторяет структуру всей программы и состоит из следующих частей:
заголовок подпрограммы
раздел описаний
тело подпрограммы
В Паскаль имеются два вида подпрограмм – процедуры и функции . Они отличаются назначеием и способом их использования. Процедуры служат для выполнения определенной последовательности действий, направленных на изменение программной обстановки (изменение значений переменных, ввод/вывод данных и т.п.). Функции для вычисления значения выражения.
5.1 Процедуры
procedure <имя> (список формальных параметров);
<раздел описаний>;
begin
< тело процедуры >;
Пример 1: Процедура вычисления и вывода на экран куба числа.
procedure cub(x: real);
Указание имени процедуры в программе приводит к активизации процедуры и называется ее вызовом . Сразу после активизации процедуры начинают выполняться входящие в нее операторы. После выполнения последнего оператора процедуры управление передается в основную программу и далее выполняются операторы, следующие за вызовом процедуры. Процедура может вызываться в основной программе неоднократно.
Например:
Для обмена информацией между основной программой и процедурой используются параметры, которые придают процедуре универсальность.
Пример 2: Программа, выводящая на экран следующее:
var a,b: integer;
procedure Stars; {без параметров}
var i: integer;
for i:=1 to 9 do write(‘*’);
for a:=1 to 4 do
writeln(‘a=’,a,’ b=’,b);
Stars; {вызов процедуры Stars }
Пример 3:
var a,b: integer;
procedure Stroka(ch: char, n: integer);
var i: integer;
for i:=1 to n do write(ch);
Stroka(‘+’,4);
for a:=1 to 3 do
writeln(‘a=’,a,’ b=’,b);
Stroka(‘*’,8);
Разберем вызов процедуры Stroka(‘*’,8): ‘*’ и 8 – фактические параметры (т.е. те, которые указаны в скобках после имени процедуры при ее вызове), они присваиваются при вызове формальным параметрам ch и n (т.е. тем, которые указаны в скобках после имени процедуры при ее описании).
Замечание: количество, порядок и тип параметров при вызове процедуры должны совпадать с количеством, порядком и типом параметров, заданным при описании процедуры.
Результат на экране :
понятие подпрограмм процедуры и функции
В ТУРБО ПАСКАЛЕ различают два вида подпрограмм - это процедуры и функции . Процедура и функция - это именованная последовательность описаний и операторов. Так же использование процедур и функций необходимо тогда, когда имеется возможность использовать некоторые фрагменты уже разработанных ранее алгоритмов. Кроме того, подпрограммы применяются для разбиения крупных программ на отдельные смысловые части в соответствии с модульным принципом в программировании. Процедура - это независимая именованная часть программы, которую можно вызвать по имени для выполнения определённой в ней последовательности действий. Процедуры служат для задания совокупности действий, направленных на изменение внешней по отношению к ним программной обстановки. В ПАСКАЛЬ, существуют стандартные процедуры: read, readln, write, writeln. Таким образом, концепция процедуры расширяет понятие оператора в языке ПАСКАЛЬ. Функция отличается от процедуры тем, что возвращает результат указанного при её описании типа. Вызов функции может осуществляться из выражения, где имя функции используется в качестве оператора. Функции являются частным случаем процедур, и обязательно возвращают в точку вызова результат как значение имени этой функции. При использовании функций необходимо учитывать совместимость типов в выражениях. В ПАСКАЛЬ, существует ряд стандартных функций, известных любой программе: sin, cos, eof, а также и другие функции из таблицы №3. Таким образом, концепция функции расширяет понятие выражения в языке ПАСКАЛЯ.
Локальные и глобальные переменныеНапомним, что каждый модуль (процедура, функция, программа) состоит из заголовка (procedure…, function…, program… ) и блока.
Если блок какой-либо процедуры p1 содержит внутри процедуру p2, то говорят, что p2 вложена в p1.
procedure p1(x: real; var y: real);
procedure p2(var z: real);
…………………….
…………………….
Любые идентификаторы, введенные внутри какого-либо блока (процедуры, функции) для описания переменных, констант, типов, процедур, называются локальными для данного блока. Такой блок вместе с вложенными в него модулями называют областью действия этих локальных переменных, констант, типов и процедур.
var y1, y2: real;
var a, b, c, d: real;
{ Переменные a, b, c, d являются локальными для sq1,
область их действия – процедура sq1 }
……………………………………
{ Переменные y1, y2 - нелокальные для sq1,
область их действия – t1 и sq1 }
Константы, переменные, типы, описанные в блоке program, называются глобальными . Казалось бы, проще иметь дело вообще только с глобальными переменными, описав их все в program. Но использование локальных переменных позволяет системе лучше оптимизировать программы, делать их более наглядными и уменьшает вероятность появления ошибок.
Глава 17. Команды вызова процедур
Что такое подпрограмма
Подпрограмма представляет собой самостоятельную компьютерную программу, включенную в состав более сложной программы (по отношению к подпрограмме она выступает в роли основной или вызывающей программы). В любом месте основной программы можно обратиться к подпрограмме (чаще говорят "вызвать подпрограмму"). Ядро процессора при этом должно перейти на адрес первой команды подпрограммы, а после ее завершения вернуться на адрес команды основной программы, следующей за командой вызова подпрограммы.
В пользу применения подпрограмм в технологии программирования чаще всего выдвигаются два довода - экономия места в оперативной памяти и модульность структуры программы. Подпрограмма, в которой закодирован определенный алгоритм, может вызываться многократно, и таким образом экономится место в оперативной памяти, но в этом смысле подпрограмма мало чем отличается от цикла. Важнее другое - подпрограммы позволяют структурно разбить программу решения сложной задачи на более мелкие модули, решающие отдельные подзадачи. Такая модульность структуры большой программы существенно облегчает ее разработку.
Механизм поддержки работы с подпрограммами должен включать два основных типа команд - команду вызова подпрограммы и команду возврата из подпрограммы. Команда вызова подпрограммы должны обеспечить переход на первую команду вызываемой подпрограммы, а команда возврата - переход на команду вызывающей программы, следующую за командой вызова. Команды относятся к категории команд управления ходом выполнения программы.
На рис. 17.1а показан пример использования подпрограммы. В данном примере имеется основная программа, которая размещена в оперативной памяти, начиная с адреса 4000. В основной программе существует вызов подпрограммы PROC1, которая размещена в оперативной памяти, начиная с адреса 4500. Когда в процессе выполнения основной программы ядро процессора дойдет до этой команды, оно прервет выполнение основной программы и перейдет на выполнение подпрограммы PROC1, поместив ее начальный адрес 4500 в счетчик команд. В теле подпрограммы PROC1 есть две команды вызова подпрограммы PROC2, которая размещена в оперативной памяти, начиная с адреса 4800. Дойдя до каждой из этих команд, ядро процессора прекратит выполнять подпрограмму PROC1 и перейдет на выполнение подпрограммы PROC2. Встретив в подпрограмме команду RETURN, ядро процессора вернется в вызывающую программу и продолжит ее выполнение с команды, следующей за командой CALL, которая вызвала переход на только что завершенную подпрограмму. Этот процесс схематически показан на рис. 17.1.6.
Необходимо обратить внимание на следующие моменты:
подпрограмма может быть вызвана из любого места других программных
модулей. Таких вызовов может быть сколько угодно.
одна подпрограмма может быть вызвана из другой, которая, в свою очередь, вызвана третьей. Это называется вложенностью (nesting) вызовов. Глубина вложенности теоретически может быть произвольной.
при выполнении возврата из подпрограммы должен обеспечиваться переход
именно на ту команду вызова, которая запустила завершенный сеанс выполнения подпрограммы.
Рис. 17.1. Вложенный вызов подпрограмм:
а - команды вызова и возврата; б - последовательность выполнения команд
Из всего этого следует, что ядро процессора при выполнении команды вызова подпрограммы должно каким-то образом сохранить адрес возврата (т.е. адрес команды вызывающей программы, следующей за выполняемой командой вызова). Существует три места, где можно было бы сохранить адрес возврата:
регистр процессора;
начальный адрес подпрограммы;
верхняя ячейка стека.
Рассмотрим машинную команду CALL X, которая интерпретируется как "вызов подпрограммы, расположенной по адресу X". Если для хранения адреса возврата использовать регистр Rn, то выполнение команды CALL X должно проходить следующим образом (PC - счетчик команд ядра процессора):
В этой записи D - длина текущей команды. Затем адрес возврата оказывается в регистре Rn, откуда его может извлечь вызванная подпрограмма и сохранить где-либо в оперативной памяти для выполнения в дальнейшем возврата в вызывающую программу.
Если будет принято решение сохранять адрес возврата по начальному адресу вызываемой подпрограммы, то при выполнении команды CALL X ядру процессора нужно будет выполнять следующие операции:
Это довольно удобно, поскольку адрес возврата всегда сохраняется в месте, точно известном подпрограмме (точнее, ее разработчику).
Оба описанных подхода работоспособны и используются на практике. Единственным, но довольно существенным их недостатком является невозможность реализации реентерабельных подпрограмм. Реентерабельность подпрограммы означает, что она может быть вызвана повторно еще до завершения текущего вызова. Например, это происходит, если внутри подпрограммы вызывается другая подпрограмма, которая, в свою очередь, вызывает первую. Реентерабельными должны быть и подпрограммы, реализующие рекурсивные алгоритмы.
Более общим, и более надежным, подходом является использование для хранения адреса возврата стека. Когда ядро процессора выполняет команду вызова подпрограммы, адрес возврата помещается в верхнюю ячейку стека, а когда он выполняет команду возврата, извлекает этот адрес из верхней ячейки стека.
Стеки
Стек - это список элементов данных, обычно слов или байтов, доступ к которым ограничен следующим правилом: элементы этого списка могут добавляться только в его конец и удаляться только из конца. Конец списка называется вершиной стека, а его начало - дном. Такую структуру иногда называют магазином. Представьте себе стопку подносов в столовой. Клиенты берут подносы сверху, работники столовой, добавляя чистые подносы, тоже кладут их на верх стопки. Этот механизм хранения хорошо описывается емкой фразой «последним вошел - первым вышел» (Last In First Out, LIFO), означающей, что элемент данных, помещенный в стек последним, удаляется из него первым. Операцию помещения нового элемента в стек часто называют его проталкиванием (push), а операцию извлечения последнего элемента из стека называют его выталкиванием (pop).
Хранящиеся в оперативной памяти компьютера данные могут быть организованы в виде стека, так чтобы последовательные элементы располагались друг за другом. Предположим, что первый элемент хранится по адресу BOTTOM, а когда в стек помещаются новые элементы, они располагаются в порядке уменьшения последовательных адресов. Таким образом, стек растет в направлении уменьшения адресов, что является весьма распространенной практикой.
На рис. 17.2 показано, как располагается в памяти компьютера стек, элементы которого занимают по одному слову.
На «дне» он содержит числовое значение 43, а на вершине - 28. Для отслеживания адреса вершины стека используется регистр ядра процессора, называемый указателем стека (Stack Pointer, SP). Это может быть один из регистров общего назначения или же регистр, специально предназначенный для этой цели.
Рис. 17.2. Стек слов в оперативной памяти
Если предположить, что оперативная память адресуется побайтно и слово имеет длину 32 разряда, операцию проталкивания в стек можно реализовать так:
Move NEWITEM.(SP),
где команда Subtract вычитает исходный операнд 4 из результирующего операнда, содержащегося в регистре SP, и помещает результат в регистр SP. Эти две команды помещают слово, хранящееся по адресу NEWiTEM, на вершину стека, предварительно уменьшая указатель стека на 4. Операция выталкивания из стека может быть реализована так:
Эти две команды перемещают значение, хранившееся на вершине стека, в другое место оперативной памяти, по адресу ITEM, а затем уменьшают указатель стека на 4, чтобы он указывал на тот элемент, который теперь располагается на вершине стека. Результат выполнения каждой из этих операций для стека, показанного на рис. 17. 2, приведен на рис. 17.3.
 |
Рис. 17.3. Результат выполнения операций со стеком
Если в архитектуре поддерживаются режимы автоинкрементной и автодекрементной адресации, для помещения нового элемента в стек достаточно команды
Move NEWITEM,-(SP),
а выталкивание элемента из стека можно выполнить посредством команды
Move (SP)+,ITEM.
Когда стек используется программой, для него обычно выделяется фиксированное количество ячеек оперативной памяти. В этом случае нужно проследить за тем, чтобы программа не пыталась помещать новые элементы в стек, достигший своего максимального размера. Кроме того, она не должна пытаться вытолкнуть элемент из пустого стека, что могло бы произойти в случае логической ошибки.
Предположим, что стек заполняется, начиная с адреса 2000 (BOTTOM) до 1500 и далее. Первоначально в регистр, играющий роль указателя стека, загружается значение 2004. Напомним, что перед помещением в стек нового элемента данных из значения SP каждый раз вычитается 4. Поэтому начальное значение 2004 означает, что первый элемент стека будет иметь адрес 2000. Для предотвращения попыток помещения элемента в полный стек или удаления элемента из пустого стека нужно несколько усложнить реализацию операций проталкивания и выталкивания элемента. Для выполнения каждой из этих операций указаннойвыше команды недостаточно - ее нужно заменить последовательностью команд, приведенной в таблице 17.1.
Команда сравнения Compare src,dst выполняет операцию - и устанавливает флаги условий в соответствии с полученным результатом. Она не изменяет значения ни одного из операндов. Фрагмент а таблицы 17.1 демонстрирует выталкивание элемента из стека, а фрагмент б этой же таблицы - помещение элемента в стек при реализации контроля пустого и полного стека при выполнении операций проталкивания и выталкивания элемента.
Таблица 17.1
| Метка | Команда | Операнды |
При решении новых задач можно попытаться воспользоваться ранее написанными программами. Алгоритм, ранее разработанный и целиком используемый в составе других алгоритмов, называется вспомогательным . Применение вспомогательных алгоритмов позволяет разбить задачу на части, структурировать ее.
Вся программа условно может быть разделена на две части: основную и вспомогательную. В основной части производится простейшая обработка информации, организуется обращение к разным вспомогательным модулям (подпрограммам) .
Вспомогательный алгоритм тоже может вызывать другие вспомогательные, длина такой цепочки вызовов теоретически не ограничена. Здесь и далее следующие пары слов используются как синонимы: алгоритм и программа, вспомогательный алгоритм и подпрограмма, команда и оператор, программа и модуль. Вспомогательными и основными алгоритмы являются не сами по себе, а по отношению друг к другу.
При использовании вспомогательных алгоритмов необходимо учитывать способ передачи значений исходных данных для них и получения результата от них. Аргументы вспомогательного алгоритма это переменные, в которых должны быть помещены исходные данные для решения соответствующей подзадачи. Результаты вспомогательного алгоритма это также переменные, где содержаться результаты решения этих подзадач, а также результатом может быть конкретное действие, которое совершает компьютер под действием подпрограммы.
Подпрограммы могут быть двух видов: подпрограмма без параметров и подпрограмма с параметрами. Обращение к подпрограмме может быть организовано из любого места основной программы или другой подпрограммы сколько угодно раз.
При работе с подпрограммами важными являются понятия формальных и фактических параметров . Формальные параметры это идентификаторы входных данных для подпрограммы. Если формальные параметры получают конкретные значения, то они называются фактическими . Формальные параметры могут получить конкретные значения только в той программе, где производится обращение к данному модулю-подпрограмме. Тип и порядок записи фактических параметров должны быть такими же, как и формальных параметров. В противном случае результат работы программы будет непредсказуемым. Из этого следует, что фактические параметры используются при обращении к подпрограмме из основной, а формальные параметры только в самом модуле.
Подпрограмма с параметрами используется для записи многократно повторяющихся действий при разных исходных данных.
При составлении подпрограмм с параметрами надо соблюдать следующие правила:
1) каждая подпрограмма имеет свое имя и список формальных параметров;
2) процедура из основной программы вызывается командой вызова, которая по форме ничем не отличается от вызова команды исполнителя. Результат присваивается одной или нескольким переменным, которые находятся в списке формальных параметров. Но результатом могут быть, конечно, не только значения переменных, но какое либо действие, выполненное ЭВМ.
Пример 1. Используем алгоритм нахождения наибольшего общего делителя двух натуральных чисел в качестве вспомогательного при решении задачи: составить программу вычитания дробей (a , b , c , d натуральные числа). Результат представить в виде обыкновенной несократимой дроби.
Подпрограмма.
- Ввести натуральные числа M, N.
- Если M=N, перейти к п. 5, иначе к следующему пункту.
- Если M>N, то M:=M-N, иначе N:=N-M.
- Перейти к п. 2.
- Передать значение M в основную программу.
- Конец подпрограммы.
Основная программа.
- Ввести значения A, B, C, D.
- E:=A*D - B*C.
- F:= B*D.
- Если E=0, вывести значение E и перейти к п. 9, иначе перейти к следующему пункту.
- M:=|E|, N:=F, перейти к подпрограмме вычисления НОД.
- G:= M.
- E и F нацело разделить на G.
- Вывести значения E и F на печать.
- Конец программы.
Как видно из примера, объявление подпрограммы-функции находится в разделе описаний прототипов функций, а реализация после основной функции main . В заголовке подпрограммы содержится список формальных параметров с указанием их типа, которые условно можно разделить на входные и выходные (перед ними стоит &). Вообще при обращении к функции со списком параметров без &, внутри функции используются копии параметров, которые после выполнения удаляются. Знак & указывает компилятору что необходимо использовать саму переменную, а не ее копию. При обращении к функции указывается ее имя и список фактических параметров. Формальные и фактические параметры должны соответствовать по количеству и по типу.
Описание функции в С++ осуществляется следующим образом:
Тип_возвращаемого_значения ();
Например,
Void Nod(int e, int f, int &k); int f1(float a); long f2();
Функция всегда возвращает единственное значение. Как видно из примера 1, мы использовали тип void в качестве возращаемого типа. Т.е. указали компилятору, что наша функция не возвращает никакого значения.
Покажем, как изменится подпрограмма из примера, если ее записать в виде функции, возвращающей само значение НОД (без использования возвращаемой переменной).
Int Nod(int m, int n) { while (m!=n) if (m > n) m -=n; else n -= m; return (n); }
Итак, в теле функции хотя бы один раз встречается команда return, которая указывает, какое значение вернуть в качестве значения функции.
Вызов функции в основной будет следующим:
G = Nod(fabs(e), f);
Вообще, вызов функции может присутствовать в выражении, стоящем: в правой части операции присваивания, в операторе вывода, в качестве фактического параметра в вызове другой подпрограммы и т.д.
При решении задач целесообразно проанализировать условие, записать решение в крупных блоках (не являющихся операторами C++), детализировать каждый из блоков (записав в виде блоков, возможно, по-прежнему не операторов C++), и т.д., продолжать до тех пор, пока каждый из блоков не будет реализован с помощью операторов языка.
Пример 2. Дано натуральное число n . Переставить местами первую и последнюю цифры этого числа.
Здесь необходимо детализировать функцию Number, возвращающую количество цифр в записи натурального числа (т.к. функция Impossible содержит ее вызов, то в разделе описаний прототипов функция Number должна ей предшествовать).
Возможны также подпрограммы, которые вызывают сами себя. Они называются рекурсивными . Создание таких подпрограмм является красивым приемом программирования, но не всегда целесообразно из-за чрезмерного расхода памяти ЭВМ.
Пример 3. Найти максимальную цифру в записи данного натурального числа.
При создании функции Maximum было использовано следующее соображение: если число состоит из одной цифры, то она является максимальной, иначе если последняя цифра не является максимальной, то ее следует искать среди других цифр числа. При написании рекурсивного алгоритма следует позаботиться о граничном условии, когда цепочка рекурсивных вызовов обрывается и начинается ее обратное «раскручивание». В нашем примере это условие N
Более подробно о рекурсии говорится в следующей статье .
Контрольные вопросы и задания- Какие алгоритмы называют вспомогательными?
- Какое количество вспомогательных алгоритмов может присутствовать в основном алгоритме?
- Можно ли вспомогательные алгоритмы, написанные для решения данной задачи, использовать при решении других задач, где их применение было бы целесообразно?
- Какие параметры называют формальными? фактическими?
- Какое соответствие должно соблюдаться между формальными и фактическими параметрами?
- Может ли фактических параметров процедуры (функции) быть больше, чем формальных? А меньше?
- Существуют ли подпрограммы без параметров?
- Существуют ли ограничения на число параметров подпрограмм? Если нет, то чем же всё-таки ограничивается это количество в С++?
- В каком разделе объявляются и в каком реализуются подпрограммы в С++?
- Какого типа может быть значение функции?
- Расскажите о методе последовательной детализации при разработке программ.
- Какие подпрограммы называют рекурсивными?
- Что такое граничное условие при организации рекурсивной подпрограммы?