Для оценки префиксного выражения либо осуществляется преобразование числа из ASCII в двоичную форму (в цикле while) в конце, либо над двумя операндами, которые оцениваются рекурсивно, выполняется операция, указанная первым символом выражения. Эта функция является рекурсивной, однако использует глобальный массив, содержащий выражение и индекс текущего символа выражения. Индекс изменяется после вычисления каждого подвыражения.
char *a; 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 (<a[i] >= '0') &&(a[i] <= '9'))
x = 10*x + (a[ i++ ] - ` 0 `);
return x;
}
Пример обработки префиксного выражения программой 4 показан на рис. 9. Множество рекурсивных вызовов маскируют сложную серию вычислений. Подобно большинству рекурсивных программ, работу этой программы проще всего понять, воспользовавшись методом индукции: полагая, что она работает правильно применительно к простым выражениям, можно предположить, что это справедливо и применительно к сложным выражениям.
Программа представляет собой простой пример рекурсивного нисходящего анализатора — аналогичный процесс используется для преобразования программ C++ в машинные коды.
Реальная проверка правильности оценки выражения программой 4 — гораздо более сложная задача, нежели проверка работы описанных функций с целочисленными аргументами, и в этой книге встретятся еще более сложные рекурсивные программы и структуры данных. Соответственно, мы не ставим перед собой идеалистичной задачи предоставления полных индуктивных доказательств правильности каждой создаваемой рекурсивной про-
граммы. В данном случае способность программы "узнавать", как следует разделять операнды в соответствии с заданным оператором, вначале кажется непостижимой (возможно потому, что не сразу по-
понятно, как выполнить это разделение на верхнем уровне). Однако в действительности вычисление достаточно понятно (поскольку нужная ветвь программы при каждом вызове функции однозначно
определяется первым символом выражения).
В принципе, любой цикл for можно заменить эквивалентной рекурсивной программой. Часто рекурсивная программа предоставляет более естественный способ выражения вычисления, чем цикл for, поэтому можно воспользоваться преимуществами механизма, предоставляемого системой, поддерживающей рекурсию. Однако, этот подход имеет один скрытый недостаток, о котором следует помнить. Как должно быть понятно из примеров, приведенных на рис. 7-9, при выполнении рекурсивной программы вывызовы функций вкладываются один в другой, пока не будет достигнута точка, когда
вместо рекурсивного вызова выполняется возврат. В большинстве сред программирования, такие вложенные вызовы функций реализуются с помощью эквивалента встроенных стеков. Сущность подобного рода реализаций будет исследоваться на протяжении данной главы. Глубина рекурсии — это максимальная степень вложенности вызовов функций в ходе вычисления. В общем случае глубина будет зависеть от вводимых данных. Например, глубина рекурсии в примерах, приведенных на рис. 8 и 9, составляет, соответственно, 9 и 4. При использовании рекурсивной программы
следует учитывать, что среда программирования должна поддерживать стек, размер которого пропорционален глубине рекурсии. При решении сложных задач необходимый для этого стека объем памяти может заставить отказаться от использования рекурсивного решения.
Структуры данных, построенные из узлов с указателями, рекурсивны изначально. Рекурсивные программы предоставляют естественные реализации для многих часто используемых функций, работающих с такими структурами данных. Программа 5 содержит четыре примера. Подобные реализации в книге используются часто, в основном потому, что их гораздо проще понять, чем их нерекурсивные аналоги. Однако, рекурсивные программы, подобные программе 5, следует использовать обдуманно при обработке очень больших списков, поскольку глубина рекурсии может быть пропорциональна длине списков и, соответственно, требуемый для рекурсивного стека объем памяти может превысить допустимые пределы.
Рис.9. Пример оценки префиксного выражения