Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
Когда процедура достигает условия остановки, она не выполняет рекурсию. Вместо этого, она присваивает 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
value = 1
Else
Factorial(num - 1, partial)
2 value = num * partial
End If
End Sub
После возврата процедуры из рекурсии, требуется узнать исходное значение переменной num, чтобы выполнить операцию умножения value = num * partial. Поскольку процедуре требуется доступ к значению num после возврата из рекурсии, она должна сохранять значение переменных pc и num до начала рекурсии.
Следующая процедура сохраняет эти значения в двух стеках на основе массивов. При подготовке к рекурсии, она проталкивает значения переменных num и pc в стеки. После завершения рекурсии, она выталкивает добавленные последними значения из стеков. Следующий код демонстрирует нерекурсивную версию подпрограммы вычисления факториала.
Private Sub Factorial(num As Integer, value As Integer)
ReDim num_stack(1 to 200) As Integer
ReDim pc_stack(1 to 200) As Integer
Dim stack_top As Integer ' Вершина стека.
Dim pc As Integer
pc = 1
Do
Select Case pc
Case 1
If num <= 1 Then ' Это условие остановки. value = 1
pc = 0 ' Конец рекурсии.
Else ' Рекурсия.
' Сохранить num и следующее значение pc.
stack_top = stack_top + 1
num_stack(stack_top) = num
pc_stack(stack_top) = 2 ' Возобновить с 2.
' Начать рекурсию.
num = num - 1
' Перенести блок управления в начало.
pc = 1
End If
Case 2
' value содержит результат последней
' рекурсии. Умножить его на num.
value = value * num
' "Возврат" из "рекурсии".
pc = 0
Case 0
' Конец "рекурсии".
' Если стеки пусты, исходный вызов
' подпрограммы завершен.
If stack_top <= 0 Then Exit Do
' Иначе восстановить локальные переменные и pc.
num = num_stack(stack_top)
pc = pc_stack(stack_top)
stack_top = stacK_top - 1
End Select
Loop
End Sub
Так же, как и устранение хвостовой рекурсии, этот метод имитирует поведение рекурсивного алгоритма. Процедура заменяет каждый рекурсивный вызов итерацией цикла While. Поскольку число шагов остается тем же самым, полное время выполнения алгоритма не изменяется.
Так же, как и в случае с устранением хвостовой рекурсии, этот метод устраняет глубокую рекурсию, которая может переполнить стек.
Нерекурсивное построение кривых Гильберта
Пример вычисления факториала из предыдущего раздела превратил простую, но неэффективную рекурсивную функцию вычисления факториала в сложную и неэффективную нерекурсивную процедуру. Намного лучший нерекурсивный алгоритм вычисления факториала, был представлен ранее в этой главе.
=======107-108
Может оказаться достаточно трудно найти простую нерекурсивную версию для более сложных алгоритмов. Методы из предыдущего раздела могут быть полезны, если алгоритм содержит многократную или косвенную рекурсию.
В качестве более интересного примера, рассмотрим нерекурсивный алгоритм построения кривых Гильберта.
Private Sub Hilbert(depth As Integer, Dx As Single, Dy As Single)
If depth > 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
' Подготовиться к рекурсии.
Depth = Depth - 1
' Dx и Dy остаются без изменений.
pc = 1 Перейти в начало рекурсивного вызова.
Else ' Условие остановки.
' Достаточно глубокий уровень рекурсии.
' Продолжить с 4 блоком кода.
pc = 4
End If
Case 4
HilbertPicture.Line -Step(-Dx, -Dy)
If Depth > 1 Then ' Рекурсия.
' Сохранить текущие значения.
Страницы: 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, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82
