Рекурсия

№

Понятие,

Термин

Неформальное определение,

пояснение

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. Разновидность математического (диалектического, продуктивного) мышления, позволяющая видеть рекурсию там, где она на первый взгляд не просматривается.