Сравнение рекурсии и итерации

Рекурсия

Применение бинарных деревьев

Пример

function NewD(X: integer): Node; {создание нового узла со значением X; функция возвращает указатель на новый узел X} var P: Node; begin New(P); P^.Info:= X; P^.Left:= NIL; P^.Right:= NIL; NewD:= P; end; procedure SetLeft (P: Node; X: integer); {создание левого сына для узла с указателем P} begin P^.Left:= NewD(X); end; procedure SetRight(P: Node;X: integer); {создание правого сына для узла с указателем P} begin P^.Right:= NewD(X); end;

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

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

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

Рассмотрим вычисление факториала

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

Дата добавления: 2014-01-04