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

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

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *