Рекурсия (стр. 1 из 12)

Нужно быть очень терпеливым,

чтобы научиться терпению.

Е. Лец

Нельзя говорить нельзя.

Д. Араго

Введение

Полезность, важность и необходимость рекурсии, как одного из концептуальных методов решения практических задач подчеркивалась многими мэтрами информатики. Сошлемся лишь на двух лауреатов премии Тьюринга: американского специалиста по системному программированию Д.Кнута и английского теоретика информатики Ч.Хоара.

Д.Кнут широко использовал рекурсию при изложении материала в ставшем уже классическим его трехтомном выпуске “Искусство программирования для ЭВМ” [1-3]. Кроме того, он предполагал продолжить издание книг этой серии и в четвертом томе одну из двух глав назвать “Рекурсия”, полностью посвятив её рекурсивным методам решения задач [1, стр.11]. К великому сожалению, тома с 4 по 7 до сих пор не вышли. Однако в настоящее время появилась надежда, что в ближайшие годы (1999г.-2004г.) они будут дописаны и опубликованы [9].

Ч.Хоару принадлежат следующие слова “Следует отдать должное гению разработчиков Алгола-60 за то, что они включили в свой язык рекурсию и дали мне тем самым возможность весьма элегантно описать мое изобретение (речь идет о так называемой быстрой сортировке – Quick Sort). Сделать возможным изящное выражение хороших мыслей – я считал это наивысшей целью проекта языка программирования” [4, стр. 176]. К этому лишь следует добавить, что, на сегодняшний день, практически все действующие языки программирования поддерживают рекурсию.

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

1.Что такое рекурсия?

Понятие рекурсии достаточно просто для понимания и не связано со знанием какого-либо определенного формализма или специальной нотации. В общем случае на рекурсию следует смотреть как на введение в определение объекта ссылку на сам объект или, более определенно, как на прием сведения решения некоторой задачи к решению “более простой” задачи такого же класса. В программировании это выражается в построении программ (процедур и функций), которые при выполнении обращаются сами к себе непосредственно или через цепочку других программ. Кажущаяся при этих самовызовах или последовательных циклических вызовах видимость порочного круга (circulus vitiosus – лат.) не более чем иллюзия. Во многих конкретных случаях простыми рассуждениями путем отслеживания значений одной или нескольких управляющих величин удается провести доказательство завершимости вычислений за конечное число шагов.

Функция называется рекурсивной, если в её определении содержится вызов этой же функции. Различают простую рекурсию, когда текст программы функции F напрямую содержит вызов F, и косвенную рекурсию, когда F обращается к иным функциям, которые содержат вызов F. Поэтому, по тексту программы рекурсивность не всегда явно определима. Знание механизмов реализации рекурсии помогает эффективно её использовать. Что происходит, когда функция F выполняет рекурсивный вызов? Прежде всего, запоминается текущее состояние программы, необходимое для продолжения вычислений, когда управление снова вернется к ней. Затем F с новыми значениями аргументов начинает выполняться заново как бы с новым экземпляром программы. При следующем рекурсивном вызове F всё повторяется и т.д. до тех пор, пока очередной вызов F не приводит к какому-либо тривиальному случаю, разрешаемому без рекурсивных вызовов. Далее, в порядке, обратном тому, в котором запоминалась серия вызовов, производятся возвраты управления. В практических приложениях важно убедиться, что максимальная глубина рекурсивных вызовов не только конечна, но и достаточно мала. В противном случае не избежать переполнения стека – специально организованного участка памяти, где запоминаются отдельные состояния программы-функции.

В таблице 1.1 приведена общая схема решения задач с помощью рекурсии. Эта схема обращается сама к себе и поэтому, является примером рекурсивного объекта. Решение конкретной задачи рекурсивным методом распадается на несколько шагов, основными из которых являются четыре этапа: параметризация, выделение базы и возможных правил её модификации, декомпозиция и проведение отложенных вычислений. Первые три из них называют рекурсивной триадой. В таблице 1.1 триада выделена общей рамкой. Остановимся на указанных этапах подробнее.

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

Выделение базы – поиск одной или нескольких подзадач, которые могут быть решены непосредственно без рекурсивного вызова.

Таблица 1.1. Рекурсивная схема решения задач с помощью рекурсии

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

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

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

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

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

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

Педагогические. Консерватизм образовательной среды по отношению к содержанию предметной области;

Методические. Отсутствие устоявшейся рабочей терминологии и понятийного аппарата, а также полноценных и доступных методических разработок по рекурсивным методам решения задач.

Технические. Недостаточные ресурсы быстродействия и, в особенности, оперативной и дисковой памяти учебных компьютеров в недавнем прошлом, а зачастую и в настоящее время.

Технологические. Отсутствие средств отладки во многих языках программирования и полное отсутствие специализированных средств отладки и тестирования рекурсивных процедур и функций.

1. О терминологии

В предыдущем пункте, поясняя, что такое рекурсия, мы были вынуждены ввести в рассмотрение несколько специальных терминов. Этот ряд необходимо продолжить. К минимальному набору, требующих прочного усвоения студентами, понятий и терминов следуют отнести следующие смысловые единицы: рекурсия, рекурсивный алгоритм, прямая рекурсия, косвенная рекурсия, рекурсивные обращения, рекуррентные соотношения (возвратные последовательности), производящая функция, параметризация задачи, вспомогательные параметры рекурсии, рекурсивная база, индикаторы завершения рекурсивных вызовов, пространство параметров, полная рекурсивная траектория, рекурсивная траектория, глубина рекурсивных вызовов, декомпозиция, предварительные вычисления, отложенные вычисления, повторительная рекурсия, рекурсивная триада, рекурсивные вычисления, прямой и обратный ход рекурсии, рекурсивный стек, динамическая рекурсивная база, срез рекурсивных вычислений, формуляр, воплощение, рекурсограмма, рекурсивная машина обработки формуляров, рекурсивная тавтология, адаптивный рекурсивный алгоритм, визуальное мышление, рекурсивное мышление. С учетом пояснений некоторых из этих терминов, сделанных в предыдущем пункте, смысл большей части остальных терминов становиться интуитивно ясным. Тем не менее, дадим им короткие пояснения (неформальные определения). Это позволит в дальнейшем избегать неточностей или двусмысленностей при описании рекурсивных алгоритмов. Все эти краткие неформальные определения собраны в таблицу 2.1