Главная » Статьи » Основные статьи сайта |
Одну и ту же задачу можно часто решить двумя способами: с помощью итерации (с использованием цикла) и с помощью рекурсии. Рекурсия – это способ организации процесса вычисления, когда алгоритм (функция или процедура программы) обращается сам к себе. В математике рекурсивной называется функция, имя которой присутствует в обоих частях уравнения – как справа, так и слева. В программировании рекурсивной называется подпрограмма, которая в процессе выполнения вызывает сама себя. Рекурсивная подпрограмма может быть реализована и как процедура, и как функция. Принцип рекурсии позволяет решить сложную задачу путем последовательного решения более простых подзадач (например, вычисление факториала, определение натуральных чисел и некоторых функций). Рекурсия необходима в тех случаях, когда требуется перебрать слишком много вариантов. Рекурсию принято считать как одну из разновидностей циклического алгоритма. Рекурсивная форма организации позволяет придать алгоритму более компактный вид и экономить оперативную память компьютера. Содержание рекурсивного алгоритма отражает более сложный объект через более простой такого же типа. Обычно рекурсивный алгоритм содержит следующие основные части:
Если каждая рекурсивная подпрограмма вызывает саму себя один раз, то такая организация рекурсии называется линейной. Сначала в каждой активации выполняются операторы, расположенные до рекурсивного вызова, затем (при достижении условия выхода) – нерекурсивная часть очередной активации, а затем – операторы, записанные после рекурсивного вызова. Кроме линейной, достаточно часто встречается рекурсия, получившая название древовидной. При древовидной рекурсии подпрограмма в течение одной активации вызывает саму себя более одного раза. Полученная в данном случае последовательность вызовов имеет форму дерева. Основное требование к рекурсивным алгоритмам – процесс обращения не должен быть бесконечным. Другими словами, должна быть реализована проверка завершения вызова, или в рекурсивном определении должно присутствовать ограничение или граничное условие, при котором дальнейшая инициализация рекурсии прекращается. Достаточно часто в рекурсивных алгоритмах используют некоторую управляющую переменную, при достижении определенного значения которой алгоритм прекращает свою работу. Обращение к рекурсивному алгоритму, реализованному в виде функции или процедуры, ничем не отличается от обычной подпрограммы. При каждом новом рекурсивном обращении к памяти создается новая копия подпрограммы со всеми локальными переменными, увеличение которых будет до тех пор, пока не действует ограничение. Максимально возможное количество копий рекурсивной подпрограммы, которое может находиться в памяти компьютера, называется глубиной рекурсии. Каждое обращение к рекурсивной подпрограмме вызывает независимую активацию этой подпрограммы. Совокупность данных, необходимых для одной активации рекурсивной подпрограммы, называется фреймом активации. При выполнении программы фреймы активации будут размещаться в стеке – специальным образом организованной памяти. Фрейм активации включает:
Примером классической рекурсивной функции является возведение некоторого действительного числа X в степень N (Xn).
Рекомендуем следующий материал - руководство по базам данных в Delphi - http://www.programmer-lib.ru/delphi.php. Нравится | ||
Просмотров: 14646
| Теги: |
Другие статьи
|
|
|
|
Всего комментариев: 0 | |