Рекурсивные процедуры

VBA допускает создание рекурсивных процедур, т. е. процедур, при вычислении вызывающих самих себя. Вызовы рекурсивной процедуры могут непосредственно входить в ее тело, или она может вызывать себя через другие процедуры. В последнем случае в модуле есть несколько связанных рекурсивных процедур. Стандартный пример рекурсивной процедуры - функция-факториал Fact(N)= N!. Вот ее определение в VBA:

Function Fact(N As Integer) As Long

If N <= 1 Then ' базис индукции.

Fact = 1 ' 0! =1.

Else ' рекурсивный вызов в случае N > 0.

Fact = Fact(N - 1) * N

End If

End Function

Так как каждый вызов процедуры требует накладных расходов, эффективнее для факториала итеративная программа:

Function Fact1(N As Integer) As Long

Dim Fact As Long, i As Integer

Fact = 1 ' 0! =1.

If N > 1 Then ' цикл вместо рекурсии.

For i = 1 To N

Fact = Fact * i

Next i

End If

Fact1 = Fact

End Function

Приведем процедуру, оценивающую время исполнения рекурсивного и не рекурсивного варианта:

Public Sub TestRecursive()

'Сравнение по времени рекурсивной и нерекурсивной реализации факториала.

Dim i As Long, Res As Long

Dim Start As Single, Finish As Single

'Рекурсивное вычисление факториала

Start = Timer

For i = 1 To 100000

Res = Fact(12)

Next i

Finish = Timer

Debug.Print "Время рекурсивных вычислений:", Finish - Start

'Нерекурсивное вычисление факториала

Start = Timer

For i = 1 To 100000

Res = Fact1(12)

Next i

Finish = Timer

Debug.Print "Время нерекурсивных вычислений:", Finish - Start

End Sub

Пример 9.3. (html, txt)

Вот результаты вычислений, приведенные для двух запусков тестовой процедуры:

Время рекурсивных вычислений: 6,238281

Время нерекурсивных вычислений: 2,304688

Время рекурсивных вычислений: 6,25

Время нерекурсивных вычислений: 2,253906

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

Польза от рекурсивных процедур в большей мере может проявиться при обработке данных, имеющих рекурсивную структуру (скажем, иерархическую или сетевую). Основные структуры данных (объекты) Office 97 вообще-то не являются рекурсивными: один рабочий лист Excel не может быть значением ячейки другого, одна таблица Access - элементом другой и т.д. Но данные, хранящиеся на рабочих листах Excel или в БД Access, сами по себе могут задавать "рекурсивные" отношения, и для их успешной обработки следует пользоваться рекурсивными процедурами. Мы рассмотрим сейчас класс, для работы с двоичными деревьями поиска. Деревья представляют рекурсивную структуру данных, поэтому и операции над ними естественным образом определяются рекурсивными алгоритмами.

Деревья поиска

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

Бинарным будем называть дерево, у которого каждая вершина имеет одного или двух потомков, называемых левым и правым сыном (поддеревом). В дальнейшем будем полагать, что узел нашего дерева содержит информационное поле info и поле ключа - key. Деревом поиска (двоичным или лексикографическим деревом) будем называть бинарное дерево, в котором ключ каждой вершины больше ключа, хранящегося в корне левого поддерева, и меньше ключа, хранящегося в корне правого поддерева.

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