Структура данных - основы рекурсии

Некоторые языки программирования позволяют функции вызывать себя. Этот метод известен как рекурсивный алгоритм. В рекурсии функция 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).

Вычислительная сложность

Вычислительная сложность определяется как количество дополнительного объема памяти, необходимого для выполнения модуля. В случае итераций компилятору практически не требуется дополнительной памяти. Компилятор продолжает обновлять значения переменных, используемые в итерациях. Но в случае рекурсивного алгоритма система должна сохранять запись активации каждый раз, когда выполняется рекурсивный вызов. Считается, что вычислительная сложность рекурсивной функции может быть выше, чем у функции с итерацией.

Данная публикация представляет собой перевод статьи «Data Structure - Recursion Basics» , подготовленной дружной командой проекта Интернет-технологии.ру