Тезаурус по рекурсии (информатика)
Home Up Next

Н     А     В     И     Г     А     Ц     И     Я

Адаптивный рекурсивный алгоритм

Отложенные вычисления

Рекурсивная траектория

Визуальное мышление

Параметризация задачи

Рекурсивная триада

Возвратная рекурсия

Повторительная рекурсия

Рекурсивное мышление

Воплощение

Полная рекурсивная траектория

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

Вспомогательные параметры рекурсии

Полное дерево рекурсивных вызовов

Рекурсивные обращения

Глубина рекурсивных вызовов

Предвычисления (предварительные вычисления)

Рекурсивные определения

Декомпозиция

Производящая функция

Рекурсивный алгоритм (процедура, функция)

Дерево рекурсивных вызовов

Пространство параметров

Рекурсивный стек (магазин, штабель)

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

Прямая рекурсия

Рекурсия

Индикаторы завершения рекурсивных вызовов

Прямой и обратный ход вычислений

Рекурсограмма

Каскадная (древовидная) рекурсия

Рабочая ветвь рекурсивного алгоритма

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

Корень полного дерева рекурсивных вызовов

Рекуррентное соотношение (рекуррентная формула)

Терминальная ветвь рекурсивного алгоритма

Косвенная (взаимная) рекурсия

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

Удаленная рекурсия

Линейная рекурсия

Рекурсивная машина обработки формуляров

Управляющие параметры рекурсии

Объем рекурсии

Рекурсивная тавтология

Формуляр

Понятие, термин

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

1.

Рекурсия

А. Введение в определение объекта ссылки на сам объект. 

B. Прием сведения решения некоторой задачи к решению серии задач, подобных исходной. 

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

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

2.

Рекурсивный алгоритм (процедура, функция)

A. Алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма.

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

3.

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

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

4.

Прямая рекурсия

Непосредственный вызов алгоритма (функции, процедуры) F из текста самого алгоритма F.

5.

Косвенная (взаимная) рекурсия

Циклическая последовательность вызовов нескольких алгоритмов F1, F2, …, Fk (функций, процедур) друг друга: F1 вызывает F2, F2 вызывает F3, …, Fk вызывает F1 (k>1).

6.

Рекурсивные обращения

Рекурсивные вызовы в прямой или косвенной рекурсии.

7.

Пространство параметров

Пусть tk (k=1, 2, …, n) - параметры задачи (алгоритма, процедуры, функции), принимающие значения из некоторых множеств объектов Mk (k=1, 2, …, n). Декартово произведение M множеств Mk называется пространством параметров задачи. Таким образом, элементами M являются наборы (упорядоченные множества) объектов m1, m2, …, mn , где mkÎ Mk (k=1, 2, …, n) вида: (m1, m2, …, mn). Областью определения параметризованной задачи является совокупность элементов пространства параметров, при которых она имеет решение.

8.

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

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

9.

Индикаторы завершения рекурсивных вызовов

Элементы постоянной или динамической рекурсивной базы.

10.

Полное дерево рекурсивных вызовов

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

11.

Корень полного дерева рекурсивных вызовов

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

12.

Дерево рекурсивных вызовов

Любое поддерево полного дерева рекурсивных вызовов.

13.

Полная рекурсивная траектория

Пусть X=(x1, x2, …, xn) и F(X) - рекурсивная функция, которую требуется вычислить в некоторой точке X0 из области определения F(X). Конечная последовательность аргументов F(X) вида X0, X1, …, Xn называется рекурсивной траекторией, если элементы Xk (k=1, 2, …, n) - суть наборы параметров при последовательных рекурсивных вызовах, а Xn принадлежит базе рекурсии. Полная рекурсивная траектория указывает последовательность обхода вершин полного рекурсивного дерева.

14.

Рекурсивная траектория

Любая начальная подпоследовательность полной рекурсивной траектории.

15.

Объем рекурсии

Количество вершин полного рекурсивного дерева (полной рекурсивной траектории) без единицы.

16.

Рекурсивный стек (магазин, штабель)

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

17.

Глубина рекурсивных вызовов

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

18.

Декомпозиция

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

19.

Параметризация задачи

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

20.

Вспомогательные параметры рекурсии

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

21.

Рекурсивная триада

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

22.

Предвычисления (предварительные вычисления)

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

23.

Отложенные вычисления

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

24.

Терминальная ветвь рекурсивного алгоритма

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

25.

Рабочая ветвь рекурсивного алгоритма

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

26.

Управляющие параметры рекурсии

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

27.

Прямой и обратный ход вычислений

Рекурсивные вычисления состоят из двух стадий, называемых прямым ходом и обратным ходом. Первая из них соответствует совокупности всех предвычислений, реализуемых до входа рекурсивной траектории в базу, а вторая - совокупности отложенных вычислений, производимых после встречи с индикатором завершения рекурсивных вызовов.

28.

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

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

29.

Линейная рекурсия

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

30.

Повторительная рекурсия

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

31.

Каскадная (древовидная) рекурсия

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

32.

Возвратная рекурсия

Рекурсивная реализация метода перебора с возвратом (backtracking).

33.

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

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

34.

Формуляр

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

35.

Воплощение

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

36.

Рекурсограмма

Последовательность воплощений, соответствующая последовательности рекурсивных вызовов.

37.

Рекурсивная машина обработки формуляров

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

38.

Рекуррентное соотношение (рекуррентная формула)

Формула вида an+p=F(an, an+1, …, an+p-1) (p³ 1, n=1, 2, …), позволяющая вычислять любой член бесконечной последовательности a1, a2, …, если заданы её первые p членов. Определяемая рекуррентной формулой последовательность называется возвратной. Прямая реализация рекурсивных вычислений по рекуррентным формулам неизбежно приводит к каскадной рекурсии. Однако во многих важных случаях от каскадной рекурсии удается избавиться. Рекуррентные соотношения часто используются для оценки трудоемкости рекурсивных алгоритмов.

39.

Производящая функция

Производящей функцией числовой бесконечной последовательности a1, a2, …, называют степенной ряд вида с вещественной или комплексной переменной z. Подобные функции играют важную роль в аналитических методах изучения рекуррентных последовательностей.

40.

Удаленная рекурсия

Рекурсивная функция, в теле которой при рекурсивных вызовах, в выражениях, являющихся фактическими параметрами, снова встречаются рекурсивные вызовы этой функции. Удаленная рекурсия трудна в понимании и, как правило, приводит к достаточно громоздким вычислениям.

41.

Рекурсивная тавтология

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

B. Рекурсивная функция (алгоритм, программа), допускающая рекурсивную тавтологию.

42.

Адаптивный рекурсивный алгоритм

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

43.

Рекурсивные определения

Описание совокупности объектов через порождающие правила, содержащие ссылки на сам определяемый объект. Такое описание предполагает наличие некой базы неопределяемых первичных объектов, заданных простым перечислением. Примерами подобных определений являются синтаксические диаграммы Вирта, нотация Бэкуса-Наура. Рекурсивные определения могут быть как прямыми, так и косвенными.

44.

Визуальное мышление

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

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

45.

Рекурсивное мышление

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

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

Home Содержание Схемы ООД Доска объявлений Поиск