Предыдущий раздел

Рекуррентные вычисления

  Вернемся к задаче, которую уже однажды решали:
  Задача 1. Написать функцию
 
FUNCTION Factorial(n:WORD):REAL;
 
вычисляющую факториал n! = 1·2·…·n неотрицательного целого n.

Наверное, стоит восстановить в памяти первое решение этой задачи, полученное нами ранее.

Обычно в учебниках идею рекурсии демонстрируют именно на этой задаче. Следуя этому обычаю, мы здесь тоже предложим второе, рекурсивное, решение. Оно основано на так называемом "рекуррентном определении" факториала:

Иначе такие определения в математике называют определениями "по индукции". Первая строка в приведенной записи является "базой индукции", а вторая представляет собой "шаг индукции".

В действительности второе (рекурсивное) решение этой задачи намного хуже первого, и я намерен довольно скоро объяснить, почему.

Сначала разберем, как работает рекурсивная функция и каких правил надо придерживаться при сочинении рекурсивного алгоритма. Возьмите файл с текстом программы и загрузите его в Turbo-Pascal. Откройте окно со стеком вызовов (опция меню Debug/Call stack), после чего выполняйте программу пошагово, используя клавишу <F7>:

Вы увидите (см. рис.), что каждый раз функция Factorial, в свою очередь, вызывает самое себя, но с меньшим на 1 значением аргумента. Вот это последовательное обращение функции к себе и называется в программировании рекурсией. Важно, что последовательность обращений не становится бесконечной, а прекращается в какой-то момент благодаря наличию "базы индукции" Factorial := 1.

Правило 1. Необходимо обеспечить завершение процесса рекурсивных вызовов функции (процедуры) на каком-то шаге. Для этого, во-первых, в теле функции должно быть предусмотрено условие, при выполнении которого дальнейшая рекурсия не требуется. Во-вторых, необходимо обеспечить такое изменение данных при повторных функции (процедуры), чтобы это условие рано или поздно наступило.

Когда, наконец, оно наступило, начинается "обратный ход" рекурсивного алгоритма. Полученное значение 1 умножается предыдущим экземпляром функции Factorial на 2, затем предыдущий экземпляр домножает произведение на 3, и т.д. (см. схему справа). Таким образом, Pascal сам берет на себя заботу об организации циклического повторения вычислительных операций.

Заметим, что при вычислениях "обратного хода" область памяти, занятая в программном стеке под организацию вызовов функции Factorial, освобождается. Программный стек – это относительно небольшая и поэтому дефицитная часть оперативной памяти компьютера, используемая для организации вызовов процедур и функций и для хранения локальных переменных. Левая часть схемы иллюстрирует использование программного стека для рекурсивного вычисления 8!. Каждый зеленый прямоугольник символизирует расход памяти стека для одного вызова функции (до 14 байт), а белый – память, отведенную под локальные переменные (аргумент функции, передаваемый по значению, можно рассматривать как частный случай локальной переменной этой функции). Рассматривая эту схему, можно прийти к следующим правилам.

Правило 2. Глубина рекурсии, т.е. максимальное количество вложенных вызовов функции или процедуры, должна быть не слишком большой.
Правило 3. Необходимо экономно расходовать локальные переменные рекурсивной функции.
Правило 4. Не следует отключать контроль использования стека (опция меню Options/Compiler/Stack checking или директива компилятора {$S+}) во избежание его переполнения. (Переполнение стека может вызвать сбой системы и повлечь за собой перезагрузку системы.)

В то же время

Правило 5. Следует избегать такого программирования, при котором рекурсивная функция (или процедура) вносит изменения в глобальные данные. Если же это правило приходится нарушить, то к таким изменениям требуется уделять повышенное внимание.

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

Можно спросить, зачем же тогда стоило весь огород городить. Дело в том, что простота программирования в других, более серьезных задачах, может оказаться решающим фактором. Наверное, любую рекурсивную программу можно переписать так, чтобы убрать рекурсию. Наверное даже, это можно доказать, как теорему. Но в результате программа может сильно усложниться, и тут надо решать, а стоит ли это делать.

  Задача 2. Написать функцию, вычисляющую определитель квадратной матрицы с целочисленными элементами. В основу вычислительного алгоритма положить формулу разложения по строке

где – элемент матрицы A, стоящий на пересечении i-той строки с j-тым столбцом матрицы, а – его минор, т.е. определитель n–1-го порядка, составленный из элементов, оставшихся после вычеркивания i-той строки и j-того столбца.

Здесь приводится решение этой задачи.

Следующий раздел