Уроки 41 - 42
§24. Процедуры
Содержание урока
Процедуры в других языках программирования. Рекурсия
Практическая работа № 20 «Процедуры»
Практическая работа № 21 «Рекурсивные процедуры»
Процедуры в других языках программирования
Рекурсия
Процедура printLine с одним параметром на языках Python и С может быть записана так:
В языке Python объявление процедуры начинается ключевым словом def. Тип параметра указывать не нужно, он определяется автоматически. Тело процедуры записывается с отступом вправо, так же, как тело цикла и условного оператора. Вывести п одинаковых символов можно без цикла, построив сразу нужную строку с помощью «умножения» символа '-' на n.
Программа на языке С очень похожа на программу на Паскале. Признак процедуры — слово void в заголовке (вместо procedure на Паскале). Тело процедуры заключено в фигурные скобки. Стандартная функция putchar выводит на экран один символ.
Рекурсия
Составим процедуру, которая выводит на экран двоичную запись натурального числа. Поскольку число будет меняться, это должна быть процедура с параметром:
Вспомним алгоритм перевода числа в двоичную систему: нужно делить число на 2, каждый раз выписывая остаток от деления, пока не получится 0. На алгоритмическом языке алгоритм можно записать так:
нц пока <> 0
вывод mod(n,2)
n:= div(n,2)
кц
Проверьте вручную работу этого алгоритма для числа 6. Удалось ли вам получить правильный ответ? Почему?
Проблема только в том, что первой мы получаем последнюю цифру двоичной записи, поэтому остатки выводятся в обратном порядке (не так, как нужно).
Есть разные способы решения этой задачи, которые сводятся к тому, чтобы запоминать остатки от деления (например, в символьной строке) и затем, когда результат будет полностью получен, вывести его на экран. Однако можно применить ещё один красивый подход. Идея такова: чтобы вывести двоичную запись числа п, нужно сначала вывести двоичную запись числа div(n,2), а затем — его последнюю двоичную цифру, которая вычисляется как mod(n,2).
Что же получилось? Прочитайте ещё раз фразу, выделенную курсивом в предыдущем абзаце. Выходит, что для того, чтобы решить задачу для исходного числа, нужно предварительно решить ту же самую задачу для меньшего числа div(n,2).
Такой алгоритм очень просто программируется:
У нас получилось, что процедура printBin вызывает сама себя! Такой приём в программировании называется рекурсией, а процедура — рекурсивной.
Рекурсивная процедура — это процедура, которая вызывает сама себя.
Проверьте с помощью отладчика 1) в пошаговом режиме, что произойдёт при вызове этой процедуры.
1) Для входа в процедуру в пошаговом режиме отладчика используйте клавишу F7.
Приведённая процедура printBin ошибочна, вернее, она не доделана. Представим себе, что мы передали процедуре число 2. Сначала она вызывает сама себя для значения div(2,2) = 1, затем — для значения div(l,2) = 0, и потом ещё бесконечно много раз для нуля. Такие вызовы никогда не закончатся, и программа зациклится. Чтобы этого не произошло, нужно выйти из процедуры (и закончить эти вложенные вызовы), когда значение параметра станет равно нулю:
В алгоритмическом языке для выхода из процедуры используется оператор выход, а в языке Паскаль — оператор exit.
Убедимся, что процедура остановится при любом заданном натуральном числе. Действительно, при каждом вложенном вызове значение параметра уменьшается (делится нацело на 2). В результате когда-нибудь оно обязательно станет равно нулю, и вложенные вызовы закончатся.
Сформулируйте алгоритм вывода цепочки одинаковых символов, используя рекурсию. Напишите рекурсивную процедуру. Попробуйте придумать два варианта решения.
Следующая страница 
Выводы
Cкачать материалы урока
