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

Некоторые языки программирования позволяют модулю или функции вызывать себя. Этот метод известен как рекурсия. В рекурсии функцияα либо вызывает себя напрямую, либо вызывает функцию β который, в свою очередь, вызывает исходную функцию α. Функцияα называется рекурсивной функцией.

Example - функция, вызывающая сама себя.

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);

   printf("%d ",value);   
}

Example - функция, которая вызывает другую функцию, которая, в свою очередь, вызывает ее снова.

int function1(int value1) {
   if(value1 < 1)
      return;
   function2(value1 - 1);
   printf("%d ",value1);   
}
int function2(int value2) {
   function1(value2);
}

Свойства

Рекурсивная функция может быть бесконечной, как цикл. Чтобы избежать бесконечного выполнения рекурсивной функции, рекурсивная функция должна иметь два свойства:

Base criteria - Должен быть хотя бы один базовый критерий или условие, чтобы при выполнении этого условия функция перестала вызывать себя рекурсивно.
Progressive approach - Рекурсивные вызовы должны выполняться таким образом, чтобы каждый раз, когда выполняется рекурсивный вызов, он приближался к базовым критериям.

Реализация

Многие языки программирования реализуют рекурсию с помощью stacks. Как правило, всякий раз, когда функция (caller) вызывает другую функцию (callee) или себя как вызываемого, вызывающая функция передает управление выполнением вызываемому. Этот процесс передачи также может включать в себя передачу некоторых данных от вызывающего к вызываемому.

Это означает, что вызывающая функция должна временно приостановить свое выполнение и возобновить ее позже, когда управление выполнением вернется из вызываемой функции. Здесь вызывающая функция должна начинаться именно с той точки выполнения, в которой она приостанавливает выполнение. Ему также нужны те же самые значения данных, над которыми он работал. Для этого создается запись активации (или кадр стека) для вызывающей функции.

Эта запись активации хранит информацию о локальных переменных, формальных параметрах, адресе возврата и всю информацию, передаваемую вызывающей функции.

Анализ рекурсии

Кто-то может спорить, зачем использовать рекурсию, ведь ту же задачу можно выполнить с итерацией. Первая причина заключается в том, что рекурсия делает программу более читаемой, а благодаря новейшим усовершенствованным системам ЦП рекурсия более эффективна, чем итерации.

Сложность времени

В случае итераций мы берем количество итераций для подсчета временной сложности. Аналогичным образом, в случае рекурсии, предполагая, что все постоянно, мы пытаемся выяснить, сколько раз выполняется рекурсивный вызов. Вызов функции равен Ο (1), следовательно, (n) количество выполненных рекурсивных вызовов делает рекурсивную функцию Ο (n).

Космическая сложность

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