void traverse(link h, void visit(link)) {

if (h == 0) return; visit(h);

traverse(h->next, visit);

void traverseR(link h, void visit(link)) {

if (h == 0) return; traverseR(h->next, visit); visit(h);

void remove (links x. Item v) {

while (x != 0 && x->item == v)

{ link t = x; X = x->next; delete t; } if (x != 0) remove (x->next, v) ;

Некоторые среды программирования автоматически выявляют и исключают листовую (оконечную) рекурсию (tail recursion); когда последним действием функции является рекурсивный вызов, увеличение глубины рекурсии вовсе не обязательно. Это усовершенствование эффективно преобразовало бы функции подсчета, обхода и удаления, используемые в программе 5.5 в циклы, но оно не применимо к функции обхода в обратном направлении.

В разделах 5.2 и 5.3 рассматриваются два семейства рекурсивных алгоритмов, представляющие важные случаи вычислений. Затем, в разделах 5.4-5.7 будут исследоваться рекурсивные структуры данных, служащие основой для большой группы алгоритмов.

Упражнения

о 5.1 Напишите рекурсивную программу для вычисления Ig(A).

5.2 Измените программу 5.1 для вычисления Л! mod Л/, чтобы переполнение больше не играло никакой роли. Попытайтесь выполнить программу для Л/ = 997 и N = 10 10, 10 и 10, чтобы увидеть, как используемая система программирования обрабатывает рекурсивные вызовы с большой глубиной вложенности.

О 5.3 Приведите последовательности значений аргументов, получаемые в результате вызова программы 5.2 для каждого из целых чисел от 1 до 9.

5.4 Найдите значение TV < 10, при котором профамма 5.2 выполняет максимальное количество рекурсивных вызовов.

О 5.5 Создайте нерекурсивную реализацию алгоритма Эвклида.

о 5.6 Приведите рисунок, соответствующий рис. 5.2, для результата выполнения алгоритма Эвклида применительно к числам 89 и 55.

о 5.7 Укажите глубину рекурсии алгоритма Эвклида при вводе двух последовательных чисел Фибоначчи (/> и /)v+i).

О 5.8 Приведите рисунок, соответствующий рис. 5.3, для результата оценки префиксного выражения в случае ввода + * * 12 12 12 144.

5.9 Создайте рекурсивную программу для оценки постфиксных выражений.

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

о 5.11 Создайте рекурсивную программу, которая преобразует корневые выражения в постфиксные.

о 5.12 Создайте рекурсивную программу, которая преобразует постфиксные выражения в инфиксные.

5.13 Создайте рекурсивную программу для решения задачи Иосифа Флавия (Josephus) (см. раздел 3.3).

5.14 Создайте рекурсивную программу, которая удаляет конечный узел из связного списка.

о 5.15 Создайте рекурсивную программу для изменения на обратный порядка следования узлов в связном списке (см. программу 3.7). Совет: используйте глобальную переменную.

5.2 Разделяй и властвуй

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

Давайте в качестве примера рассмотрим задачу отыскания максимального из N элементов, сохраненных в массиве а[0], a[N-l]. Эту задачу можно легко выполнить за один проход массива демонстрируется в примере:

for (t = а[0], i = 1; i < N; i++) if (a[i] > t = a[i];

Рекурсивное решение типа разделяй и властвуй , приведенное в программе 5.6 - еще один простой (хотя и совершенно иной) алгоритм решения той же задачи; он использовался только с целью иллюстрации концепции разделяй и властвуй .

Программа 5.6 Применение алгоритма разделяй и властвуй

для отыскания максимума

Эта функция делит массив а[1], а[г] на массивы а[1].....а[т] и а[т+1].....а[г],

находит максимальные элементы в обоих частях (рекурсивно) и возвращает больший из них в качестве максимального элемента всего массива. В программе предполагается, что Item - тип первого класса, для которого операция > определена. Если размер массива является четным числом, обе части имеют одинаковые размеры, если же нечетным, эти размеры различаются на 1.

Item inax(Item а[] , int 1, int г) {

if (1 == г) return а[1] ;

int m = (l+r)/2;

Item u = max (a, 1, m) ;

Item V = niax(a, m+1, r) ;

If (u > v) return u; else return v;

Чаще всего подход разделяй и властвуй используют из-за того, что он обеспечивает более быстрые рещения, чем простые итерационные алгоритмы (в конце главы рассматриваются несколько примеров таких алгоритмов); кроме того, данный подход заслуживает подробного исследования, поскольку он способствует пониманию сущности определенных базовых вычислений.

На рис. 5.4 показаны рекурсивные вызовы, выполняемые при запуске программы 5.6 применительно к примеру массива. Структура программы кажется сложной, но обычно об этом можно не беспокоиться - для проверки программы мы полагаемся на метод математической индукции, а для анализа ее производительности используется рекуррентное соотнощение.

Как обычно, сам код предполагает проверку правильности вычисления методом индукции:

Он явно и немедленно отыскивает максимальный элемент массива, размер которого равен 1.

Для N > 1 код разделяет массив на два, размер каждого из которых меньше N, исходя из индуктивного предложения, находит максимальные элементы в обеих частях и возвращает большее из этих двух значений, которое должно быть максимальным значением для всего массива.

01234S6789 10 Т I NYEXAMPLE

Y тах(0, 10) Y тахСО, 5) Т юахСО, 2) Т тахСО, 1) Т тах(0, 0) I maxd, 1) N max(2, 2) У шахСЗ, 5) Y mai(3, 4) У тах(3, 3) Е тах(4. 4) X шах(5, 5) Р тахСб, 10) Р юахСб, 8) М тах(6. 7) А тах(6, б) М тах(7, 7) Р max(8, 8) L maxO, 10) L max(9, 9) E max(10. 10)

РИСУНОК 5.4 РЕКУРСИВНЫЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧИ ОТЫСКАНИЯ МАКСИМУМА

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

Более того, рекурсивную структуру программы можно использовать для исследования характеристик ее производительности.

Лемма 5.1 Рекурсивная функция, которая разделяет задачу размерности N на две независимые (непустые) решающие ее части, рекурсивно вызывает себя менее N раз.

Если одна часть имеет размерность к, а другая - N-k, то общее количество рекурсивных вызовов используемой функции равно

7:v = 7; + 7;v- + l, приЛ>1;Г, =0

Решение Т] = N - 1 можно получить непосредственно методом индукции. Если сумма размеров частей меньше N, доказательство того, что количество вызовов меньше чем - 1 вытекает из тех же рассуждений по методу индукции. Аналогичными рассуждениями можно подтвердить справедливость данного утверждения и для общего случая (см. упражнение 5.20).