Дипломная работа: Рекурсия

Динамическая

рекурсивная база

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

Срез рекурсивных

вычислений

При решении задачи каждое рекурсивное обращение, в том числе и начальный запуск вычислений, инициируют работу как бы со ‘своим экземпляром’ исходного алгоритма. Последовательность вычислений значений локальных и глобальных переменных, соответствующая одному конкретному ‘виртуальному экземпляру’ алгоритма и не включающая в себя вычисления по вызовам из данного экземпляра (но использующая их результаты!), называется срезом рекурсивных вычислений. 24. Формуляр Специально разработанный расчетный бланк, в котором фиксируется протокол вычислений конкретного рекурсивного среза. Формуляр может быть задан таблицей, деревом Канторовича или иным способом. В нем должны указываться взаимосвязь шагов вычислений и, кроме того, предлагаться место для проведения вычислений. 25. Воплощение Заполненный формуляр. Воплощение формируется для каждого рекурсивного среза на отдельном формуляре. Это же самое касается и всех вызовов нерекурсивных подпрограмм, для которых должны быть разработаны свои собственные формуляры. 26. Рекурсограмма Последовательность воплощений, соответствующая последовательности рекурсивных вызовов. 27.

Рекурсивная

машина

обработки

формуляров

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

Рекурсивная

тавтология

Прямое или косвенное обращение рекурсивной функции (алгоритма) к самой себе с набором значений параметров, с которого начиналось вычисление этой функции. 29.

Адаптивный

рекурсивный

алгоритм

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

Визуальное

мышление

1. Способ решения интеллектуальных задач с опорой на внутренние визуальные образы.

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

31.

Рекурсивное

мышление

1. Способ решения прикладных задач с преимущественной опорой на рекурсивные алгоритмы.

2. Разновидность математического (диалектического, продуктивного) мышления, позволяющая видеть рекурсию там, где она на первый взгляд не просматривается.

Замечания. В таблице описаны термины и понятия, связанные с рекурсией и используемые в информатике. Их оказалось чуть более 30. При этом многие понятия вводятся впервые. В то же время подобных слов и словосочетаний, активно используемых в математике порядка 300.

2. Корзина разнообразных задач

Как для конкретной задачи построить рекурсивный алгоритм её решения? - готовых рецептов не существует. Некоторые практические рекомендации на этот счет приведены в [6, стр. 144]. Однако лишь ознакомление с достаточным количеством учебных рекурсивных алгоритмов позволит выработать определенную интуицию в выборе тактики и стратегии поиска и обнаружения спасательной рекурсии в незнакомой обстановке и заложить фундамент для освоения, совершенствования и отработки техники рекурсивного программирования. Общие рекомендации здесь могли бы быть такими. Пытаясь искать рекурсивное решение какой-либо задачи, следует опираться на одну из предлагаемых ниже именованных схем.

· Схема 1 - “увидеть”. Увидеть непосредственную рекурсию в определении объекта. Во многих задачах условия не просто задают её постановку, но делают это рекурсивно. Отсюда и рекурсивные программы, являющиеся точной копией условий задачи. Смотри задачи ??? .

· Схема 2 - “переформулировать”. Часто в условиях задачи не только не проглядывается рекурсия, но и сама задача неявляется алгоритмически сформулированной. Иногда её простая перефразировка, а чаще построение математической модели позволяют вдруг обнаружить первоначально скрытую рекурсию. Смотри задачи ???.

· Схема 3 - “обобщить (погрузить, вложить)”. Если из постановки задачи рекурсию извлечь не удаётся, то за счет перехода к её некоторому обобщению иногда это сделать можно. При этом предполагается, что из решения обобщенной задачи без особого труда может быть получено решение исходной задачи. Как правило, переход к обобщенной задаче происходит за счет введения дополнительных параметров. В некоторых случаях рассматриваемая схема может быть использована для перехода от одного типа рекурсии к другому. Смотри задачи ???.

· Схема 4 - “найти родственника”. Иногда к исходной задаче удается найти одну или несколько вспомогательных родственных к ней задач так, что в совокупности, взаимно дополняя друг друга, они уже будут определять вполне просматриваемую косвенную рекурсию. Смотри задачи

· Схема 5 - “обнаружить характеристическое свойство”. Пусть совокупность всех или части условий задачи оформлена в виде некоторого предиката над наборами входных данных и возможных результатов. Такой предикат определяет некоторое характеристическое свойство задачи. Формальная запись предиката с одной стороны позволяет проводить независимую “экспертную” проверку правильности работы ранее разработанных алгоритмов решения данной задачи, а с другой стороны, может оказать существенную помощь для отыскания новых рекурсивных алгоритмов её решения. При этом иногда целесообразно преобразовать предикат, то есть переформулировать характеристическое свойство задачи так, чтобы из него можно было извлечь какой-либо иной алгоритм. В любом случае, следует помнить, что характеристические свойства не всегда определяют исходную задачу однозначно.

· Схема 6 - “перенести часть условий в проверку ”. Иногда при рассмотрении всех условий задачи рекурсия в явном виде сразу не обнаруживается, но удаление части условий приводит к новой вспомогательной задаче, рекурсивный алгоритм решения которой строится без особых затруднений. В этом случае, чтобы узнать, является ли полученный для новой задачи ответ (ответы) решением исходной задачи, необходимо проверить выполняются ли для него ранее удаленные условия или нет. Если решение задачи сводится к вычислению значения истинности некоторого предиката, непосредственно построенного из конъюнкции условий задачи на наборах входных данных, то описанная схема допускает возможность проверки выполнимости удаляемых условий как до использования рекурсивного алгоритма решения вспомогательной задачи, так и после этого. Смотри задачи ???.