Обсудив возможности рекурсии, вернемся к бинарным деревьям. Алгоритмы, используемые для добавления, исключения и поиска элементов в дереве, зависят не от количества узлов в дереве, а от его глубины, обеспечивая эффективность вычислений.
Рассмотрим задачу: как обойти дерево, отметив каждый узел один раз? Естественный порядок перенумерования элементов линейных списков от начала до конца не может быть применен для бинарных деревьев. Рассмотрим три метода прохождения, которые определяются рекурсивно:
рис. 24 - Прохождение бинарного дерева
- попасть в корень;
- пройти в прямом порядке левое поддерево;
- пройти в прямом порядке правое поддерево.
Для дерева,получим: ABDGJKEHILMCF
2. Прохождение в симметричном порядкеhttp://www.k-press.ru/cs/2000/3/trees/trees.asp
- пройти в симметричном порядке левое поддерево;
- попасть в корень;
- пройти в симметричном порядке правое поддерево.
Обход дерева даст следующую последовательность узлов: JGKDBHELIMACF
- пройти в обратном порядке левое поддерево;
- пройти в обратном порядке правое поддерево;
- попасть в корень.
Обойдя наше дерево, получим: JKGDHLMIEBFCA
Кроме выше указанных процедур приведены следующие процедуры и функции:
· процедура включения в стек при нисходящем обходе (Push_st);
· функция извлечения из стека при нисходящем обходе (Pop_st);
· процедура включения в стек при восходящем и смешанном обходе (S_Push);
· функция извлечения из стека при восходящем и смешанном обходе (S_Pop).
Для прошитых деревьев:
· функция нахождения сына данного узла ( Inson );
· функция нахождения отца данного узла ( Inp );
· процедура включения в дерево узла слева от данного (leftIn);
Рекурсивные алгоритмы особенно подходят для задач, где обрабатываемые данные определяются в терминах рекурсии. Однако это не означает, что такое рекурсивное определение данных гарантирует бесспорность употребления для решения задачи рекурсивного алгоритма. Фактически объяснение концепций рекурсивных алгоритмов на неподходящих для этого примерах и вызвало широко распространенное предубеждение против использования рекурсий в программировании; их даже сделали синонимом неэффективности.
Программы, в которых следует избегать алгоритмической рекурсии, можно охарактеризовать некоторой схемой, отражающей их строение (специфично, что тут есть единственное обращение к Р в конце или начале всей конструкции):
Р≡ IF В THEN (S; Р), 3.6
Р ≡ (S; IF В THEN Р). 3.7
Такие схемы естественны в ситуациях, где вычисляемые значения определяются с помощью простых рекуррентных отношений.
Например: вычисления факториала
i =0,1,2,3,4,5,….,
fi=1,1,2,6,24,120,…. 3.8
Первое из чисел определяется явно fо = 1, а последующие определяются рекурсивным образом с помощью предшествующего числа:
fi+1= (i+1)* fi 3.9
Такое рекуррентное отношение предполагает рекурсивный алгоритм вычисления n-го факториального числа.
Если мы введем две переменные I и F, обозначающие i и fi; на i-м уровне рекурсии, то для перехода к следующему числу последовательности нужно проделать такие вычисления:
I := I+1; F: I*F 3.10
и, подставляя (3.10) вместо S в (3.6), получаем рекурсивную программу:
Р≡ IF I<n THEN I:= I+1; F: = I*F; P END; 3.11
В первую строчку (3.11) можно переписать так:
FUNCTION P;
BEGIN
IF I < n THEN BEGIN I := I+1; F := I*F; P END
END; {P}
Более часто употребляется и полностью эквивалентная запись, где вместо Р приведена так называемая процедура-функция, т. е. процедура, с которой связывается значение-результат и которую поэтому можно применять прямо как составляющую выражения.
В этом случае переменная F становится излишней, а роль I явно выполняет параметр процедуры:
FUNCTION F (I: INTEGER): INTEGER; BEGIN IF I > 0 THEN F := I*F (I-l)
ELSE F := 1
END; {F}
Теперь уже ясно, что в рекурсия крайне просто заменяется итерацией. Это проделано в такой программе:
I := 0; F :=1;
WHILE I < n DO BEGIN I := I+1; F := I*F END;
Программы, построенные по схемам (3.6) и (3.7), нужно переписывать, руководствуясь схемой:
Р≡ [х: =х0 WHILE В DO S]. (3.15)
Следовательно, следует избегать рекурсий там, где есть очевидное итерационное решение. Однако это не означает, что от рекурсий следует избавляться любой ценой.
Существует много хороших примеров применения рекурсии,
То, что существуют реализации рекурсивных процедур на фактически нерекурсивных машинах, доказывает, что для практических целей любую рекурсивную программу можно трансформировать в итеративную.
Это требует явной работы со стеком для рекурсий, причем эти действия часто настолько затуманивают суть программы, что ее бывает трудно понять.
Алгоритмы, рекурсивные по своей природе, а не итеративные, нужно формулировать как рекурсивные процедуры.
