Рекурсия и деревья

аналогичный объект в виде некоторой его части. Существуют рекурсивные структуры данных

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

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

Рекурсия и поисковые задачи

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

может повлиять на характер протекания процесса поиска и реализуемый алгоритм будет выполнять полный перебор всех возможных вариантов;
Если рекурсивная функция выполняет поиск первого попавшегося варианта, то результатом ее является как правило логическое значение (в Си - 0/1). При этом «ИСТИНА» соответствует успешному завершению поиска, а «ЛОЖЬ» - неудачному. Общим для всех алгоритмов поиска является: если рекурсивный вызов возвращает «ИСТИНУ», то она должна быть немедленно «передана наверх», то есть текущий вызов также должен быть завершен со значением «ИСТИНА». Если рекурсивный вызов возвращает «ЛОЖЬ», по поиск должен быть продолжен. При завершении полного перебора всех вариантов рекурсивная функция также должна возвратить «ЛОЖЬ»;
Если в процессе поиска производится более сложный анализ и сравнение вариантов, то рекурсивная функция и, соответственно, шаг процесса должны производить выбор между подходящими вариантами, в целью выбора наиболее оптимального. Обычно для этого используется минимум или максимум какой-либо характеристики выбираемого варианта. Тогда рекурсивная функция возвращает значение, которое является оценкой для оставшихся не просмотренных элементов, а текущий рекурсивный вызов выбирает из них минимум или максимум с учетом данных текущего шага.

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

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

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

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

следующие дополнительные условия (свойства дерева поиска):
Оба поддерева – левое и правое, являются двоичными деревьями поиска;
У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X;
У всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X.
Данные в каждом узле должны обладать ключами, на которых определена операция сравнения.
Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных.