Основы офисного программирования и язык VBA

       

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


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

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

Пример 9.3.

(html, txt)

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

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

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

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



Содержание раздела