Структура данных - основы рекурсии
Некоторые языки программирования позволяют функции вызывать себя. Этот метод известен как рекурсивный алгоритм. В рекурсии функция a вызывает непосредственно саму себя или вызывает функцию b, которая в свою очередь вызывает оригинальную функцию a. Функция a называется рекурсивной.
Пример — функция, вызывающая себя:
int function(int value) {
if(value < 1)
return;
function(value - 1);
printf("%d ",value);
}Пример — функция, которая вызывает другую функцию, которая в свою очередь, вызывает ее снова:
int function(int value) {
if(value < 1)
return;
function(value - 1);
printf("%d ",value);
}Свойства
Рекурсивная функция может быть бесконечной, как цикл. Чтобы избежать бесконечного выполнения функции, есть два принципа, которых нужно придерживаться при программировании рекурсивных алгоритмов:
- Основной критерий — должно быть, по крайней мере, одно условие, при выполнении которого функция прекращала бы рекурсивный вызов.
- Прогрессивный подход — рекурсивные вызовы должны развиваться таким образом, чтобы при каждом вызове приближаться к выполнению базового условия.
Реализация
Во многих языках программирования рекурсия реализуется с помощью стеков. Всякий раз, когда функция вызывает другую функцию (или саму себя), вызывающая функция передает управление вызываемой структуре. Этот процесс передачи также может включать в себя передачу данных от вызывающей функции к вызываемой.
Из этого следует, что вызывающая функция должна приостановить свое выполнение, и возобновить его позже, когда управление будет возвращено ей. Вызывающая функция должна запуститься именно в той точке исполнения, где остановилась. Для продолжения работы ей нужны те же значения параметров. С этой целью для вызывающей функции создается запись активации (или фрейм стека):
Фрейм стека хранит информацию о локальных переменных, формальных параметрах, адрес возврата, а также все сведения, передаваемые вызываемой функции.
Анализ рекурсии
Но зачем использовать рекурсию, если та же задача может быть выполнена с помощью итераций? Использование рекурсивных функций в теории алгоритмов делает код более читабельным, а современные процессоры делают рекурсию более эффективной, чем итерации.
Сложность по времени
Чтобы подсчитать время работы алгоритма на основе итераций, мы используем количество операций. С рекурсией все аналогично: мы пытаемся выяснить процессорное время, за которое выполняется рекурсивный вызов. Вызов функции 0(1), следовательно (n) — количество рекурсивных вызовов, которые выполнит рекурсивная функция 0(n).
Вычислительная сложность
Вычислительная сложность определяется как количество дополнительного объема памяти, необходимого для выполнения модуля. В случае итераций компилятору практически не требуется дополнительной памяти. Компилятор продолжает обновлять значения переменных, используемые в итерациях. Но в случае рекурсивного алгоритма система должна сохранять запись активации каждый раз, когда выполняется рекурсивный вызов. Считается, что вычислительная сложность рекурсивной функции может быть выше, чем у функции с итерацией.
Пожалуйста, оставьте ваши мнения по текущей теме статьи. За комментарии, подписки, лайки, дизлайки, отклики огромное вам спасибо!