Вопрос 9: Рекурсивные процедуры. Достоинства и недостатки рекурсии. Рекомендации по применению. Способы обхода бинарного дерева.

Рекурсивным называется объект, частично состоящий или определяемый с помощью самого себя. Рекурсивные определения представляют собой мощный аппарат в математике.

            Примеры.

            1. Факториал определяется с помощью рекурсии:

0! = 1; (n+1)! = n! (n+1).

            2. Бинарное дерево было определено рекурсивно (см. гл I, § 8).

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

            Если некоторая процедура P содержит явную ссылку на саму себя, то она называется прямо рекурсивной:

P=R[S,P].

Здесь S  - это операторы, не содержащие P.

            Если же процедура P ссылается на другую процедуру Q, содержащую ссылку на P, то P называется косвенно рекурсивной:

P=R1[S1, Q], где Q=R2[S2, P].

 Здесь S1 и S2- это операторы, не содержащие P.

            Рекурсивное обращение к процедуре P должно управляться некоторым условием, которое в какой-то конечный момент времени становится ложным. Простейшее такое условие - “n>0”. В этом случае схема рекурсивных алгоритмов должна быть следующая:

P(n)=if n>0 then R[S,P(n-1)] end

или

P(n)= R[S, if n>0 then P(n-1) end].

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

            В качестве примера рассмотрим два варианта (рекурсивный и итерационный) вычисления факториала.

            Рекурсивный вариант

                        procedure P(var i,f: integer; n: integer); {*при первом вызове i=0; f=1*}

                        begin

                                   if i<n then begin i:=i+1; f:=i*f; P(i,f,n) end

                        end;

            При работе рекурсивных процедур среда незавершенного вызова сохраняется, т.е. запоминается адрес точки прерывания, сохраняются значения переменных, параметров и т.д. Сохранение среды для незавершенных вызовов производится по принципу стека (см. гл. I, § 2.1). Таким образом, предложенный рекурсивный алгоритм вычисления факториала неэффективен как с точки зрения временной сложности (процедура тратит время на обращения к себе самой), так и с точки зрения пространственной сложности (расходуется память на сохранение среды незавершенного вызова).

            В этом случае предпочтительнее итерационный вариант:

                        ...

            i:=0; f:=1;

            while i<n do begin i:=i+1; f:=i*f end

                        ...

            Таким образом, следует избегать рекурсий там, где есть очевидное итерационное решение.

            Использовать рекурсию удобно, например, в тех случаях, когда отказ от нее заставил бы программиста самого организовывать стек для хранения промежуточных результатов. Рекурсия весьма эффективна при работе с графами. Ее применение часто позволяет давать более прозрачные и сжатые описания алгоритмов, чем это было бы возможно без рекурсии.

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

            Существуют три принципа упорядочения вершин, естественно вытекающих из структуры бинарного дерева. Выразим эти принципы в терминах рекурсии.

            I принцип. Обход сверху вниз прямом порядке): посетить корень, посетить ЛПД, посетить ППД.

            II принцип. Обход слева направо (во внутреннем порядке): посетить ЛПД, посетить корень, посетить ППД.

            III принцип. Обход снизу вверх обратном порядке): посетить ЛПД, посетить ППД, посетить корень.

            Пример. Составим двоичное дерево, соответствующее арифметическому выражению (a+b)*(-c) (рис. 2.1,а), и пронумеруем его вершины в соответствии с каждым из принципов (рис. 2.1,б,г).

            Рис. 2.1.

           

            Обход сверху вниз дает префиксную запись арифметического выражения: *+ab-c (знаки операций впереди), обход слева направо дает привычную нам инфиксную запись: a+b*-c (но без скобок), обход снизу вверх - постфиксную запись: ab+c-* (знаки операций сзади).

            Если дерево хранится в виде списка (цепным способом), то все три способа обхода легко реализовать в виде рекурсивных процедур.

           

procedure PreOrder (t: ptr);

begin   if t<>nil then begin P(t); PreOrder(t^.left); PreOrder(t^.right) end end; {*PreOrder*}

 

procedure InOrder (t: ptr);

begin   if t<>nil then begin InOrder(t^.left); P(t); InOrder(t^.right) end    end; {*InOrder*}

 

procedure PostOrder (t: ptr);

begin   if t<>nil then begin PostOrder(t^.left); PostOrder(t^.right); P(t) end         end; {*PostOrder*}

 

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