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

Таблица 2.1. Понятия и термины, связанные с рекурсией

№	Понятие,Термин	Неформальное определение,пояснение
1.	Рекурсия	1. Введение в определение объекта ссылку на сам объект.2. Прием сведения решения некоторой задачи к решению серии задач, подобных исходной. 3. Свойство алгоритмической системы на промежуточных этапах своего функционирования создавать другие системы, включая идентичные себе самой, и использовать результаты их функционирования в дальнейшей работе. При достаточно широкой трактовке понятия алгоритмической системы концепция рекурсивности отражает основные формы развития материи и является одним из важнейших методов познания.
2.	Рекурсивныйалгоритм(процедура,функция)	1. Алгоритм (функция, процедура) называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма. 2. Рекурсивная функция - одно из математических уточнений интуитивного понятия вычислимой функции.
3.	Прямаярекурсия	Непосредственный вызов алгоритма (функции, процедуры) F из текста самого алгоритма F.
4.	Косвеннаярекурсия	Циклическая последовательность вызовов нескольких алгоритмов (функций, процедур) F1, F2, … Fkдруг друга: F1 вызывает F2, F2 вызывает F3, …, Fkвызывает F1 (k>1).
5.	Рекурсивныеобращения(рекурсивныевызовы)	Прямая или косвенная рекурсия при рекурсивных вычислениях
6.	Рекуррентноесоотношение(рекуррентная формула)	Формула вида an+p=F(an, an+1,…, an+p-1) (p³1), позволяющая вычислять любой член бесконечной последовательности a1, a2,…, если заданы её первые p членов. Определяемая рекуррентной формулой последовательность называется возвратной.
7.	Производящаяфункция	Производящей функцией числовой бесконечной последовательности a1, a2,…, называют степенной ряд вида: , с вещественной или комплексной переменной z.
8.	Параметризациязадачи	Выявление совокупности исходных величин, определяющих постановку и решение задачи. Значения этих параметров или некоторых из них влияют на трудоемкость решения задачи.
9.	Вспомогательныепараметрырекурсии	Параметры, напрямую с постановкой задачи не связанные, но помогающие изменить тип рекурсии или перейти к обобщенной задаче, где рекурсия проглядывается явно.
10.	Рекурсивная база	Совокупность наборов значений параметров и соответствующих им решений задачи (или простых правил для получения этих решений). Выделение базы - один из основных этапов решения задачи с помощью рекурсии.
11.	Индикаторызавершениярекурсивныхвызовов	Элементы постоянной или динамической рекурсивной базы.
12.	Пространствопараметров	Пусть tk(k=1..n) параметры задачи (алгоритма, процедуры, функции), принимающие значения из некоторых множеств объектов Mk (k=1..n). Декартово произведение M множеств Mk (k=1..n) называется пространством параметров задачи. Таким образом, элементами M являются наборы (упорядоченные множества) объектов m1, m2, … mn, где mkÎMk (k=1..n) вида: (m1, m2, … mn). Областью определения параметризованной задачи, является совокупность элементов пространства параметров, при которых она имеет решение.
13.	Полная рекурсивнаятраектория	Пусть F(X), где X=(x1, x2,…xn) - рекурсивная функция, которую требуется вычислить в некоторой точке X0. Конечная последовательность аргументов F(X) вида: X0, X1, …Xnназывается рекурсивной траекторией, если элементы Xk (k =1..n) - суть наборы параметров при последовательных рекурсивных вызовах, а Xn принадлежит базе рекурсии.
14.	Рекурсивнаятраектория	Любая начальная подпоследовательность полной рекурсивной траектории.
15.	Глубина рекурсивныхвызовов	Количество элементов полной рекурсивной траектории в пространстве параметров.
16.	ДекомпозицияПредварительныевычисления(предвычисления)	Процесс последовательного разложения задачи на серию более простых подзадач, аналогичных исходной задаче, каждая из которых обычно по тому или иному признаку более близка к тривиальному случаю, чем предыдущая. Декомпозиция предполагает наличие некоторых вычислений, предшествующих и способствующих переходам к более простым подзадачам. Назовем их предварительными вычислениями или предвычислениями. Декомпозицию необходимо осуществлять так, чтобы несложно было доказать, что при любом допустимом наборе значений параметров, рано, или поздно, она приведет нас к одному из выделенных тривиальных случаев, то есть к задаче с набором параметров, являющемся индикатором завершения рекурсивных вызовов.
17.	ОтложенныевычисленияПовторительнаярекурсия	Вычисления, проводимые после того, как рекурсивная траектория попала в базу, то есть стала полной. Возможно, что отложенные вычисления состоят лишь из серии передач значений и управления в порядке, обратном рекурсивным вызовам. В этом случае реальные отложенные вычисления отсутствуют, а соответствующая рекурсия называется повторительной.
18.	Управляющиепараметрырекурсии(управляющийпараметр)	Параметры задачи, с помощью которых организуется её декомпозиция, обеспечивающая правила выполнения рекурсивных вызовов, а также предварительных и отложенных вычислений.
19.	Рекурсивнаятриада	Три основных этапа решения задач с помощью рекурсии: параметризация, выделение базы (или выделение начальной базы и правил её изменения), декомпозиция.
20.	РекурсивныевычисленияПрямой иобратный ходвычислений	Вычисления, проводимые с помощью рекурсивных алгоритмов. Они состоят из двух стадий, называемых прямым ходом и обратным ходом. Первая из них соответствует совокупности всех предвычислений, реализуемых до входа рекурсивной траектории в базу, а вторая - совокупности отложенных вычислений, производимым после встречи с индикатором завершения рекурсивных вызовов.
21.	Рекурсивный стек	Область памяти, в которую заносятся значения всех локальных переменных алгоритма (программы) в момент рекурсивного обращения. Каждое такое обращение формирует один слой данных стека. При завершении вычислений по конкретному обращению a из стека считывается соответствующий ему слой данных, и локальные переменные восстанавливаются, снова принимая значения, которые они имели в момент обращения a.
22.	Динамическаярекурсивная база	Рекурсивная база, меняющаяся в процессе вычислений. Как правило, она расширяется за счет получения решений промежуточных задач и облегчает выполнение процесса отложенных вычислений. Возможно и сужение рекурсивной базы.
23.	Срез рекурсивныхвычислений	При решении задачи каждое рекурсивное обращение, в том числе и начальный запуск вычислений, инициируют работу как бы со ‘своим экземпляром’ исходного алгоритма. Последовательность вычислений значений локальных и глобальных переменных, соответствующая одному конкретному ‘виртуальному экземпляру’ алгоритма и не включающая в себя вычисления по вызовам из данного экземпляра (но использующая их результаты!), называется срезом рекурсивных вычислений.
24.	Формуляр	Специально разработанный расчетный бланк, в котором фиксируется протокол вычислений конкретного рекурсивного среза. Формуляр может быть задан таблицей, деревом Канторовича или иным способом. В нем должны указываться взаимосвязь шагов вычислений и, кроме того, предлагаться место для проведения вычислений.
25.	Воплощение	Заполненный формуляр. Воплощение формируется для каждого рекурсивного среза на отдельном формуляре. Это же самое касается и всех вызовов нерекурсивных подпрограмм, для которых должны быть разработаны свои собственные формуляры.
26.	Рекурсограмма	Последовательность воплощений, соответствующая последовательности рекурсивных вызовов.
27.	Рекурсивнаямашинаобработкиформуляров	Если правила заполнения формуляров при решении определенного круга задач с помощью рекурсии некоторым образом формализованы, то этот процесс может быть автоматизирован. В этом смысле можно говорить о виртуальной рекурсивной машине по заполнению формуляров.
28.	Рекурсивнаятавтология	Прямое или косвенное обращение рекурсивной функции (алгоритма) к самой себе с набором значений параметров, с которого начиналось вычисление этой функции.
29.	Адаптивныйрекурсивныйалгоритм	Алгоритм, который благодаря рекурсивности учитывает те или иные индивидуальные характеристики решаемой задачи из области своего определения.
30.	Визуальноемышление	1. Способ решения интеллектуальных задач с опорой на внутренние визуальные образы.2. Вид мышления, продуктом которого является порождение новых образов, создание новых визуальных форм, несущих определенную смысловую нагрузку.
31.	Рекурсивноемышление	1. Способ решения прикладных задач с преимущественной опорой на рекурсивные алгоритмы.2. Разновидность математического (диалектического, продуктивного) мышления, позволяющая видеть рекурсию там, где она на первый взгляд не просматривается.

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