Программирование на языке C




Рекурсия - часть 2


i n-1 w n-1 j + | -------->-+|+--------->+ | n-1| | I | Ш | | + / \ / \ / \ +-/-----\-+ / \ +-/-----\-+ ==+----|----+===/=========\====+----|----+====== +-------------->-------------+ П Рис.32. Схема решения задачи о Ханойских башнях.

Ниже приведена программа, которая вводит число n и печатает список перемещений, решающая задачу о Ханойских башнях при количестве дисков n. Используется внутренняя рекурсивная процедура tn(n,i,j,w), печатающая перемещения, необходимые для переноса n дисков со стержня i на стержень j с использованием вспомогательного стержня w при {i,j,w} = {1,3,2}.

/* ханойские башни */ #include

main() /* вызывающая */ { void tn(int, int, int, int); /* функция */ int n; scanf(" %d",&n); tn(n,1,2,3); }

void tn(int n, int i, int j, int w) /* рекурсивная */ { if (n>1) /* функция */ { tn (n-1,i,w,j); tn (1,i,j,w); tn (n-1,w,j,i); } else printf(" \n %d -> %d",i,j); return ; }

Последовательность вызовов процедуры tn при m=3 иллюстрируется древовидной структурой на рис.33. Каждый раз при вызове процедуры tn под параметры n, i, j, w выделяется память и запоминается место возврата. При возврате из процедуры tn память, выделенная под параметры n, i, j, w, освобождается и становится доступной память, выделенная под параметры n, i, j, w предыдущим вызовом, а управление передается в место возврата.

Рис.33. Последовательность вызовов процедуры tn.

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

Предположим, что имеется ситуация:

main() /* вызывающая функция */ { ... f() ...} f() /* рекурсивная функция */ { ... f() ...}

Здесь в функции main вызывается рекурсивная функция f. Требуется заменить описание функции f и ее вызова на эквивалентный фрагмент программы, т.е. удалить функцию f.

Пусть рекурсивная функция f имеет параметры Р1,Р2,...,Рs, внутренние переменные V1,V2,...,Vt и в функциях main и f имеется k обращений к функции f. Для удаления такой функции требуются следующие дополнительные объекты:

- переменные AR1,AR2,...,ARs, содержащие значения фактических параметров при вызове функции f (типы переменных должны соответствовать типам параметров Р1,Р2,...,Рs);

- переменная rz для вычисляемого функцией f результата (тип переменных совпадает с типом возвращаемого значения функции f);

- стек, содержащий в себе все параметры и все внутренние переменные функции f, а также переменную lr типа int, для хранения точки возврата, и переменную pst типа указатель, для хранения адреса предыдущего элемента стека;

- указатель dl для хранения адреса вершин стека;

- промежуточный указатель u для операций над стеком;

- k новых меток L1,...,Lk для обозначенных точек возврата;

- метка jf, используемая для обхода модифицированного тела функции f;

- промежуточная переменная l типа int для передачи номера точки возврата.

Чтобы получить эквивалентную нерекурсивную программу без функции f, необходимо выполнить следующие действия:

1. Убрать объявление функции f в функцию main;

2. Добавить в функции main объявления переменных AR1,AR2,...,ARs,RZ, объявления стека ST и указателей dl и u:




Содержание  Назад  Вперед