Анализ подпрограмм

Анализ подпрограммы — это пошаговое прослеживание того, какие значения получают параметры и локальные переменные, в каком порядке выполняются вызовы и какое значение возвращается. Такой способ позволяет надёжно решать задания, где нужно определить результат работы программы или последовательность вызовов.

Что происходит при вызове подпрограммы

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

Формальный параметр записан в объявлении подпрограммы, а фактический параметр — выражение или переменная, указанная при вызове. Например, в f(2 * x) выражение 2 * x является фактическим параметром, а имя a в function f(a) — формальным.

Если параметр передаётся по значению, подпрограмма получает копию. Изменение этой копии не меняет исходную переменную. При передаче по ссылке параметр связан с исходной переменной, поэтому присваивание внутри подпрограммы может изменить её.

Области видимости и локальные переменные

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

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

Порядок выполнения и граф вызовов

Структура программы задаёт порядок команд: сначала выполняется очередной оператор, затем — вызванная им подпрограмма. Если функция A вызывает B, а B вызывает C, выполнение идёт по цепочке A → B → C, а после завершения C управление возвращается в B, затем в A.

Для ручного решения полезно строить не только граф, но и стек вызовов. В него записывают текущую цепочку, например A → B → D. Возвращаясь из D, удаляют последний элемент и продолжают B с команды после вызова D.

Алгоритм трассировки

В экзаменационном задании не пытайтесь сразу вычислить всё выражение. Разделите работу на состояния и фиксируйте каждое изменение. Особенно важно различать присваивание и возврат: команда x := f(a) сначала полностью выполняет f(a), а затем записывает возвращённое значение в x.

1. Выпишите начальные значения всех переменных.
2. Найдите первый выполняемый вызов и передайте ему фактические значения.
3. Создайте отдельную запись параметров и локальных переменных этого вызова.
4. Выполняйте команды сверху вниз, раскрывая вложенные вызовы только в момент их появления.
5. Запишите результат return или присваивания имени функции.
6. Вернитесь к вызывающей подпрограмме и продолжите со следующего оператора.
7. После завершения основного вызова определите требуемый вывод или итоговую переменную.

Разобранный пример

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

1function F(a)
2    b := a + 1
3    if a > 1 then
4        return b + F(a - 2)
5    else
6        return b
7
8x := F(5)

Формулы и контроль результата

Если подпрограмма возвращает результат через выражение, результат внешнего вызова вычисляется после завершения внутреннего. Для последовательных вызовов полезно записывать зависимость справа налево.

В этой записи \(g(a)\) — базовый случай, \(h(a)\) — часть результата текущего вызова, а \(q(a)\) — новый параметр. Для обычных, нерекурсивных подпрограмм аналогичный контроль выполняют по цепочке возвратов: сначала считают самый глубокий вызов, затем подставляют его результат.