Рекурсивные методы

Суть рекурсивных методов — сведение задачи к самой себе. В современных языках программирования существует возможность рекурсивного определения функций и процедур. Эта возможность представляет собой способ программной реализации рекурсивных алгоритмов. Однако увидеть рекурсивный путь решения задачи (рекурсивный алгоритм) часто очень непросто.

Например, функция вычисления факториала числа.

Function Fact (N: byte): Longint;

Begin

If n = 0 then fact:= 1

else fact:= fact (N - 1) * N

End;

Например, в основной программе происходит вызов функции Fact (3). Тогда при входе в подпрограмму-функцию в употребление вводиться некоторая локальная переменная N, соответствующая этому параметру-значению, после чего выполняются операторы подпрограммы. Т.к. N=3, то выполняется оператор

Fact:= Fact (2)*3.

В процессе выполнения происходит новое обращение к подпрограмме Fact для вычисления значения Fact (2). При этом снова вводится в употребление локальная переменная, соответствующая этому параметру-значению. Но это уже другая переменная, например, N1. Ей присваивается значение N1:= 2, а т.к. ее значение не равно нулю, то выполняется оператор

Fact:= Fact (1)*2.

При его выполнении для вычисления Fact (1) снова требуется обращение к функции Fact, что требует введения новой локальной переменной N2 со значением, равным 1, и выполнится оператор

Fact:= Fact (0)*1.

При этом каждый раз завершение вычисления выражения в правой части оператора присваивания откладывается. При очередном обращении к подпрограмме-функции получим
N3 = 0, и в теле подпрограммы выполняется оператор Fact: = 1.

После этого завершится выполнение оператора Fact:= Fact (0)*1, т.е. получим Fact (1):= 1.

После этого завершится выполнение оператора Fact:= Fact (1)*2, что даст Fact (2):= 2, и, наконец, завершится выполнение оператора Fact:= Fact (2)*3, что даст Fact (3):= 6.

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

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

Методы перебора в задачах поиска

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

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

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

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

Рассмотрим пример. В одномерном массиве X заданы координаты п точек, лежащих на вещественной числовой оси. Точки пронумерованы. Их номера соответствуют последовательности в массиве X. Определить номер точки, наиболее удаленной от начала координат.

Легко понять, что это задача определения номера наибольшего по модулю элемента массива X. Она решается путем полного перебора следующим образом:

Const N=100;

Var X: Array [l..N] of real;

I, Number: 1..N;

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