VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
алгоритм для рисования кривых Серпинского. При выполнении программы,
задавайте вначале небольшую глубину рекурсии (меньше 6), до тех пор, пока
вы не определите, насколько быстро выполняется эта программа на вашем
компьютере.
Опасности рекурсии
Рекурсия может служить мощным методом разбиения больших задач на части, но
она таит в себе несколько опасностей. В этом разделе мы пытаемся охватить
некоторые из этих опасностей и объяснить, когда стоит и не стоит
использовать рекурсию. В последующих разделах приводятся методы устранения
от рекурсии, когда это необходимо.
Бесконечная рекурсия
Наиболее очевидная опасность рекурсии заключается в бесконечной рекурсии.
Если неправильно построить алгоритм, то функция может пропустить условие
остановки рекурсии и выполняться бесконечно. Проще всего совершить эту
ошибку, если просто забыть о проверке условия остановки, как это сделано в
следующей ошибочной версии функции факториала. Поскольку функция не
проверяет, достигнуто ли условие остановки рекурсии, она будет бесконечно
вызывать сама себя.
@Рис. 5.10 Программа Sierp
=====96
Private Function BadFactorial(num As Integer) As Integer
BadFactorial = num * BadFactorial (num - 1)
End Function
Функция также может вызывать себя бесконечно, если условие остановки не
прекращает все возможные пути рекурсии. В следующей ошибочной версии
функции факториала, функция будет бесконечно вызывать себя, если входное
значение — не целое число, или если оно меньше 0. Эти значения не являются
допустимыми входными значениями для функции факториала, поэтому в
программе, которая использует эту функцию, может потребоваться проверка
входных значений. Тем не менее, будет лучше, если функция выполнит эту
проверку сама.
Private Function BadFactorial2(num As Double) As Double
If num = 0 Then
BadFactorial2 = 1
Else
BadFactorial2 = num * BadFactorial2(num-1)
End If
End Function
Следующая версия функции Fibonacci является более сложным примером. В ней
условие остановки рекурсии прекращает выполнение только нескольких путей
рекурсии, и возникают те же проблемы, что и при выполнении функции
BadFactorial2, если входные значения отрицательные или не целые.
Private Function BadFib(num As Double) As Double
If num = 0 Then
BadFib = 0
Else
BadFib = BadPib(num - 1) + BadFib (num - 2)
End If
End Function
И последняя проблема, связанная с бесконечной рекурсией, заключается в том,
что «бесконечная» на самом деле означает «до тех пор, пока не будет
исчерпано стековое пространство». Даже корректно написанные рекурсивные
процедуры будут иногда приводить к переполнению стека и аварийному
завершению работы. Следующая функция, которая вычисляет сумму N + (N - 1) +
… + 2 +1, приводит к исчерпанию стекового пространства при больших
значениях N. Наибольшее возможное значение N, при котором программа еще
будет работать, зависит от конфигурации вашего компьютера.
Private Function BigAdd(N As Double) As Double
If N 1
value = value * N
N = N - 1 ' Подготовить аргументы для "рекурсии".
Loop
Factorial = value
End Function
Private Function GCD(ByVal A As Double, ByVal B As Double) As Double
Dim B_Mod_A As Double
B_Mod_A = B Mod A
Do While B_Mod_A <> 0
' Подготовить аргументы для "рекурсии".
B = A
A = B_Mod_A
B_Mod_A = B Mod A
Loop
GCD = A
End Function
Private Function BigAdd(ByVal N As Double) As Double
Dim value As Double
value = 1# ' ' Это будет значением функции.
Do While N > 1
value = value + N
N = N - 1 ' подготовить параметры для "рекурсии".
Loop
BigAdd = value
End Function
=====101
Для алгоритмов вычисления факториала и наибольшего общего делителя
практически не существует разницы между рекурсивной и нерекурсивной
версиями. Обе версии выполняются достаточно быстро, и обе они могут
оперировать задачами большой размерности.
Для функции BigAdd, тем не менее, разница огромна. Рекурсивная версия
приводит к переполнению стека даже для довольно небольших входных значений.
Поскольку нерекурсивная версия не использует стек, она может вычислять
результат для значений N вплоть до 10154. После этого наступит переполнение
для данных типа double. Конечно, выполнение 10154 шагов алгоритма займет
очень много времени, поэтому возможно вы не станете проверять этот факт
сами. Заметим также, что значение этой функции совпадает со значением более
просто вычисляемой функции N * N(N + 1) / 2.
Программы Facto2, GCD2 и BigAdd2 демонстрируют эти нерекурсивные алгоритмы.
Нерекурсивное вычисление чисел Фибоначчи
К сожалению, нерекурсивный алгоритм вычисления чисел Фибоначчи не содержит
только хвостовую рекурсию. Этот алгоритм использует два рекурсивных вызова
для вычисления значения, и второй вызов следует после завершения первого.
Поскольку первый вызов не находится в самом конце функции, то это не
хвостовая рекурсия, и от ее нельзя избавиться, используя прием устранения
хвостовой рекурсии.
Это может быть связано и с тем, что ограничение рекурсивного алгоритма
вычисления чисел Фибоначчи связано с тем, что он вычисляет слишком много
промежуточных значений, а не глубиной вложенности рекурсии. Устранение
хвостовой рекурсии уменьшает глубину рекурсии, но оно не изменяет время
выполнения алгоритма. Даже если бы устранение хвостовой рекурсии было бы
применимо к алгоритму вычисления чисел Фибоначчи, этот алгоритм все равно
остался бы чрезвычайно медленным.
Проблема этого алгоритма в том, что он многократно вычисляет одни и те же
значения. Значения Fib(1) и Fib(0) вычисляются Fib(N + 1) раз, когда
алгоритм вычисляет Fib(N). Для вычисления Fib(29), алгоритм вычисляет одни
и те же значения Fib(0) и Fib(1) 832.040 раз.
Поскольку алгоритм многократно вычисляет одни и те же значения, следует
найти способ избежать повторения вычислений. Простой и конструктивный
способ сделать это — построить таблицу вычисленных значений. Когда
понадобится промежуточное значение, можно будет взять его из таблицы,
вместо того, чтобы вычислять его заново.
=====102
В этом примере можно создать таблицу для хранения значений функции
Фибоначчи Fib(N) для N, не превосходящих 1477. Для N >= 1477 происходит
переполнение переменных типа double, используемых в функции. Следующий код
содержит измененную таким образом функцию, вычисляющую числа Фибоначчи.
Const MAX_FIB = 1476 ' Максимальное значение.
Dim FibValues(0 To MAX_FIB) As Double
Private Function Fib(N As Integer) As Double
' Вычислить значение, если оно не находится в таблице.
If FibValues(N) < 0 Then _
FibValues(M) = Fib(N - 1) + Fib(N - 2)
Fib = FibValues(N)
End Function
При запуске программы, она присваивает каждому элементу в массиве FibValues
значение -1. Затем она присваивает FibValues(0) значение 0, и
FibValues(1) — значение 1. Это условия остановки рекурсии.
При выполнении функции, она проверяет, находится ли уже в массиве значение,
которое ей требуется. Если его там нет, она, как и раньше, рекурсивно
вычисляет это значение и сохраняет его в массиве для дальнейшего
использования.
Программа Fibo2 использует этот метод для вычисления чисел Фибоначчи.
Программа может быстро вычислить Fib(N) для N до 100 или 200. Но если вы
попытаетесь вычислить Fib(1476), то программа выполнит последовательность
рекурсивных вызовов глубиной 1476 уровней, которая вероятно переполнит стек
вашей системы.
Тем не менее, по мере того, как программа вычисляет новые значения, она
заполняет массив FibValues. Значения из массива позволяют функции вычислять
все большие и большие значения без глубокой рекурсии. Например, если
вычислить последовательно Fib(100), Fib(200), Fib(300), и т.д. то, в конце
концов, можно будет заполнить массив значений FibValues и вычислить
максимальное возможно значение Fib(1476).
Процесс медленного заполнения массива FibValues приводит к новому методу
вычисления чисел Фибоначчи. Когда программа инициализирует массив
FibValues, она может заранее вычислить все числа Фибоначчи.
Private Sub InitializeFibValues()
Dim i As Integer
FibValues(0) = 0 ' Инициализация условий остановки.
FibValues(1) = 1
For i = 2 To MAX_FIB
FibValues(i) = FibValues(i - 1) + FibValues(i - 2)
Next i
End Sub
Private Function Fib(N As Integer) As Duble
Fib - FibValues(N)
End Function
=====104
Определенное время в этом алгоритме занимает составление массива с
табличными значениями. Но после того как массив создан, для получения
элемента из массива требуется всего один шаг. Ни процедура инициализации,
ни функция Fib не используют рекурсию, поэтому ни одна из них не приведет к
исчерпанию стекового пространства. Программа Fibo3 демонстрирует этот
подход.
Стоит упомянуть еще один метод вычисления чисел Фибоначчи. Первое
рекурсивное определение функции Фибоначчи использует подход сверху вниз.
Для получения значения Fib(N), алгоритм рекурсивно вычисляет Fib(N - 1) и
Fib(N - 2) и затем складывает их.
Подпрограмма InitializeFibValues, с другой стороны, работает снизу вверх.
Она начинает со значений Fib(0) и Fib(1). Она затем использует меньшие
значения для вычисления больших, до тех пор, пока таблица не заполнится.
Вы можете использовать тот же подход снизу вверх для прямого вычисления
значений функции Фибоначчи каждый раз, когда вам потребуется значение. Этот
метод требует больше времени, чем выборка значений из массива, но не
требует дополнительной памяти для таблицы значений. Это пример
пространственно-временного компромисса. Использование большего объема
памяти для хранения таблицы значений делает выполнение алгоритма более
быстрым.
Private Function Fib(N As Integer) As Double
Dim Fib_i_minus_1 As Double
Dim Fib_i_minus_2 As Double
Dim fib_i As Double
Dim i As Integer
If N
Subr()
End Sub
Поскольку после рекурсивного шага есть еще операторы, вы не можете
использовать устранение хвостовой рекурсии для этого алгоритма.
=====105
Вначале пометим первые строки в 1 и 2 блоках кода. Затем эти метки будут
использоваться для определения места, с которого требуется продолжить
выполнение при возврате из «рекурсии». Эти метки используются только для
того, чтобы помочь вам понять, что делает алгоритм — они не являются частью
кода Visual Basic. В этом примере метки будут выглядеть так:
Sub Subr(num)
1
Subr()
2
End Sub
Используем специальную метку «0» для обозначения конца «рекурсии». Теперь
можно переписать процедуру без использования рекурсии, например, так:
Sub Subr(num)
Dim pc As Integer ' Определяет, где нужно продолжить рекурсию.
pc = 1 ' Начать сначала.
Do
Select Case pc
Case 1
If (достигнуто условие остановки) Then
' Пропустить рекурсию и перейти к блоку 2.
pc = 2
Else
' Сохранить переменные, нужные после рекурсии.
' Сохранить pc = 2. Точка, с которой
продолжится
' выполнение после возврата из "рекурсии".
' Установить переменные, нужные для рекурсии.
' Например, num = num - 1.
:
' Перейти к блоку 1 для начала рекурсии.
pc = 1
End If
Case 2 ' Выполнить 2 блок кода
pc = 0
Case 0
If (это последняя рекурсия) Then Exit Do
' Иначе восстановить pc и другие переменные,
' сохраненные перед рекурсией.
End Select
Loop
End Sub
======106
Переменная pc, которая соответствует счетчику программы, сообщает
процедуре, какой шаг она должна выполнить следующим. Например, при pc = 1,
процедура должна выполнить 1 блок кода.
Когда процедура достигает условия остановки, она не выполняет рекурсию.
Вместо этого, она присваивает pc значение 2, и продолжает выполнение 2
блока кода.
Если процедура не достигла условия остановки, она выполняет «рекурсию». Для
этого она сохраняет значения всех локальных переменных, которые ей
понадобятся позже после завершения «рекурсии». Она также сохраняет значение
pc для участка кода, который она будет выполнять после завершения
«рекурсии». В этом примере следующим выполняется 2 блок кода, поэтому она
сохраняет 2 в качестве следующего значения pc. Самый простой способ
сохранения значений локальных переменных и pc состоит в использовании
стеков, подобных тем, которые описывались в 3 главе.
Реальный пример поможет вам понять эту схему. Рассмотрим слегка измененную
версию функции факториала. В нем переписана только подпрограмма, которая
возвращает свое значение при помощи переменной, а не функции, для упрощения
работы.
Private Sub Factorial(num As Integer, value As Integer)
Dim partial As Integer
1 If num 1 Then Hilbert depth - 1, Dy, Dx
HilbertPicture.Line -Step(Dx, Dy)
If depth > 1 Then Hilbert depth - 1, Dx, Dy
HilbertPicture.Line -Step(Dy, Dx)
If depth > 1 Then Hilbert depth - 1, Dx, Dy
HilbertPicture.Line -Step(-Dx, -Dy)
If depth > 1 Then Hilbert depth - 1, -Dy, -Dx
End Sub
В следующем фрагменте кода первые строки каждого блока кода между
рекурсивными шагами пронумерованы. Эти блоки включают первую строку
процедуры и любые другие точки, в которых может понадобиться продолжить
выполнение после возврата после «рекурсии».
Private Sub Hilbert(depth As Integer, Dx As Single, Dy As Single)
1 If depth > 1 Then Hilbert depth - 1, Dy, Dx
2 HilbertPicture.Line -Step(Dx, Dy)
If depth > 1 Then Hilbert depth - 1, Dx, Dy
3 HilbertPicture.Line -Step(Dy, Dx)
If depth > 1 Then Hilbert depth - 1, Dx, Dy
4 HilbertPicture.Line -Step(-Dx, -Dy)
If depth > 1 Then Hilbert depth - 1, -Dy, -Dx
End Sub
Каждый раз, когда нерекурсивная процедура начинает «рекурсию», она должна
сохранять значения локальных переменных Depth, Dx, и Dy, а также следующее
значение переменной pc. После возврата из «рекурсии», она восстанавливает
эти значения. Для упрощения работы, можно написать пару вспомогательных
процедур для заталкивания и выталкивания этих значений из нескольких
стеков.
====109
Const STACK_SIZE =20
Dim DepthStack(0 To STACK_SIZE)
Dim DxStack(0 To STACK_SIZE)
Dim DyStack(0 To STACK_SIZE)
Dim PCStack(0 To STACK_SIZE)
Dim TopOfStack As Integer
Private Sub SaveValues (Depth As Integer, Dx As Single, _
Dy As Single, pc As Integer)
TopOfStack = TopOfStack + 1
DepthStack(TopOfStack) = Depth
DxStack(TopOfStack) = Dx
DyStack(TopOfStack) = Dy
PCStack(TopOfStack) = pc
End Sub
Private Sub RestoreValues (Depth As Integer, Dx As Single, _
Dy As Single, pc As Integer)
Depth = DepthStack(TopOfStack)
Dx = DxStack(TopOfStack)
Dy = DyStack(TopOfStack)
pc = PCStack(TopOfStack)
TopOfStack = TopOfStack - 1
End Sub
Следующий код демонстрирует нерекурсивную версию подпрограммы Hilbert.
Private Sub Hilbert(Depth As Integer, Dx As Single, Dy As Single)
Dim pc As Integer
Dim tmp As Single
pc = 1
Do
Select Case pc
Case 1
If Depth > 1 Then ' Рекурсия.
' Сохранить текущие значения.
SaveValues Depth, Dx, Dy, 2
' Подготовиться к рекурсии.
Depth = Depth - 1
tmp = Dx
Dx = Dy
Dy = tmp
pc = 1 ' Перейти в начало рекурсивного
вызова.
Else ' Условие остановки.
' Достаточно глубокий уровень рекурсии.
' Продолжить со 2 блоком кода.
pc = 2
End If
Case 2
HilbertPicture.Line -Step(Dx, Dy)
If Depth > 1 Then ' Рекурсия.
' Сохранить текущие значения.
SaveValues Depth, Dx, Dy, 3
' Подготовиться к рекурсии.
Depth = Depth - 1
' Dx и Dy остаются без изменений.
pc = 1 Перейти в начало рекурсивного
вызова.
Else ' Условие остановки.
' Достаточно глубокий уровень рекурсии.
' Продолжить с 3 блоком кода.
pc = 3
End If
Case 3
HilbertPicture.Line -Step(Dy, Dx)
If Depth > 1 Then ' Рекурсия.
' Сохранить текущие значения.
SaveValues Depth, Dx, Dy, 4
' Подготовиться к рекурсии.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31
|