4. Устранение рекурсии в общем случае

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

Некоторые рекурсивные алгоритмы настолько сложны, то применение этих методов затруднено или невозможно.

Основной подход при этом заключается в том, чтобы рассмотреть порядок выполнения рекурсии на компьютере и затем попытаться сымитировать шаги, выполняемые компьютером. Затем новый алгоритм будет сам осуществлять «рекурсию» вместо того, чтобы всю работу выполнял компьютер.

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

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

Рассмотрим следующую обобщенную рекурсивную процедуру:

Sub Subr(num)

<1 блок кода>

Subr(<параметры>)

<2 блок кода>

End Sub

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

Вначале пометим первые строки в 1 и 2 блоках кода. Затем эти метки будут использоваться для определения места, с которого требуется продолжить выполнение при возврате из «рекурсии». Эти метки используются только для того, чтобы помочь вам понять, что делает алгоритм — они не являются частью кода VisualBasic. В этом примере метки будут выглядеть так:

Sub Subr(num)

1 <1 блок кода>

Subr(<параметры>)

2 <2 блок кода>

End Sub

Используем специальную метку «0» для обозначения конца «рекурсии». Теперь можно переписать процедуру без использования рекурсии, например, так:

Sub Subr(num)

Dim pc As Integer ' Определяет, где нужно продолжить рекурсию.

pc = 1 ' Начать сначала.

Do

Select Case pc

Case 1

<1 блок кода>

If (достигнуто условие остановки) Then

' Пропустить рекурсию и перейти к блоку 2.

pc = 2

Else

' Сохранить переменные, нужные после рекурсии.

' Сохранить pc = 2. Точка, с которой продолжится

' выполнение после возврата из "рекурсии".

' Установить переменные, нужные для рекурсии.

' Например, num = num - 1.

:

' Перейти к блоку 1 для начала рекурсии.

pc = 1

End If

Case 2 ' Выполнить 2 блок кода

<2 блок кода>

pc = 0

Case 0

If (это последняя рекурсия) Then Exit Do

' Иначе восстановить pc и другие переменные,

' сохраненные перед рекурсией.

End Select

Loop

End Sub

Переменная 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

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. Поскольку число шагов остается тем же самым, полное время выполнения алгоритма не изменяется.

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

5. Резюме

При применении рекурсивных алгоритмов следует избегать трех основных опасностей:

• Бесконечной рекурсии. Убедитесь, что условия остановки вашего алгоритма прекращают все рекурсивные пути.

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

• Ненужной рекурсии. Обычно это происходит, если алгоритм типа рекурсивного вычисления чисел Фибоначчи, многократно вычисляет одни и те же промежуточные значения. Если вы столкнетесь с этой проблемой в своей программе, попробуйте переписать алгоритм, используя подход снизу вверх. Если алгоритм не позволяет прибегнуть к подходу снизу вверх, создайте таблицу промежуточных значений.

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

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

Задача о Ханойских башнях. Имеются три стержня с номерами 1, 2, 3. На стержень 1 надетоNдисков различного диаметра так, что они образуют пирамиду. Написать программу для печати последовательности перемещений дисков со стержня на стержень, необходимых для переноса пирамиды со стержня 1 на стержень 3 при использовании стержня 2 в качестве вспомогательного. При этом за одно перемещение должен переноситься только один диск, и диск большего диаметра не должен помещаться на диск меньшего диаметра. Доказано, что дляNдисков минимальное число необходимых перемещений равно.

Для решения простейшего случая задачи, когда пирамида состоит только из одного диска, необходимо выполнить одно действие – перенести диск со стержня Iна стерженьJ, что очевидно (обозначим такой переносIJ). Общий случай задачи изображен на рис 2., когда требуется перенестиNдисков со стержняIна стерженьJ, считая стерженьWвспомогательным. Сначала следует перенестиN-1 диск со стержняIна стерженьWпри вспомогательном стержнеJ, затем перенести один диск со стержняIна стерженьJ, и, наконец, перенестиN-1 диск изWна стерженьJ, используя вспомогательный стерженьI. Итак, задача о переносеNдисков сводится к двум задачам о переносеN-1 диска и одной простейшей задаче. Схематически это можно записать так:T(N,I,J,W)≈T(N-1,I,W,J),T(1,I,J,W),T(N-1,W,J,I).

Рекурсивный вариант процедуры приведен ниже.

Sub Hanoy()

Dim m As Integer

m=InputBox("Введите количество дисков", 5)

disk_exch m, 1, 3, 2

End Sub

Sub disk_exch(n As Integer, i As Integer, j As Integer, w As Integer)

If n > 1 Then

disk_exch n - 1, i, w, j

disk_exch 1, i, j, w

disk_exch n - 1, w, j, i

Else

Debug.Print i & "-->" & j

End If

End Sub

Протокол работы для 3-х дисков:

1-->3

1-->2

3-->2

1-->3

2-->1

2-->3

1-->3

Задание: переписать процедуру без рекурсии.

13