20
осточноукраинский
национальный университет имени Владимира
Даля
Рекурсия
Информатика и компьютерная техника
© Велигура А.В., кафедра экономической кибернетики, 2004
Рекурсия — мощный метод программирования, который позволяет разбить задачу на части все меньшего и меньшего размера до тех пор, пока они не станут настолько малы, что решение этих подзадач сведется к набору простых операций.
После того, как вы приобретете опыт применения рекурсии, вы будете обнаруживать ее повсюду. Многие программисты, недавно овладевшие рекурсией, увлекаются, и начинают применять ее в ситуациях, когда она является ненужной, а иногда и вредной.
Что такое рекурсия?
Рекурсия происходит, если функция или подпрограмма вызывает сама себя. Прямая рекурсия (direct recursion) выглядит примерно так:
Function Factorial(num As Long) As Long
Factorial = num * Factorial(num - 1)
End Function
В случае косвенной рекурсии(indirectrecursion) рекурсивная процедура вызывает другую процедуру, которая, в свою очередь, вызывает первую:
Private Sub Ping(num As Integer)
Pong(num - 1)
End Sub
Private Sub Pong(num As Integer)
Ping(num / 2)
End Sub
Рекурсия полезна при решении задач, которые естественным образом разбиваются на несколько подзадач, каждая из которых является более простым случаем исходной задачи. Можно представить дерево в виде «ствола», на котором находятся два дерева меньших размеров. Тогда можно написать рекурсивную процедуру для рисования деревьев:
Private Sub DrawTree()
Нарисовать "ствол"
Нарисовать дерево меньшего размера, повернутое на -45 градусов
Нарисовать дерево меньшего размера, повернутое на 45 градусов
End Sub
Хотя рекурсия и может упростить понимание некоторых проблем, люди обычно не мыслят рекурсивно. Они обычно стремятся разбить сложные задачи на задачи меньшего объема, которые могут быть выполнены последовательно одна за другой до полного завершения. Например, чтобы покрасить изгородь, можно начать с ее левого края и продолжать двигаться вправо до завершения. Вероятно, во время выполнения подобной задачи вы не думаете о возможности рекурсивной окраски — вначале левой половины изгороди, а затем рекурсивно — правой.
Для того чтобы думать рекурсивно, нужно разбить задачу на подзадачи, которые затем можно разбить на подзадачи меньшего размера. В какой‑то момент подзадачи становятся настолько простыми, что могут быть выполнены непосредственно. Когда завершится выполнение подзадач, большие подзадачи, которые из них составлены, также будут выполнены. Исходная задача окажется выполнена, когда будут все выполнены образующие ее подзадачи.
Опасности рекурсии
Бесконечная рекурсия
Наиболее очевидная опасность рекурсии заключается в бесконечной рекурсии. Если неправильно построить алгоритм, то функция может пропустить условие остановки рекурсии и выполняться бесконечно. Проще всего совершить эту ошибку, если просто забыть о проверке условия остановки, как это сделано в следующей ошибочной версии функции факториала. Поскольку функция не проверяет, достигнуто ли условие остановки рекурсии, она будет бесконечно вызывать сама себя.
Private Function BadFactorial(num As Integer) As Integer
BadFactorial = num * BadFactorial (num - 1)
End Function
Функция также может вызывать себя бесконечно, если условие остановки не прекращает все возможные пути рекурсии. В следующей ошибочной версии функции факториала, функция будет бесконечно вызывать себя, если входное значение — не целое число, или если оно меньше 0. Эти значения не являются допустимыми входными значениями для функции факториала, поэтому в программе, которая использует эту функцию, может потребоваться проверка входных значений. Тем не менее, будет лучше, если функция выполнит эту проверку сама.
Private Function BadFactorial2(num As Double) As Double
If num = 0 Then
BadFactorial2 = 1
Else
BadFactorial2 = num * BadFactorial2(num-1)
End If
End Function
Следующая версия функции Fibonacciявляется более сложным примером. В ней условие остановки рекурсии прекращает выполнение только нескольких путей рекурсии, и возникают те же проблемы, что и при выполнении функцииBadFactorial2, если входные значения отрицательные или не целые.
Private Function BadFib(num As Double) As Double
If num = 0 Then
BadFib = 0
Else
BadFib = BadPib(num - 1) + BadFib (num - 2)
End If
End Function
И последняя проблема, связанная с бесконечной рекурсией, заключается в том, что «бесконечная» на самом деле означает «до тех пор, пока не будет исчерпано стековое пространство». Даже корректно написанные рекурсивные процедуры будут иногда приводить к переполнению стека и аварийному завершению работы. Следующая функция, которая вычисляет сумму N + (N - 1) + … + 2 +1, приводит к исчерпанию стекового пространства при больших значенияхN. Наибольшее возможное значениеN, при котором программа еще будет работать, зависит от конфигурации вашего компьютера.
Private Function BigAdd(N As Double) As Double
If N <= 1 Then
BigAdd = 1
Else
BigAdd=N + BigAdd(N - 1)
End If
End Function
Программа BigAddна диске с примерами демонстрирует этот алгоритм. Проверьте, насколько большое входное значение вы можете ввести в этой программе до того, как наступит переполнение стека на вашем компьютере.