Рекурсивные алгоритмы
Рекурсия – это способ организации процесса вычисления, когда алгоритм обращается сам к себе.
Принцип рекурсии позволяет решить сложную задачу путем последовательного решения более простых подзадач.
Как правило, рекурсия необходима в тех случаях, когда требуется перебрать слишком много вариантов. Рекурсию принято считать как одну из разновидностей циклического алгоритма. Рекурсивная форма организации позволяет придать алгоритму более компактный вид. Таким образом, решается проблема от сложного к простому – содержание рекурсивного алгоритма отражает более сложный объект через более простой такого же типа. Обычно рекурсивный алгоритм содержит следующие основные части:
Различают прямую и косвенную рекурсию. В первом случае алгоритм содержит функцию, которая сама себя вызывает. Если функция вызывает другую функцию, которая, в свою очередь, вызывает первую, то такая функция называется косвенно рекурсивной.
Основное требование к рекурсивным алгоритмам – процесс обращения не должен быть бесконечным. Другими словами, должна быть реализована проверка завершения вызова, или в рекурсивном определении должно присутствовать ограничение, при котором дальнейшая инициализация рекурсии прекращается.
Примером рекурсивной функции является вычисление суммы элементов массива.
Принцип рекурсии позволяет решить сложную задачу путем последовательного решения более простых подзадач.
Как правило, рекурсия необходима в тех случаях, когда требуется перебрать слишком много вариантов. Рекурсию принято считать как одну из разновидностей циклического алгоритма. Рекурсивная форма организации позволяет придать алгоритму более компактный вид. Таким образом, решается проблема от сложного к простому – содержание рекурсивного алгоритма отражает более сложный объект через более простой такого же типа. Обычно рекурсивный алгоритм содержит следующие основные части:
- условие для завершения цикла
- тело рекурсии, которое включает действия, предназначенные для выполнения на каждой итерации
- шаг рекурсии, на котором рекурсивный алгоритм вызывает сам себя
Различают прямую и косвенную рекурсию. В первом случае алгоритм содержит функцию, которая сама себя вызывает. Если функция вызывает другую функцию, которая, в свою очередь, вызывает первую, то такая функция называется косвенно рекурсивной.
Основное требование к рекурсивным алгоритмам – процесс обращения не должен быть бесконечным. Другими словами, должна быть реализована проверка завершения вызова, или в рекурсивном определении должно присутствовать ограничение, при котором дальнейшая инициализация рекурсии прекращается.
Примером рекурсивной функции является вычисление суммы элементов массива.
Function XSum (k As Integer, x () As Single) As Single
If k = 0 Then
XSum = 0
Else: XSum = x (k)+ XSum (k-1, x)
End If
End Function
Алексей Иванов
Опубликовано 28-08-2023
147