Когда нужно использовать рекурсию
Эти рассуждения могут заставить вас думать, что рекурсия всегда нежелательна. Но это определенно не так. Многие алгоритмы являются рекурсивными по своей природе. И хотя любой алгоритм можно переписать так, чтобы он не содержал рекурсии, многие алгоритмы сложнее понимать, анализировать, отлаживать и поддерживать, если они написаны нерекурсивно.
Если алгоритм рекурсивен по природе, записывайте его с использованием рекурсии. В лучшем случае, вы не встретитесь ни одной из описанных проблем. Если же вы столкнетесь с некоторыми из них, вы сможете переписать алгоритм без использования рекурсии при помощи методов, представленных в следующих разделах. Переписать алгоритм часто гораздо проще, чем с самого начала написать его без применения рекурсии.
Хвостовая рекурсия
Вспомним представленные ранее функции для вычисления факториалов и наибольшего общего делителя, а также функцию BigAdd, которая приводит к переполнению стека даже для относительно небольших входных значений.
Private Function Factorial(num As Integer) As Integer
If num <= 0 Then
Factorial = 1
Else
Factorial = num * Factorial(num - 1)
End If
End Function
Private Function GCD(A As Integer, B As Integer) As Integer
If B Mod A = 0 Then
GCD = A
Else
GCD = GCD(B Mod A, A)
End If
End Function
Private Function BigAdd(N As Double) As Double
If N <= 1 Then
BigAdd = 1
Else
BigAdd = N + BigAdd(N - 1)
End If
End Function
Во всех этих функциях, последнее действие перед завершением функции — это рекурсивный шаг. Этот тип рекурсии в конце процедуры называется хвостовой рекурсией(tailrecursion).
Так как после рекурсии в процедуре ничего не происходит, существует простой способ ее устранения. Вместо рекурсивного вызова функции, процедура сбрасывает свои параметры, устанавливая те, которые бы она получила при рекурсивном вызове, и затем выполняется снова.
Рассмотрим общий случай рекурсивной процедуры:
Private Sub Recurse(A As Integer)
' Выполняются какие‑либо действия, вычисляется B, и т.д.
Recurse B
End Sub
Эту процедуру можно переписать без рекурсии как:
Private Sub NoRecurse(A As Integer)
Do While (not done)
' Выполняются какие‑либо действия, вычисляется B, и т.д.
A = B
Loop
End Sub
Эта процедура называется устранением хвостовой рекурсии(tailrecursionremoval). Этот прием не изменяет время выполнения программы. Рекурсивные шаги просто заменяются проходами в циклеWhile.
Устранение хвостовой рекурсии, тем не менее, устраняет вызовы подпрограмм, и поэтому может увеличить скорость работы алгоритма. Что более важно, этот метод также уменьшает использование стека.
Некоторые компиляторы автоматически устраняют хвостовую рекурсию, но компилятор VisualBasicэтого не делает.
Используя устранение хвостовой рекурсии, легко переписать функции факториала, наибольшего общего делителя, и BigAddбез рекурсии. Эти версии используют зарезервированное словоByValдля сохранения значений своих параметров для вызывающей процедуры.
Private Function Factorial(ByVal N As Integer) As Double
Dim value As Double
value = 1# ' Это будет значением функции.
Do While 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
Для алгоритмов вычисления факториала и наибольшего общего делителя практически не существует разницы между рекурсивной и нерекурсивной версиями. Обе версии выполняются достаточно быстро, и обе они могут оперировать задачами большой размерности.
Для функции BigAdd, тем не менее, разница огромна. Рекурсивная версия приводит к переполнению стека даже для довольно небольших входных значений. Поскольку нерекурсивная версия не использует стек, она может вычислять результат для значенийNвплоть до 10154. После этого наступит переполнение для данных типаdouble. Конечно, выполнение 10154шагов алгоритма займет очень много времени, поэтому возможно вы не станете проверять этот факт сами. Заметим также, что значение этой функции совпадает со значением более просто вычисляемой функцииN* N(N + 1) / 2.