Пусть F(X), где X=(x1 , x2 ,…xn ) - рекурсивная функция, которую требуется вычислить в некоторой точке X0 . Конечная последовательность аргументов F(X) вида: X0 , X1 , …Xn называется рекурсивной траекторией, если элементы Xk (k =1..n) - суть наборы параметров при последовательных рекурсивных вызовах, а Xn принадлежит базе рекурсии.
14.
Рекурсивная
траектория
Любая начальная подпоследовательность полной рекурсивной траектории.
15.
Глубина
рекурсивных
вызовов
Количество элементов полной рекурсивной траектории в пространстве параметров.
16.
Декомпозиция
Предварительные
вычисления
(предвычисления)
Процесс последовательного разложения задачи на серию более простых подзадач, аналогичных исходной задаче, каждая из которых обычно по тому или иному признаку более близка к тривиальному случаю, чем предыдущая. Декомпозиция предполагает наличие некоторых вычислений, предшествующих и способствующих переходам к более простым подзадачам. Назовем их предварительными вычислениями или предвычислениями . Декомпозицию необходимо осуществлять так, чтобы несложно было доказать, что при любом допустимом наборе значений параметров, рано, или поздно, она приведет нас к одному из выделенных тривиальных случаев, то есть к задаче с набором параметров, являющемся индикатором завершения рекурсивных вызовов.
17.
Отложенные
вычисления
Повторительная
рекурсия
Вычисления, проводимые после того, как рекурсивная траектория попала в базу, то есть стала полной. Возможно, что отложенные вычисления состоят лишь из серии передач значений и управления в порядке, обратном рекурсивным вызовам. В этом случае реальные отложенные вычисления отсутствуют, а соответствующая рекурсия называется повторительной.
18.
Управляющие
параметры
рекурсии
(управляющий
параметр)
Параметры задачи, с помощью которых организуется её декомпозиция, обеспечивающая правила выполнения рекурсивных вызовов, а также предварительных и отложенных вычислений.
19.
Рекурсивная
триада
Три основных этапа решения задач с помощью рекурсии: параметризация, выделение базы (или выделение начальной базы и правил её изменения), декомпозиция.
20.
Рекурсивные
вычисления
Прямой и
обратный ход
вычислений
Вычисления, проводимые с помощью рекурсивных алгоритмов. Они состоят из двух стадий, называемых прямым ходом и обратным ходом. Первая из них соответствует совокупности всех предвычислений, реализуемых до входа рекурсивной траектории в базу, а вторая - совокупности отложенных вычислений, производимым после встречи с индикатором завершения рекурсивных вызовов.