Учебники

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

Декабрь 12, 2018

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

Пример — функция, вызывающая себя сама. 

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

   printf("%d ",value);   
}

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

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

свойства

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

  • Базовые критерии — должен быть хотя бы один базовый критерий или условие, чтобы при выполнении этого условия функция перестала вызывать себя рекурсивно.

  • Прогрессивный подход — рекурсивные вызовы должны развиваться таким образом, чтобы каждый раз, когда выполняется рекурсивный вызов, он приближался к базовым критериям.

Базовые критерии — должен быть хотя бы один базовый критерий или условие, чтобы при выполнении этого условия функция перестала вызывать себя рекурсивно.

Прогрессивный подход — рекурсивные вызовы должны развиваться таким образом, чтобы каждый раз, когда выполняется рекурсивный вызов, он приближался к базовым критериям.

Реализация

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

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

Активация Записи

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

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

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

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

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

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

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

50
Share: