Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
=====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 вплоть до 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 раз.
Поскольку алгоритм многократно вычисляет одни и те же значения, следует найти способ избежать повторения вычислений. Простой и конструктивный способ сделать это — построить таблицу вычисленных значений. Когда понадобится промежуточное значение, можно будет взять его из таблицы, вместо того, чтобы вычислять его заново.
Страницы: 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
