Ниже приведена программа, которая вводит
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:
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий