правило, в соответствии с которым каждый рекур- cd(314i59 271828)

сивный вызов должен использовать меньшие зна- gc<i(271828, 42331)

чения аргументов, и поэтому для ее проверки gcd(4233l, 17842)

нельзя использовать метод математической ин- gc<i(17842 , 6647)

дукции. Действительно, неизвестно, завершается 1

gcd(4458, 2099)

ли это вычисление для каждого значения N, по- gcd(2099 350)

скольку значение не имеет никаких пределов. gcd(350 , 349)

Для меньших целочисленных значений, которые gcd(349, 1)

могут быть представлены значениями типа int, gcdCl, 0)

можно проверить, что программа прерывается рсуноК 5.2 ПРИМЕР ПРИМЕНЕНИЯ (см. рис. 5.1 и упражнение 5.4), но для больших ддроритМА ЭВКЛИДА целочисленных значений (скажем, для 64-разряд- вложенная последовательность

ных слов), не известно, входит ли эта программа вызовов функции иллюстрирует работу в бесконечный цикл. алгоритма Эвклида, показывая, что

Программа 5.3 - компактная реализация алго- чиспа 314159и 271828являются ритма Евклида для отыскания наибольшего обще- взаимно простыми. го делителя для двух целых чисел. Алгоритм основывается на наблюдении, что наибольший общий делитель двух целых чисел х v\ у, когда X > у, совпадает с наибольшим общим делителем числа у х по модулю у (остатка от деления х на у). Число г делит и х и тогда, и только тогда, когда оно делит и и X mod у (х по модулю у), поскольку х равно х mod у плюс число, кратное у. Рекурсивные вызовы, созданные для примера выполнения этой программы, показаны на рис. 5.2. При реализации алгоритма Эвклида глубина рекурсии зависит от арифметических свойств аргументов (она связана с ними логарифмической зависимостью).

Программа 5.3 Алгоритм Эвклида

Это один из наиболее давно известных алгоритмов, разработанный свыше 2000 лет назад - рекурсивный метод отыскания наибольшего общего делителя двух целых чисел.

int gcd(int m, int n) {

if (n == 0) return m; return gcd(rt, m % n) ;

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

Программа 5.4 Рекурсивная программа для оценки префиксных выражений

Для оценки префиксного выражения либо осуществляется преобразование числа из ASCII в двоичную форму (в цикле while) в конце, либо над двумя операндами, которые оцениваются рекурсивно, выполняется операция, указанная первым символом

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

char *а; int i; int evalО { int X = 0; while (a[i] == ) i++; if (a[i] == + )

{ i++; return eval() + eval(); if (a[i] == *)

{ i++; return eval() * eval(); while ((ati] >= O && (atH <=

9))

X = 10*x return x;

+ (ati++]-0);

Пример обработки префиксного выражения программой 5.4 показан на рис. 5.3. Множество рекурсивных вызовов маскируют сложную серию вычислений. Подобно большинству рекурсивных программ, работу этой программы проще всего понять, воспользовавшись методом индукции: полагая, что она работает правильно применительно к простым выражениям, можно предположить, что это справедливо и применительно к сложным выражениям. Программа представляет собой простой пример рекурсивного нисходящего анализатора - аналогичный процесс используется для преобразования программ С++ в машинные коды.

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

В принципе, любой цикл for можно заменить эквивалентной рекурсивной программой. Часто ре-

evalO * + 7**46 + 8Э5 evalO + 7**46 + 89 eval О 7

evalO * * 4 6 + 8 9 evalO * 4 6 eval О 4 evalС) 6 retiinx 24 - 4*6 evalO +89 val() 8 evalO 9 retiim 17 = 8 + 9 retTirn 408 - 24*17 return 415 = 7+408 eval О 5

return 2075 = 415*5

РИСУНОК 5.3 ПРИМЕР ОЦЕНКИ ПРЕФИКСНОГО ВЫРАЖЕНИЯ

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

курсивная программа предоставляет более естественный способ выражения вычисления, чем цикл for, поэтому можно воспользоваться преимуществами механизма, предоставляемого системой, поддерживающей рекурсию. Однако, этот подход имеет один скрытый недостаток, о котором следует помнить. Как должно быть понятно из примеров, приведенных на рис. 5.1-5.3, при выполнении рекурсивной программы вызовы функций вкладываются один в другой, пока не будет достигнута точка, когда вместо рекурсивного вызова выполняется возврат. В больщинстве сред программирования такие вложенные вызовы функций реализуются с помощью эквивалента встроенных стеков. Сущность подобного рода реализаций будет исследоваться на протяжении данной главы. Глубина рекурсии - это максимальная степень вложенности вызовов функций в ходе вычисления. В общем случае глубина будет зависеть от вводимых данных. Например, глубина рекурсии в примерах, приведенных на рис. 5.2 и 5.3, составляет, соответственно, 9 и 4. При использовании рекурсивной профаммы следует учитывать, что среда программирования должна поддерживать стек, размер которого пропорционален глубине рекурсии. При рещений сложных задач необходимый для этого стека объем памяти может заставить отказаться от использования рекурсивного рещения.

Структуры данных, построенные из узлов с указателями, рекурсивны изначально. Например, определение связных списков в главе 3 (определение 3.3) является рекурсивным. Следовательно, рекурсивные программы предоставляют естественные реализации для многих часто используемых функций, работающих с такими структурами данных. Профамма 5.5 содержит четыре примера. Подобные реализации в книге используются часто, в основном потому, что их гораздо проще понять, чем их нерекурсивные аналоги. Однако, рекурсивные программы, подобные программе 5.5, следует использовать обдуманно при обработке очень больших списков, поскольку глубина рекурсии может быть пропорциональна длине списков и, соответственно, требуемый для рекурсивного стека объем памяти может превысить допустимые пределы.

Программа 5.5 Примеры рекурсивных функций для связных списков

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

Первая функция count подсчитывает количество узлов в списке. Вторая, traverse, вызывает функцию visit для каждого узла списка, с начала до конца. Обе функции легко реализуются с помощью цикла for или while. Третья функция traverseR не имеет простого итеративного аналога. Она вызывает функцию visit для каждого узла списка, но в обратном порядке.

Четвертая функция remove удаляет из списка все узлы с заданным значением элемента. Основа реализации этой функции - изменение связи х = x->next в узле, предшествующем удаляемому, что возможно благодаря использованию параметра ссылки. Структурные изменения для каждой итерации цикла while совпадают с показанными на рис. 3.3, в данном случае и х, и t ссылаются на один и тот же узел.

int count(link х) {

if (х = 0) return 0; return 1 + count(x->next);