Необоснованное применение рекурсии

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

 

=====98

 

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

С другой стороны, применение рекурсии ухудшает алгоритм вычисления чисел Фибоначчи. Для вычисления Fib(N), алгоритм вначале вычисляет Fib(N - 1) и Fib(N - 2). Но для вычисления Fib(N - 1) он должен сначала вычислить Fib(N - 2) и Fib(N - 3). При этом Fib(N - 2) вычисляется дважды.

Предыдущий анализ этого алгоритма показал, что Fib(1) и Fib(0) вычисляются Fib(N + 1) раз во время вычисления Fib(N). Так как Fib(30) = 832.040 то, чтобы вычислить Fib(29), приходится вычислять одни и те же значения Fib(0) и Fib(1) 832.040 раз. Алгоритм вычисления чисел Фибоначчи тратит огромное количество времени на вычисление этих промежуточных значений снова и снова.

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

Похожая проблема существует и в функции факториала. Для входного значения N глубина рекурсии для факториала и функции BigAdd равна N. Функция факториала не может быть вычислена для таких больших входных значений, которые допустимы для функции BigAdd. Максимальное значение факториала, которое может уместиться в переменной типа double, равно 170! » 7,257E+306, поэтому это наибольшее значение, которое может вычислить эта функция. Хотя эта функция приводит к глубокой рекурсии, она вызывает переполнение до того, как наступит переполнение стека.

Когда нужно использовать рекурсию

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

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

С другой стороны, нерекурсивные версии алгоритмов построений кривых Гильберта и Серпинского намного сложнее. Их труднее понять, поддерживать, и они даже выполняются немного медленнее, чем рекурсивные версии. Они приведены лишь для того, чтобы продемонстрировать методы, которые вы можете использовать для устранения рекурсии из сложных алгоритмов, а не потому, что они лучше, чем рекурсивные версии соответствующих алгоритмов.

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

 

======99

 

Хвостовая рекурсия

Вспомним представленные ранее функции для вычисления факториалов и наибольшего общего делителя, а также функцию 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

 

Во всех этих функциях, последнее действие перед завершением функции — это рекурсивный шаг. Этот тип рекурсии в конце процедуры называется хвостовой рекурсией (tail recursion или end recursion).

Так как после рекурсии в процедуре ничего не происходит, существует простой способ ее устранения. Вместо рекурсивного вызова функции, процедура сбрасывает свои параметры, устанавливая те, которые бы она получила при рекурсивном вызове, и затем выполняется снова.

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

 

Private Sub Recurse(A As Integer)

' Выполняются какие‑либо действия, вычисляется B, и т.д.

Recurse B

End Sub

 

 

======100

 

Эту процедуру можно переписать без рекурсии как:

 

Private Sub NoRecurse(A As Integer)

Do While (not done)

   ' Выполняются какие‑либо действия, вычисляется B, и т.д.

   A = B

Loop

End Sub

 

Эта процедура называется устранением хвостовой рекурсии (tail recursion removal или end recursion removal). Этот прием не изменяет время выполнения программы. Рекурсивные шаги просто заменяются проходами в цикле While.

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

Некоторые компиляторы автоматически устраняют хвостовую рекурсию, но компилятор Visual Basic этого не делает. В противном случае, функция BigAdd, приведенная в предыдущем разделе, не приводила бы к переполнению стека.

Используя устранение хвостовой рекурсии, легко переписать функции факториала, наибольшего общего делителя, и 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

 

 

=====101

 

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

Для функции BigAdd, тем не менее, разница огромна. Рекурсивная версия приводит к переполнению стека даже для довольно небольших входных значений. Поскольку нерекурсивная версия не использует стек, она может вычислять результат для значений N вплоть до 10¹⁵⁴. После этого наступит переполнение для данных типа double. Конечно, выполнение 10¹⁵⁴ шагов алгоритма займет очень много времени, поэтому возможно вы не станете проверять этот факт сами. Заметим также, что значение этой функции совпадает со значением более просто вычисляемой функции N * N(N + 1) / 2.

Программы Facto2, GCD2 и BigAdd2 демонстрируют эти нерекурсивные алгоритмы.